پاورپوینت کامل درس طراحی الگوریتم ها ۲۵۹ اسلاید در PowerPoint

توجه : این فایل به صورت فایل power point (پاور پوینت) ارائه میگردد

 پاورپوینت کامل درس طراحی الگوریتم ها ۲۵۹ اسلاید در PowerPoint دارای ۲۵۹ اسلاید می باشد و دارای تنظیمات کامل در PowerPoint می باشد و آماده ارائه یا چاپ است

شما با استفاده ازاین پاورپوینت میتوانید یک ارائه بسیارعالی و با شکوهی داشته باشید و همه حاضرین با اشتیاق به مطالب شما گوش خواهند داد.

لطفا نگران مطالب داخل پاورپوینت نباشید، مطالب داخل اسلاید ها بسیار ساده و قابل درک برای شما می باشد، ما عالی بودن این فایل رو تضمین می کنیم.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل می باشد و در فایل اصلی پاورپوینت کامل درس طراحی الگوریتم ها ۲۵۹ اسلاید در PowerPoint،به هیچ وجه بهم ریختگی وجود ندارد

---

بخشی از مطالب داخلی اسلاید ها

پاورپوینت کامل درس طراحی الگوریتم ها ۲۵۹ اسلاید در PowerPoint

اسلاید ۴: بکار بردن تکنیک منجر به روشی گام به گام (الگوریتم ) در حل یک مسئله می شود. منظورازسریع بودن یک الگوریتم، یعنی تحلیل آن از لحاظ زمان و حافظه.

اسلاید ۵: نوشتن الگوریتم به زبان فارسی دو ایراد دارد:۱- نوشتن الگوریتم های پیچیده به این شیوه دشوار است.۲- مشخص نیست از توصیف فارسی الگوریتم چگونه می توان یک برنامه کامپیوتری ایجاد کرد.

اسلاید ۶: الگوریتم ۱-۱: جست و جوی ترتیبیVoid seqsearch ( int n const keytype S[ ] keytype x, index& location){ location = 1; while (location <= n && S[location] ! = x) location++; if (location > n ) location = 0 ;

اسلاید ۷: الگوریتم ۲-۱:محاسبه مجموع عناصر آرایهnumber sum (int n , const number s[ ]){ index i; number result; result = 0; for (i = 1; i <= n; i++) result = result + s[i]; return result;}

اسلاید ۸: الگوریتم ۳-۱:مرتب سازی تعویضیمسئله: n کلید را به ترتیب غیر نزولی مرتب سازی کنید. void exchangesort (int n , keytype S[ ]) { index i,j; for (i = 1 ; i<= n -1; i++) for (j = i +1; j <= n ; j++) if ( S[j] < S[i]) exchange S[i] and S[j];}

اسلاید ۹: الگوریتم ۴-۱:ضرب ماتریس ها void matrixmult (int n const number A [ ] [ ], const number B [ ] [ ], number C [ ] [ ], { index i , j, k; for ( i = 1; I <= n ; i++) for (i = 1; j <= n ; j++)} C [i] [j] = 0;

اسلاید ۱۰: for (k = 1 ; k <= n ; k++) C [i][j] = C[i] [j] + A [i][k] * B [k][j] } }

اسلاید ۱۱: ۲- ۱اهمیت ساخت الگوریتم های کارآمدجست و جوی دودویی معمولا بسیار سریع تر ازجست و جوی ترتیبی است.تعداد مقایسه های انجام شده توسط جست و جوی دودویی برابر با lg n + 1 است .

اسلاید ۱۲: الگوریتم ۱-۱: جست و جوی ترتیبیVoid seqsearch ( int n const keytype S[ ] keytype x, index& location){ location = 1; while (location <= n && S[location] ! = x) location++; if (location > n ) location = 0 ;

اسلاید ۱۳: الگوریتم ۵-۱: جست و جوی دودوییVoid binsearch (int n, const keytype S[ ], keytype x, index& location){ index low, high, mid; low = 1 ; high = n; location = 0; while (low <= high && location = = 0) { mid = (low + high)/2;

اسلاید ۱۴: if ( x = = S [mid]) location = mid; else if (x < S [mid]) high = mid – ۱; else low = mid + 1; } }

اسلاید ۱۵: الگوریتم ۶-۱: جمله n ام فیبوناچی (بازگشتی)مسئله : جمله n ام از دنباله فیبوناچی را تعیین کنید. int fib (int n) { if ( n <= 1) return n; else return fib (n – ۱) + fib (n – ۲); }

اسلاید ۱۶: الگوریتم ۷-۱:جمله nام فیبوناچی (تکراری) int fib2 (int n) { index i; int f [0..n]; f[0] = 0; if (n > 0) { f[1] = 1; for (i = 2 ; I <= n; i++) f[i] = f [i -1] + f [i -2]; } return f[n]; }

اسلاید ۱۷: ۳-۱ تحلیل الگوریتم هابرای تعیین میزان کارایی یک الگوریتم را باید تحلیل کرد.۱-۳-۱ تحلیل پیچیدگی زمانیتحلیل پیچیدگی زمانی یک الگوریتم ، تعیین تعداد دفعاتی است که عمل اصلی به ازای هر مقدار از ورودی انجام می شود.

اسلاید ۱۸: T(n) را پیچیدگی زمانی الگوریتم در حالت معمول می گویند.W(n) را تحلیل پیچیدگی زمانی در بدترین حالت می نامند.A(n) را پیچیدگی زمانی در حالت میانگین می گویند.

اسلاید ۱۹: تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم(جمع کردن عناصرآرایه)عمل اصلی: افزودن یک عنصر از آرایه به sum.اندازه ورودی: n، تعداد عناصر آرایه.T(n) = n

اسلاید ۲۰: تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم(مرتب سازی تعویضی) عمل اصلی: مقایسه S [j] با S[i] .اندازه ورودی: تعداد عناصری که باید مرتب شوند.T(n) = n(n -1) /2

اسلاید ۲۱: تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم(جست و جوی ترتیبی)عمل اصلی: مقایسه یک عنصر آرایه با x.اندازه ورودی: , n تعداد عناصر موجود در آرایه.W (n) = n

اسلاید ۲۲: تحلیل پیچیدگی زمانی در بهترین حالت برای الگوریتم(جست وجوی ترتیبی)عمل اصلی: مقایسه یک عنصر آرایه با x.اندازه ورودی: , n تعداد عناصر آرایه.B (n) = 1

اسلاید ۲۳: ۴-۱مرتبه الگوریتمالگوریتم ها یی با پیچیدگی زمانی ازقبیل n و۱۰۰n را الگوریتم های زمانی خطی می گویند.مجموعه کامل توابع پیچیدگی را که با توابع درجه دوم محض قابل دسته بندی باشند، n²) ( می گویند.

اسلاید ۲۴: مجموعه ای ازتوابع پیچیدگی که با توابع درجه سوم محض قابل دسته بندی باشند، n³) ( نامیده می شوند.برخی از گروه های پیچیدگی متداول در زیر داده شده است:(lg n) < (n) < (n lg n) < (n²) < (n³) < (2 )

اسلاید ۲۵: ۲-۴-۱آشنایی بیشتر با مرتبه الگوریتم هابرای یک تابع پیچیدگی مفروض ƒ(n) ،O (ƒ (n) ”O بزرگ“ مجموعه ای از توابع پیچیدگی g (n) است که برای آن ها یک ثابت حقیقی مثبت c و یک عدد صحیح غیر منفی N وجود دارد به قسمی که به ازای همه ی N =< n داریم:g (n) >= c × ƒ (n)

اسلاید ۲۶: برای یک تابع پیچیدگی مفروض ƒ(n) ، ( (ƒ(n)مجموعه ای از توابع پیچیدگی g (n) است که برای آن ها یک عدد ثابت حقیقی مثبت c و یک عدد صحیح غیر منفی N وجود دارد به قسمی که به ازای همه ی N =< n داریم:g (n) =< c × ƒ (n)

اسلاید ۲۷: برای یک تابع پیچیدگی مفروض ƒ(n)، داریم: (ƒ(n)) = O (ƒ(n)) (ƒ(n)) یعنی (ƒ(n)) مجموعه ای از توابع پیچیدگی g (n) است که برای آن ها ثابت های حقیقی مثبت c وd و عدد صحیح غیر منفی N وجود دارد به قسمی که :c × ƒ (n) <= d × ƒ(n)

اسلاید ۲۸: برای یک تابع پیچیدگی ƒ(n) مفروض،( o(ƒ(n) ”o کوچک” عبارت ازمجموعه کلیه توابع پیچیدگیg (n) است که این شرط را برآورده می سازند : به ازای هرثابت حقیقی مثبت c ،یک عدد صحیح غیر منفی N وجود دارد به قسمی که به ازای همه ی N =< n داریم:g (n) =< c × ƒ (n)

اسلاید ۲۹: ویژگی های مرتبه۱- O (ƒ(n)) g (n) اگروفقط اگر.ƒ (n) (g(n))2- (ƒ(n)) g (n) اگروفقط اگرƒ (n) (g (n)).3- اگر b >1 و a > 1، در آن صورت:log a (log b) 4- اگر b > a > 0 ،در آن صورت:a o (b)

اسلاید ۳۰: ۵- به ازای همه ی مقادیر a > 0 داریم :a o (n!)6- اگرc >= 0، d >0 ، g (n) o (ƒ(n)) وh(n) (ƒ(n)) باشد، درآن صورت:c × g(n) + d × h (n) (ƒ(n))

اسلاید ۳۱: ۷- ترتیب دسته های پیچیدگی زیر را در نظربگیرید: (lg n) (n) (n lg n) (n²) (n^j) (n^k) (a) (b) (n!) که در آن k > j > 2 و b > a > 1 است. اگر تابع پیچیدگیg (n) در دسته ای واقع در طرف چپ دسته ی حاوی ƒ (n) باشد، در آن صورت:g (n) o (ƒ(n))

اسلاید ۳۲: فصل دوم: روش تقسیم و حل

اسلاید ۳۳: روش تقسیم و حل یک روش بالا به پایین است.حل یک نمونه سطح بالای مسئله با رفتن به جزء و بدست آوردن حل نمونه های کوچکتر حاصل می شود.

اسلاید ۳۴: هنگام پی ریزی یک الگوریتم بازگشتی ، باید:۱- راهی برای به دست آوردن حل یک نمونه از روی حل یک نمونه ازروی حل یک یا چند نمونه کوچک تر طراحی کنیم.۲- شرط(شرایط ) نهایی نزدیک شدن به نمونه(های) کوچک تر را تعیین کنیم.۳- حل را در حالت شرط (شرایط)نهایی تعیین کنیم.

اسلاید ۳۵: الگوریتم۱-۲: جست و جوی دودویی (بازگشتی) index location ( index low, index high ){ index mid; if (low > high ) return 0; else { mid = (low + high) /2; if (x = = S [mid]) return mid;

اسلاید ۳۶: else if ( x < S [mid]) return location (low , mid – ۱); else return location (mid + 1, high); } }

اسلاید ۳۷: تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم جست و جوی دودویی بازگشتی عمل اصلی: مقایسه x با S [mid]. اندازه ورودی: n ، تعداد عناصر آرایه.W (n) = W (n / 2) + 1 برای n >1 ، n توانی از ۲ است W (n) = W (n / 2) + 1 W (1) = 1 W (n) = lg n + 1 (lg n)

اسلاید ۳۸: ۲-۲مرتب سازی ادغامیادغام یک فرآیند مرتبط با مرتب سازی است.ادغام دوطرفه به معنای ترکیب دو آرایه مرتب شده در یک آرایه ی مرتب است.

اسلاید ۳۹: مرتب سازی ادغامی شامل مراحل زیر می شود:۱- تقسیم آرایه به دو زیر آرایه، هر یک با n/2 عنصر.۲- حل هر زیر آرایه با مرتب سازی آن.۳- ترکیب حل های زیر آرایه ها از طریق ادغام آن ها در یک آرایه مرتب.

اسلاید ۴۰: الگوریتم۲-۲: مرتب سازی ادغامی void mergsort (int n , keytype S [ ]) { const int h = n/2 , m = n – h; keytype U [1…h],V [1..m]; if (n >1) { copy S[1] through S[h] to U[h]; copy S [h + 1] through S[h] to V[1] through V[m]; mergesort(h, U); mergesort(m,V); merge (h , m , U,V,S); } }

اسلاید ۴۱: الگوریتم۳-۲: ادغام void merg ( int h , int m, const keytype U[ ], const keytype V[ ], keytype S[ ] ) { index i , j , k; i = 1; j = 1 ; k = 1; while (i <= h && j <= m) { if (U [i] < V [j]) { S [k] = U [i] i+ + ;

اسلاید ۴۲: } else { S [k] = V [j]; j+ +; } k+ +; } if ( i > h) copy V [j] through V [m] to S [k] through S [ h + m ] else copy U [i] through U [h] to S [k] through S [ h + m ] }

اسلاید ۴۳: تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم ۳-۲(ادغام) عمل اصلی: مقایسهU [i] با . V[j] اندازه ورودی:h وm ،تعداد عناصر موجود در هر یک از دو آرایه ورودی.W ( h , m) = h + m – 1

اسلاید ۴۴: تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم ۲-۲( مرتب سازی ادغامی)عمل اصلی: مقایسه ای که درادغام صورت می پذیرد. اندازه ورودی: n ، تعداد عناصر آرایه S. W (n) = W (h) + W ( m) + h + m – ۱ زمان لازم برای ادغام زمان لازم برای مرتب سازی V زمان لازم برای مرتب سازی U برای n >1 که n توانی از ۲ است W (n) = 2 W( n / 2) + n -1 W (1) = 0W( n ) ( n lg n)

اسلاید ۴۵: الگوریتم۴-۲: مرتب سازی ادغامی ۲(mergesort 2 )void mergesort2 (index low, index high) { index mid; if (low < high) { mid = ( low + high) / 2 ; mergesort 2 (low, mid); mergesort 2 (mid +1, high); merge2(low,mid,high) } }

اسلاید ۴۶: الگوریتم۵-۲:ادغام۲ مسئله: ادغام دو آرایه ی مرتب S که درmergesort ایجاد شده اند. void mrge2 (index low, index mid, index high) { index i, j , k; keytype U [ low..high] i = low; j = mid +1 ; k = low; while ( i <= mid && j <= high) { if ( S [i] < S [j] ) { U [k] = S [i]; i + + ; }

اسلاید ۴۷: else { U [k] = S [j] j ++; } k ++; } if ( i > mid ) move S [j] through S [high] to U [k] through U [high] else move S [i] through S [mid] to U [k] through U [high] move U [low] through U [high] to S [low] through S [high] }

اسلاید ۴۸: ۳-۲روش تقسیم و حل راهبرد طراحی تقسیم و حل شامل مراحل زیر است:۱- تقسیم نمونه ای ازیک مسئله به یک یا چند نمونه کوچکتر.۲- حل هر نمونه کوچکتر. اگر نمونه های کوچک تر به قدر کوچک تر به قدر کافی کوچک نبودند، برای این منظور از بازگشت استفاده کنید.۳- در صورت نیاز، حل نمونه های کوچک تر را ترکیب کنید تا حل نمونه اولیه به دست آید.

اسلاید ۴۹: ۴-۲ مرتب سازی سریع (quicksort)در مرتب سازی سریع، ترتیب آنها از چگونگی افراز آرایه ها ناشی می شود.همه عناصر کوچک تر آز عنصر محوری در طرف چپ آن وهمه عناصربزرگ تر، درطرف راست آن واقع هستند.

اسلاید ۵۰: مرتب سازی سریع، به طور بازگشتی فراخوانی می شود تا هر یک از دوآرایه را مرتب کند، آن ها نیز افراز می شوند واین روال ادامه می یابد تا به آرایه ای با یک عنصربرسیم. چنین آرایه ای ذاتاً مرتب است.

اسلاید ۵۱: الگوریتم۶-۲ :مرتب سازی سریع مسئله: مرتب سازی n کلید با ترتیب غیر نزولی. void quicksort (index low , index high) { index pivotpoint; if ( high > low) { partition (low , high , pivotpoint) quicksort (low , pivotpoint – ۱) quicksort (pivotpoint + 1 , high); } }

اسلاید ۵۲: الگوریتم۷-۲: افراز آرایه مسئله: افراز آرایه S برای مرتب سازی سریع. void partition (index low, index high) index & pivotpoint) { index i , j; keytype pivotitem; pivotitem = S [low]; j = low for ( i = low +1 ; i <= high; i ++)

اسلاید ۵۳: if ( S [i] < pivotitem ) { j++; exchange S [i] and S [j]; } pivotpoint = j; exchange S [low] and S [ pivotpoint];}

اسلاید ۵۴: تحلیل پیچیدگی زمانی در حالت معمول برای الگوریتم ۷-۲( افراز)عمل اصلی: مقایسهS [i] با pivotitem .اندازه ورودی: n = high – how +1 ، تعداد عناصرموجود در زیر آرایه.T(n) = n – 1

اسلاید ۵۵: تحلیل پیچیدگی زمانی در بدترین حالت برای الگوریتم ۶-۲(مرتب سازی سریع)عمل اصلی: مقایسهS [i] با pivotitem در روال partition .اندازه ورودی: n ، تعداد عناصر موجود درآرایه S. T(n) = T(0) + T( n – ۱) + n – ۱ زمان لازم برای افراز زمان لازم برای مرتب سازی زمان لازم برای مرتب سازی زیرآرایه طرف راست زیر آرایه طرف چپ

اسلاید ۵۶: به ازای n > 0 T (n) = T (n – ۱) + n – ۱ T (0) = 0W (n) = n (n – ۱) / ۲ (n²)

اسلاید ۵۷: تحلیل پیچیدگی زمانی در حالت میانگین برای الگوریتم ۶-۲(مرتب سازی سریع)عمل اصلی: مقایسهS [i] با pivotitem در partition .اندازه ورودی: n ، تعداد عناصر موجود در S. A (n) (n lg n)

اسلاید ۵۸: ۵-۲الگوریتم ضرب ماتریس استراسنپیچیدگی این الگوریتم از لحاظ ضرب، جمع و تفریق بهتر از پیچیدگی درجه سوم است.روش استراسن در مورد ضرب ماتریس های ۲×۲ ارزش چندانی ندارد.

اسلاید ۵۹: الگوریتم ۸-۲: استراسنمسئله : تعیین حاصلضرب دو ماتریس n ×n که در آن n توانی از ۲ است. void starssen ( int n n × n _ matrix A, n × n _ matrix B, n × n _ matrix & C) { if ( n <= threshold) compute C = A × B using the standard algorithm;

اسلاید ۶۰: else { partition A into four submatrics A11, A12 , A21,A22; partition B into four submatrics B11, B12 , B21,B22; compute C = A × B using Starssen’s Method; } }

اسلاید ۶۱: تحلیل پیچیدگی زمانی تعداد ضرب ها در الگوریتم ۸-۲(استرسن)در حالت معمول عمل اصلی: یک ضرب ساده. اندازه ورودی:n ، تعداد سطرها و ستون ها در ماتریس. به ازای n > 1 که n توانی از ۲است T (n) = 7 T (n / 2) T (1) = 1 T (n) ( n ^2.81)

اسلاید ۶۲: تحلیل پیچیدگی زمانی تعدادجمع هاو تفریقهای الگوریتم (استرسن)درحالت معمولعمل اصلی: یک جمع یا تفریق ساده. اندازه ورودی:n ، تعداد سطرها و ستون ها در ماتریس.به ازای n > 1 که n توانی از ۲است۱۸ (n/2)² +(T (n) = 7T(n/2 T ( 1 ) = 1 T ( n ) ( n ^ 2.81)

اسلاید ۶۳: الگوریتم۹-۲: ضرب اعداد صحیح بزرگ مسئله: ضرب دو عدد صحیح بزرگ u و v large _ integer prod ( large_integer u, large_integer v) { large_inreger x , y , w , z ; int n , m ; n = maximum(number of digits in u,number of digits in v) if (u = = 0 || v = = 0) return 0 ;

اسلاید ۶۴: else if (n < = threshold) return u × v obtained in the usual way; else { m = n / 2 ; x = u divide 10 ^ m ; y = rem 10 ^ m; w = v divide 10 ^ m ; z = rem 10 ^ m; return prod (x ,w) × ۱۰ ^۲m + ( prod ( x, z) + prod (w, y )) × ۱۰ ^ m + prod ( y, z); } }

اسلاید ۶۵: تحلیل پیچیدگی زمانی در بدترین حالت برای ا لگوریتم۹-۲( ضرب اعداد صحیح) عمل اصلی: دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در هنگام جمع کردن ، تفریق کردن، یا انجام اعمالdivide 10 ^ m ، rem 10 ^m یا ×۱۰ ^ m. هر یک از این اعمال را m بار انجام می دهد.اندازه ورودی: n ، تعداد ارقام هر یک از دو عدد صحیح. به ازای n > s که n توانی از ۲استW ( n ) = 4 W (n / 2) + cn W ( s ) = 0 W ( n ) ( n² )

اسلاید ۶۶: الگوریتم ۱۰-۲: ضرب اعداد صحیح بزرگ ۲ large_integer prod2 (large_integer u , large_ integer v) { large_integer x , y , w , z , r , p , q; int n , m; n = maximum (number of digits in u,number of digits in v); if (u = = 0 || v = = 0) return 0 ; else if (n < = threshold) return u × v obtained in the usual way;

اسلاید ۶۷: else { m = n / 2 ; x = u divide 10 ^ m ; y = rem 10 ^ m; w = v divide 10 ^ m ; z = rem 10 ^ m; r = prod2 (x + y, w + z ); p = prod2 ( x , w ) q = prod2 ( y , z ); return p ×۱۰ ^ ۲m + ( r – p – q ) × ۱۰ ^ m +q ; } }

اسلاید ۶۸: تحلیل پیچیدگی زمانی در بدترین حالت برای الگوریتم۱۰-۲( ضرب اعداد صحیح۲)عمل اصلی: دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در هنگام جمع کردن ، تفریق کردن، یا انجام اعمالdivide 10 ^ m ، rem 10 ^m یا ×۱۰ ^ m. هر یک از این اعمال را m بار انجام می دهد.اندازه ورودی: n ، تعداد ارقام هر یک از دو عدد صحیح.به ازای n > s که n توانی از ۲است۳W(n/2)+ c n <=W (n) <= 3W (n / 2 +1) + c n W (s) = 0W (n) = (n ^ 1.58)

اسلاید ۶۹: فصل سوم: برنامه نویسی پویا

اسلاید ۷۰: برنامه نویسی پویا، از این لحاظ که نمونه به نمونه های کوچکتر تقسیم می شود ، مشابه روش تقسیم و حل است ولی در این روش ، نخست نمونه های کوچک تر را حل می کنیم ، نتایج را ذخیره می کنیم و بعدا هر گاه به یکی از آن ها نیاز پیدا شد، به جای محاسبه دوباره کافی است آن را بازیابی کنیم.

اسلاید ۷۱: مراحل بسط یک الگوریتم برنامه نویسی پویا به شرح زیر است: ۱- ارائه یک ویژگی بازگشتی برای حل نمونه ای از مسئله . ۲- حل نمونه ای از مسئله به شیوه جزء به کل با حل نمونه های کوچک تر.

اسلاید ۷۲: الگوریتم ۳-۱: ضریب دو جمله ای با استفاده از تقسیم و حل int bin ( int n , int k) { if ( k == 0 || n ==k ) return 1 ; else return bin (n – ۱ , k -1 ) + bin ( n-1 , k); }

اسلاید ۷۳: الگوریتم ۲-۳: ضریب دو جمله ای با استفاده از برنامه نویسی پویا int bin2 ( int n , int k ) { index i , j ; int B [0..n][0..k] for ( i = 0; i n ; i ++) if ( j == 0 || j == i ) B [i] [j] = 1; else B [i] [j] = B [ i – ۱ ] [ j -1 ] + B [ i -1 ] [j]; return B[n] [k]:}

اسلاید ۷۴: الگوریتم ۳-۳: الگوریتم فلوید برای یافتن کوتاه ترین مسیر void floyd ( int n const number W [][], number D [][], { index i , j , k ; D = W ; for ( k = 1 ; k n ; k ++) for ( i = 1; i n ; i++) for ( j = 1 ; j n ; j ++) D [i] [j] = minimum ( D [i][j], D[i][k] + D[k][j]); }

اسلاید ۷۵: تحلیل پیچیدگی زمانی در بدترین حالت برای ا لگوریتم۳-۳ (الگوریتم فلوید برای یافتن کوتاهترین مسیر)عمل اصلی: دستورهای موجود در حلقه for .اندازه ورودی:n ، تعداد رئوس گراف.T (n) = n × n × n = n³ (n³)

اسلاید ۷۶: الگوریتم ۴-۳:الگوریتم فلوید برای یافتن کوتاهترین مسیر ۲ void floyd2 ( int n, const number W [][], number D [][], index P [][]) { index i , j , k ; for ( i = 1 ; i n ; i ++) for ( j = 1 ; j n ; j++)

اسلاید ۷۷: P [i] [j] = 0; D = W; for ( k = 1 ; k <= n ; k ++) for ( i = 1 ; i <= n ; i ++) for ( j = 1 ; j <= n ; j ++) if ( D [i] [k] + D [k] [j] < D [i] [j] ) { P [i] [j] = k; D [i] [j] = D [i] [k] + D [k] [j]; } }

اسلاید ۷۸: الگوریتم ۵-۳:چاپ کوتاهترین مسیرمسئله: چاپ رئوس واسطه روی کوتاه ترین مسیر از راسی به راس دیگر در یک گراف موزون. void path ( index q , r) { if (P [q] [r] != 0 ) { path (q , P [q] [r] ); cout << “v” << P [q] [r]; path (P [q] [r] , r ); } }

اسلاید ۷۹: ۳-۳ برنامه نویسی پویا و مسائل بهینه سازیحل بهینه ، سومین مرحله از بسط یک الگوریتم برنامه نویسی پویا برای مسائل بهینه سازی است. مراحل بسط چنین الگوریتمی به شرح زیر است:

اسلاید ۸۰: ۱- ارائه یک ویژگی بازگشتی که حل بهینه ی نمونه ای از مسئله را به دست می دهد. ۲- محاسبه مقدار حل بهینه به شیوه ی جزء به کل. ۳- بنا کردن یک حل نمونه به شیوه ی جزء به کل.