درس طراحی الگوریتم ها

درس طراحی الگوریتم ها

اسلاید 1: درس طراحی الگوریتم ها (با شبه کد های c ++) تعداد واحد: 3 تهیه کننده : جعفر پورامینیمنبع : کتاب طراحی الگوریتمهامترجم : جعفر نژاد قمی

اسلاید 2: فصل اول: کارایی ، تحلیل و مرتبه الگوریتم ها

اسلاید 3: این کتاب در باره تکنیک های مربوط به حل مسائل است.تکنیک ، روش مورد استفاده در حل مسائل است.مسئله ، پرسشی است که به دنبال پاسخ آن هستیم.

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

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

اسلاید 6: الگوریتم 1-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 ;

اسلاید 7: الگوریتم 2-1:محاسبه مجموع عناصر آرایه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;}

اسلاید 8: الگوریتم 3-1:مرتب سازی تعویضیمسئله: 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];}

اسلاید 9: الگوریتم 4-1:ضرب ماتریس ها 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;

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

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

اسلاید 12: الگوریتم 1-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 ;

اسلاید 13: الگوریتم 5-1: جست و جوی دودویی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⌡;

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

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

اسلاید 16: الگوریتم 7-1:جمله 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]; }

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

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

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

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

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

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

اسلاید 23: 4-1مرتبه الگوریتمالگوریتم ها یی با پیچیدگی زمانی ازقبیل n و100n را الگوریتم های زمانی خطی می گویند.مجموعه کامل توابع پیچیدگی را که با توابع درجه دوم محض قابل دسته بندی باشند، n²) ( θ می گویند.

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

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

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

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

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

اسلاید 29: ویژگی های مرتبه1- 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ⁿ)

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

اسلاید 31: 7- ترتیب دسته های پیچیدگی زیر را در نظربگیرید: θ (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))

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

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

اسلاید 34: هنگام پی ریزی یک الگوریتم بازگشتی ، باید:1- راهی برای به دست آوردن حل یک نمونه از روی حل یک نمونه ازروی حل یک یا چند نمونه کوچک تر طراحی کنیم.2- شرط(شرایط ) نهایی نزدیک شدن به نمونه(های) کوچک تر را تعیین کنیم.3- حل را در حالت شرط (شرایط)نهایی تعیین کنیم.

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

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

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

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

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

اسلاید 40: الگوریتم2-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); } }

اسلاید 41: الگوریتم3-2: ادغام 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+ + ;

اسلاید 42: } 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 ] }

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

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

اسلاید 45: الگوریتم4-2: مرتب سازی ادغامی 2(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) } }

اسلاید 46: الگوریتم5-2:ادغام2 مسئله: ادغام دو آرایه ی مرتب 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 + + ; }

اسلاید 47: 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] }

اسلاید 48: 3-2روش تقسیم و حل راهبرد طراحی تقسیم و حل شامل مراحل زیر است:1- تقسیم نمونه ای ازیک مسئله به یک یا چند نمونه کوچکتر.2- حل هر نمونه کوچکتر. اگر نمونه های کوچک تر به قدر کوچک تر به قدر کافی کوچک نبودند، برای این منظور از بازگشت استفاده کنید.3- در صورت نیاز، حل نمونه های کوچک تر را ترکیب کنید تا حل نمونه اولیه به دست آید.

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

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

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

اسلاید 52: الگوریتم7-2: افراز آرایه مسئله: افراز آرایه 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 ++)

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

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

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

اسلاید 56: به ازای n > 0 T (n) = T (n – 1) + n – 1 T (0) = 0W (n) = n (n – 1) / 2 Є θ (n²)

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

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

اسلاید 59: الگوریتم 8-2: استراسنمسئله : تعیین حاصلضرب دو ماتریس n ×n که در آن n توانی از 2 است. 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;

اسلاید 60: 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; } }

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

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

اسلاید 63: الگوریتم9-2: ضرب اعداد صحیح بزرگ مسئله: ضرب دو عدد صحیح بزرگ 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 ;

اسلاید 64: 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) × 10 ^2m + ( prod ( x, z) + prod (w, y )) × 10 ^ m + prod ( y, z); } }

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

اسلاید 66: الگوریتم 10-2: ضرب اعداد صحیح بزرگ 2 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;

اسلاید 67: 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 ×10 ^ 2m + ( r – p – q ) × 10 ^ m +q ; } }

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

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

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

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

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

اسلاید 73: الگوریتم 2-3: ضریب دو جمله ای با استفاده از برنامه نویسی پویا 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 – 1 ] [ j -1 ] + B [ i -1 ] [j]; return B[n] [k]:}

اسلاید 74: الگوریتم 3-3: الگوریتم فلوید برای یافتن کوتاه ترین مسیر 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]); }

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

اسلاید 76: الگوریتم 4-3:الگوریتم فلوید برای یافتن کوتاهترین مسیر 2 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++)

اسلاید 77: 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]; } }

اسلاید 78: الگوریتم 5-3:چاپ کوتاهترین مسیرمسئله: چاپ رئوس واسطه روی کوتاه ترین مسیر از راسی به راس دیگر در یک گراف موزون. 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 ); } }

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

اسلاید 80: 1- ارائه یک ویژگی بازگشتی که حل بهینه ی نمونه ای از مسئله را به دست می دهد. 2- محاسبه مقدار حل بهینه به شیوه ی جزء به کل. 3- بنا کردن یک حل نمونه به شیوه ی جزء به کل.

اسلاید 81: هر مسئله بهینه سازی را نمی توان با استفاده از برنامه نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله صدق کند.اصل بهینگی در یک مسئله صدق می کند اگریک حل بهینه برای نمونه ای از مسئله ، همواره حاوی حل بهینه برای همه ی زیر نمونه ها باشد.

اسلاید 82: 4-3 ضرب زنجیره ای ماتریس ها هدف بسط الگوریتمی است که ترتیب بهینه را برای n ماتریس معین کند.ترتیب بهینه فقط به ابعاد ماتریس ها بستگی دارد.علاوه بر n ، این ابعاد تنها ورودی های الگوریتم هستند.این الگوریتم حداقل به صورت نمایی است.

اسلاید 83: الگوریتم 6-3: حداقل ضرب ها int minimult ( int n, const int d [], index P [][] ) { index i , j , k , diagonal; int M [1..n] [1..n]; for ( i = 1 ; i ≤ n ; i ++) M [i] [i] = 0:

اسلاید 84: for (diagonal = 1; diagonal ≤ n -1 ; diagonal ++) for ( i = 1 ; i ≤ n – diagonal ; i ++) { j = i + diagonal ; M[i][j] = minimum (M[i][k] + M[k +1 ][j] + d [ i – 1] * d [k] * d [j]); P [i][j] = a value of k that gave the minimum; } return M[1][n]; }

اسلاید 85: تحلیل پیچیدگی زمانی حالت معمول برای ا لگوریتم6-3( حداقل ضرب ها) عمل اصلی: می توان دستورات اجرا شده برای هر مقدار k را عمل اصلی در نظر بگیریم. مقایسه ای را که برای آزمون حداقل انجام می شود، به عنوان عمل اصلی در نظر می گیریم. اندازه ورودی: n ، تعداد ماتریس ها که باید ضرب شوند.N (n -1) (n + 1) / 6 Є θ (n³)

اسلاید 86: الگوریتم 7-3: چاپ ترتیب بهینه مسئله: چاپ ترتیب بهینه برای ضرب n ماتریس. void order ( index i, index j) { if ( i == j) cout << “A” << i ; else { k = P [i] [j]; cout << “(“; order ( i , k); order ( k +1 , j ); cout << “)”; } }

اسلاید 87: 5-3 درخت های جست و جوی دودویی بهینهدرخت جست و جوی دودویی یک دودویی از عناصر( که معمولا کلید نامیده می شوند)است که از یک مجموعه مرتب حاصل می شود، به قسمی که: 1- هر گره حاوی یک کلید است.

اسلاید 88: 2- کلید های موجود در زیردرخت چپ یک گره مفروض، کوچک تر یا مساوی کلید آن گره هستند.3- کلیدهای موجود درزیردرخت راست یک گره مفروض، بزرگ تر یا مساوی کلید آن گره هستند.

اسلاید 89: الگوریتم 8-3: درخت جست و جوی دودویی void search ( node _ pointer tree , keytype keyin, node _ poiner & p) { bool found ; p = tree; found = false; while (! found)

اسلاید 90: if ( p - > key == keyin ) found = true ; else if ( keyin < p - > key ) p = p -> left ; else p = p - > right ; }

اسلاید 91: الگوریتم 9-3 : درخت جست و جوی بهینه مسئله: تعیین یک درخت جست وجوی بهینه برای مجموعه ای از کلید ها، هر یک با احتمالی مشخص. void optsearchtree ( int n , const float p[]; float & minavg, index R[][]) { index i , j , k , diagonal ;

اسلاید 92: float A [1..n + 1] [0..n]; for ( i = 1 ; i ≤ n ; i ++) { A [i] [i -1] = 0 A [i] [i] = p [i]; R [i] [i] = i ; R [i] [ i – 1 ] = 0; } A[ n + 1 ] [n] = 0 ; R[ n + 1 ] [n] = 0 ;

اسلاید 93: for (diagonal = 1;diagonal ≤ n – 1; diagonal++) for ( i = 1; i ≤ n – diagonal ; i ++) { j = i + diagonal ; A[i][j] = minimum(A[i][k-1]+A[k+1][j])+∑pm R[i][j] = a value of k that gave the minimum; } minavg = A [1][n]; }

اسلاید 94: تحلیل پیچیدگی زمانی حالت معمول برای ا لگوریتم درخت جستجوی دودویی بهینه عمل اصلی: دستورات اجرا شده به ازای هر مقدار از k .این دستورات شامل یک مقایسه برای آزمون حداقل است. اندازه ورودی: n ، تعداد کلید.T(n) = n ( n -1) ( n + 4 ) / 6 Є θ ( n³ )

اسلاید 95: الگوریتم 10 -3: ساخت درخت جست و جوی دودویی بهینه node _ pointer tree ( index i , j ) { index k ; node _ pointer p ; k = R [i] [j]; if ( k == 0 ) return NULL; else {

اسلاید 96: p = new nodetype ; p - > key = key [k] ; p - > left = tree (i , k – 1); p - > right = tree ( k+1 , j); return P; } }

اسلاید 97: الگوریتم11-3:الگوریتم برنامه نویسی پویا برای مسئله فروشنده دوره گرد void tarvel ( int , n const number W[ ][ ] , index P[ ] [ ] , number & minlength) { index i , j , k ; number D[1..n][subset of V - { v1 } ] ; for ( i = 2 ; i ≤ n ; i ++)

اسلاید 98: D[i] [Ø] = W [i] [1] ; for (k = 1 ; k ≤ n - 2 ; k ++) for (all subsets A Ç V – { v1 } containing k vertices) for (i such that i != 1 and vi is not inA){ D[i] [A] = minimum ( W [i] [j] + D [j] [A – {vj}]); P [i] [A] = value of j that gave the minimum;

اسلاید 99: D [1] [ V – { v1 } ] = minimum ( W [1] [j] + D [j] [ V – { v1 – v j } ] ); P [1] [ V – { v1 } ] = value of j that gave the minimum; minlength = D [1] [ V – { v1 } ]; }

اسلاید 100: تحلیل پیچیدگی فضا و زمان در حالت معمول برای ا لگوریتم 11-3 ( الگوریتم برنامه نویسی پویا برای مسئله فروشنده دوره گرد) عمل اصلی: زمان در هر دو حلقه ی اول و آخر ، در مقایسه با زمان در حلقه میانی چشمگیر نیست، زیرا حلقه میانی حاوی سطوح گوناگون تودر تویی است . دستورات اجرا شده برای هر مقدار v j را می توان عمل اصلی در نظر گرفت. اندازه ورودی : n ، تعداد رئوس موجود در گراف.T (n) = n 2ⁿ Є θ ( n 2ⁿ )

اسلاید 101: فصل چهارم:روش حریصانه در طراحی الگوریتم

اسلاید 102: الگوریتم حریصانه ، به ترتیب عناصر را گرفته ، هر بار آن عنصری را که طبق ملاکی معین ”بهترین“ به نظر می رسد، بدون توجه به انتخاب هایی که قبلا انجام داده یا در آینده انجام خواهد داد، بر می دارد.

اسلاید 103: الگوریتم حریصانه ، همانند برنامه نویسی پویا غالبا برای حل مسائل بهینه سازی به کار می روند، ولی روش حریصانه صراحت بیشتری دارد.در روش حریصانه ، تقسیم به نمونه های کوچک تر صورت نمی پذیرد.

اسلاید 104: الگوریتم حریصانه با انجام یک سری انتخاب، که هر یک در لحظه ای خاص ،بهترین به نظر می رسد عمل می کند، یعنی انتخاب در جای خود بهینه است.امید این است که یک حل بهینه سرتاسری یافت شود، ولی همواره چنین نیست.برای یک الگوریتم مفروض باید تعیین کرد که آیا حل همواره بهینه است یا خیر.

اسلاید 105: الگوریتم حریصانه ، کار را با یک مجموعه تهی آغاز کرده به ترتیب عناصری به مجموعه اضافه می کند تا این مجموعه حلی برای نمونه ای از یک مسئله را نشان دهد. هر دور تکرار ، شامل مولفه های زیر است:

اسلاید 106: 1- روال انتخاب، عنصربعدی را که باید به مجموعه اضافه شود،انتخاب می کند.انتخاب طبق یک ملاک حریصانه است.2- بررسی امکان سنجی ، تعیین می کند که آیا مجموعه جدید برای رسیدن به حل،عملی است یا خیر. 3- بررسی راه حل ، تعیین می کند که آیا مجموعه جدید ، حل نمونه را ارائه می کند یا خیر.

اسلاید 107: 1-4 درخت های پو شای کمینهفرض کنید طراح شهری می خواهد چند شهر معین را با جاده به هم وصل کند، به قسمی که مردم بتوانند از هر شهر به شهر دیگر بروند. اگر محدودیت بودجه ای در کار باشد ، ممکن است طراح بخواهد این کار را با حداقل مقدار جاده کشی انجام دهد.برای این مسئله دو الگوریتم حریصانه متفاوت : پریم و کروسکال بررسی می شود.

اسلاید 108: هر یک از این الگوریتم ها از یک ویژگی بهینه محلی استفاده می کند.تضمینی وجود ندارد که یک الگوریتم حریصانه همواره حل بهینه بدهد، ثابت می شود که الگوریتم های کروسکال و پریم همواره درخت های پوشای کمینه را ایجاد می کنند.

اسلاید 109: 1-1-4الگوریتم پریمالگوریتم پریم با زیر مجموعه ای تهی از یال های F و زیرمجموعه ای از رئوس Y آغاز می شود، زیرمجموعه حاوی یک راس دلخواه است. به عنوان مقداراولیه، {v1} را به Y می دهیم . نزدیک ترین را س به Y ، راسی در V – Y است که توسط یالی با وزن کمینه به راسی در Y متصل است.

اسلاید 110: الگوریتم 1-4: الگوریتم پریم void prim ( int n, const number W[ ] [ ], set_ of_edges & F ) { index i , vnear; number min; edge e; index nearest [2..n];

اسلاید 111: number distance [2..n]; F = Ø ; for ( i = 2 ; i ≤ n ; i ++) { narest [i] = 1 ; distance [i] = W [1] [i] ; } repeat ( n-1 times ) { min = ∞ ; for ( i = 2 ; i < = n ; i ++) if ( 0 ≤ distance [i] < min ) {

اسلاید 112: min = distance [i] ; vnear = i ; } e = edge connecting vertices indexed by near and nearest [ vnear ] ; add e to F ; distance [ vnear ] = -1 ; for ( i = 2 ; i ≤ n ; i ++)

اسلاید 113: if ( W[i] [ vnear ] < distance [i]) { distance [i] = W [i] [ vnear ] ; nearest [i] = vnear ; } } }

اسلاید 114: تحلیل پیچیدگی زمانی در حالت معمول برای ا لگوریتم 1-4(الگوریتم پریم) عمل اصلی: در حلقه repeat دو حلقه وجود دارد که هر یک (n – 1 ) بار تکرار می شود . اجرای دستورات داخل هر یک از آن ها را می توان به عنوان یک بار اجرای عمل اصل در نظر گرفت. اندازه ورودی: n ، تعداد رئوس.T (n) = 2 ( n – 1) ( n – 1) Є θ ( n²)

اسلاید 115: قضیه 1-4الگوریتم پریم همواره یک درخت پوشای کمینه تولید می کند. اثبات : برای آ ن که نشان دهیم مجموعه F پس از هر بار تکرارحلقه repeat، امید بخش است ازاستقرا استفاده می کنیم. مبنای استقرا : واضح است که مجموعه Ø امید بخش است.

اسلاید 116: الگوریتم 4-2: الگوریتم کروسکال void kruskal ( int n , int m, set _ of _ edges E, set _ of _edges & F ) { index i , j ; set _pointer p , q; edge e ; sort the m edges in E by weight in

اسلاید 117: nondecreasing order; F = Ø ; intitial (n) ; while( number of edges in F is less than n-1){ e = edge with least weight not yet considered ; i , j = indices of vertices connected by e; p = find (i) ; q = find (i) ;

اسلاید 118: if (! equal ( p, q )) { merge ( p , q ) ; add e to F ; } } }

اسلاید 119: تحلیل پیچیدگی زمانی در بدترین حالت برای ا لگوریتم 2-4(الگوریتم کروسکال) عمل اصلی: یک دستور مقایسه. اندازه ورودی : n ، تعداد رئوس و m تعداد یال ها. درباره این الگوریتم سه نکته را باید در نظر داشت: 1- زمان لازم برای مرتب سازی یال ها .W (m) Є θ ( m lg m)

اسلاید 120: 2- زمان در حلقه while .W (m) Є θ ( m lg m) 3- زمان لازم برا ی مقدار دهی اولیه به n مجموعه متمایز.W ( m, n ) Є θ( m lg m) در نتیجه ، بدترین حالت:( n² lg n² ) = θ ( n²lg n ) W ( m, n ) Є θ

اسلاید 121: قضیه 2-4الگوریتم کروسکال همواره یک درخت پوشای کمینه تولید می کند. اثبات : اثبات از طریق استقرا با شروع از مجموعه ای تهی از یال ها آغاز می شود.

اسلاید 122: 2-4 الگوریتم دیکسترا برای کوتاهترین مسیر تک مبدابرای کوتاهترین مسیر از هر راس به همه رئوس دیگر در یک گراف موزون و بدون جهت یک الگوریتم(θ(n² از روش حریصانه داریم، که آن دیکسترا نام دارد.

اسلاید 123: الگوریتم را با این فرض ارائه می دهیم که از راس مورد نظر به هر یک از رئوس دیگر، مسیری وجود دارد.این الگوریتم مشابه الگوریتم پریم برای مسئله درخت پوشای کمینه است.

اسلاید 124: الگوریتم3-4: الگوریتم دیکسترا void dijkstra ( int n, const number W[ ] [ ], set _ of _ edges & F) { index i , vnear, edge e ; index touch [2..n]; number length[2..n];

اسلاید 125: F = Ø ; for ( i = 2; i ≤ n ; i ++ ) { touch [i] = 1 ; length [i] = W [1][i]; } repeat ( n – 1 times ) { min = ∞ ; for ( i = 2 ; i ≤ n ; i ++) if ( 0 <= length [i] < min ) { min = length [i] ;

اسلاید 126: vnear = i ; } e = edge from vertix indexed by touch [vnear] to vertex indexed by vnear; add e to F; for ( i = 2 ; i ≤ n; i ++) if ( length [vnear] + W [vnear] [i] < length[i]) { length [i] = length [vnear] + W [vnear] [i];

اسلاید 127: touch [i] = vnear ; } length [vnear] = -1; } }

اسلاید 128: قضیه 3-4 تنها زمان بندی که زمان کل درسیستم را کمینه سازی می کند، زمان بندی است که در آن کارها بر حسب افزایش زمان ارائه خدمات مرتب می شوند.

اسلاید 129: الگوریتم 4-4 : زمان بندی با مهلت معین مسئله : تعیین زمان بندی با سود کل بیشینه ، با این فرض که هر کاری دارای سود است و فقط وقتی قابل حصول است که آن کار در مهلت مقررش انجام شود. void schedule ( int n , const int deadline [ ] , sequence _ of _ integer& j ) { index i ;

اسلاید 130: sequence_ of_integer K ; j = [1]; for ( i = 2 ; i ≤ n ; i ++) { K = J with i added according to nondecreasing values of deadline [i]; if ( K is feasible) J = K; } }

اسلاید 131: تحلیل پیچیدگی زمانی در بدترین حالت برای ا لگوریتم زمان بندی با مهلت معین عمل اصلی: باید برای مرتب سازی کارها، مقایسه هایی انجام پذیرد و هنگامی که K با J (پس از افزوده شدن کار i ام ) مساوی قرار داده می شود،به مقایسه های بیشتری نیاز داریم و هنگامی که امکان پذیر بودن K چک می شود، به مقا یسه های بیشتری نیاز است. عمل اصلی مقایسه است. اندازه ورودی : n ، تعداد کارها. W (n) Є θ (n²)

اسلاید 132: قضیه 4-4 الگوریتم 4-4 ( زمان بندی با مهلت معین ) همواره یک مجموعه بهینه تولید می کند.اثبات: ازطریق استقرا روی تعداد کارها،n،صورت می پذیرد.مبنای استقرا: اگر یک کار داشته باشیم ، قضیه بر قراراست.

اسلاید 133: قضیه 5-4 الگوریتم هافمن یک کد دودویی بهینه تولید می کند.اثبات : ازطریق استقرا صورت می گیرد. با این فرض که درخت های به دست آمده درمرحله i، انشعاب هایی در درخت دودویی متناظر با کد بهینه اند، نشان می دهیم که درخت های بدست آمده در مرحله (( i + 1 نیز انشعاب هایی در درخت دودویی متناظر با یک کد بهینه اند.

اسلاید 134: فصل پنجم:راهبرد عقبگرد

اسلاید 135: از تکنیک عقبگرد برای حل مسائلی استفاده می شود که در آن ها دنباله ای از اشیاء از یک مجموعه مشخص انتخاب می شود، به طوری که این دنباله ، ملا کی را در بر می گیرد.یک مثال کلاسیک از عقبگرد، مسئله n وزیر است.

اسلاید 136: هدف از مسئله n وزیر ، چیدن n مهره وزیر در یک صفحه شطرنج است ، به طوری که هیچ دو وزیری یکدیگر را گارد ندهند. یعنی هیچ دو مهره ای نباید در یک سطر، ستون یا قطر یکسان باشند.

اسلاید 137: عقبگرد حالت اصلاح شده ی جست و جوی عمقی یک درخت است.الگوریتم عقبگرد همانند جست و جوی عمقی است، با این تفاوت که فرزندان یک گره فقط هنگامی ملاقات می شوند که گره امید بخش باشدو در آن گره حلی وجود نداشته باشد.

اسلاید 138: الگوریتم 1-5: الگوریتم عقبگرد برای مسئله n وزیر void queens ( index i) { index j; if ( promising(i)) if ( i == n) cout << col [1] through col [n]; else for ( j = 1 ; j ≤ n ; j++ ) {

اسلاید 139: col [ i +1 ] = j; queens ( i + 1); }}bool promising ( index i ){ index k ; bool switch; k = 1; switch = true ;

اسلاید 140: while ( k < i && switch ) { if (col [i] == col[k] || abs(col[i] – col[k] == i-k) switch = false; k++; } return switch; }

اسلاید 141: 5-3 استفاده از الگوریتم مونت کارلو برای برآورد کردن کارایی یک الگوریتم عقبگردالگوریتم های مونت کارلو ، احتمالی هستند،یعنی دستور اجرایی بعدی گاه به طور تصادفی تعیین می شوند. در الگوریتم قطعی چنین چیزی رخ نمی دهد.همه ی الگوریتم هایی که تا کنون بحث شدند، قطعی هستند.

اسلاید 142: الگوریتم مونت کارلو مقدار مورد انتظار یک متغیر تصادفی را که روی یک فضای ساده تعریف می ود ، با استفاده از مقدار میانگین آن روی نمونه تصادفی از فضای ساده بر آورد می کند.

اسلاید 143: تضمینی وجود ندارد که این برآورد به مقدار مورد انتظار واقعی نزدیک باشد، ولی احتمال نزدیک شدن آن، با افزایش زمان در دسترس برای الگوریتم، افزایش می یابد.

اسلاید 144: الگوریتم2-5 : برآورد مونت کارلو int estimate () { node v ; int m, mprod , numnodes; v = root of state space tree; numnodes = 1; m = 1; mprod = 1;

اسلاید 145: while ( m != 0) { t = number of children of v ; mprod - mprod * m; numnodes = numnodes + mprod * t; m = number of promising children of v; if ( m != 0) v = randomly selected promising child of v ; } return numnodes; }

اسلاید 146: الگوریتم 3-5: بر آورد مونت کارلو برای الگوریتم 1-5 (الگوریتم عقبگرد برای مسئلهn وزیر) int ostimate _ n_ queens (int n) { index i , j , col [1..n]; int m , mprod , numnodes ; set _of_ index prom _children; i = 0; numnodes =1 ; m = 1;

اسلاید 147: mprod = 1 ; while ( m != 0 && i != n ) { mprod = mprod * m ; numnodes = numnodes + mprod * n; i ++; m = 0 ; prom_childern = Ø; for ( j = 1 ; j ≤ n ; j++;) { col [i] = j ; if ( promising(i)) {

اسلاید 148: m++; prom_children = prom _ children U {i}; } } if ( m != 0) { j = random selection from prom _ children ; col [i]; } } return numnodes; }

اسلاید 149: الگوریتم 4-5: الگوریتم عقبگرد برای مسئله حاصل جمع زیر مجموعه ها مسئله : تعیین همه ی ترکیبات اعداد صحیح موجود در یک مجموعه n عدد صحیح ، به طوری که حاصل جمع آن ها مساوی مقدار معین W شود. void sum _of _subsets ( index i , int weight , int total) { if (promising(i)) if ( weight == W ) cout << include [1] through include [i]; else {

اسلاید 150: include [i +1] = “yes” ; sum_ of_subsets ( i +1 , weight + w [i +1], total – w [ i + 1 ]); } } bool promising ( index i); { return (weight + total ≥ W) &&( weight == W || weight + w [ i + 1 ] ≤ W ); }

اسلاید 151: 5-5 رنگ آمیزی گرافمسئله رنگ آمیزی m ، عبارت از یافتن همه ی راه ها ی ممکن برای رنگ آمیزی یک گراف بدون جهت ، با استفاده از حداکثر m رنگ متفاوت است، به طوری که هیچ دو راس مجاوری هم رنگ نباشند.

اسلاید 152: الگوریتم5-5: الگوریتم عقبگرد برای مسئله رنگ آمیزی m void m_coloring (index i ) { int color ; if ( promising (i)) if ( i == n) cout << vcolor[1] through vcolor [n]; else for (color = 1; color ≤ m; color ++) {

اسلاید 153: vcolor [ i + 1] = color ; m_coloring (i + 1); } } bool promising ( index i ) { index j ; bool switch ; switch = true;

اسلاید 154: j = 1; while ( j < i && switch ) { if ( W [i] [j] && vcolor [i] == vcolor[j]) switch = false ; j ++; } return switch ; }

اسلاید 155: الگوریتم 6-5: الگوریتم عقبگرد برای مسئله مدارهای ها میلتونی void hamiltonian ( index i ) { index j ; if ( promising (i) if ( i == n - 1) cout << vindex [0] through vindex [ n-1]; else for ( j = 2 ; j ≤ n ; j ++) {

اسلاید 156: vindex [ i +1] = j ; hamiltonian ( i +1 ); } } bool promising ( index i ) { index j ; bool switch ; if( i == n -1 &&! W [vindex [ n-1 ]] [ vindex [0]]) switch = false ;

اسلاید 157: else { switch = true ; j = 1;while ( j < i && switch ) { if (vindex [i] == vindex [j]) switch = false ; j++; } } return switch; }

اسلاید 158: 5-7 مسئله کوله پشتی صفر و یکدر این مسئله مجمو عه ای از قطعات داریم که هر یک دارای وزن و ارزش معین است. اوزان و ارزش ها اعداد مثبتی هستند.

اسلاید 159: دزدی درنظر دارد قطعاتی که می دزدد درون یک کوله پشتی قرار دهد و اگر وزن کل قطعات قرار داده شده در آن کوله پشتی از یک عدد صحیح مثبتW فراتر رود، کوله پشتی پاره می شود.

اسلاید 160: الگوریتم 7-5:الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک void knapsack ( index i , int profit , int weight) { if ( weight ≤ W && profit > maxprofit ) { maxprofit = profit ; numbest = i ; bestset = include; } if ( promising (i)) {

اسلاید 161: include [ i + 1 ] = “yes”; knapsack ( i + 1, profit + p [ i + 1] , weight + w [ i +1 ]); include [ i +1] = “ no”; knapsachk ( i +1 , profit , weight ); } } bool promising ( index i ) { index j , k ;

اسلاید 162: int totweight ; float bound; if ( weight ≥ W) return false ; { j = i +1 ; bound = profit ; totweight = weight ; while ( j <= n && totweight + w[j] <= W) { totweight = totweight + W [j];

اسلاید 163: bound = bound + p[j]; j++; } k = j; if ( k <= n) bound = bound + (W – totweight) * p [k]/w[k]; return bound > max profit ; } }

اسلاید 164: 2-5-7 مقایسه الگوریتم برنامه نویسی پویا و الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یکتعداد عناصری که توسط الگوریتم برنامه نویسی پویا برای مسئله کوله پشتی صفر و یک محاسبه می شود دربدترین حالت به O (minimum (2ⁿ , nW)) تعلق دارد.در بدترین حالت ، الگوریتم عقبگرد (ⁿ 2)θ گره را چک می کند.

اسلاید 165: الگوریتم عقبگرد معمولا کارایی بیشتری نسبت به الگوریتم برنامه نویسی پویا دارد.هوروویتز و شانی ، روش تقسیم و حل را با روش برنامه نویسی پویا ترکیب کرده الگوریتمی برای مسئله کوله پشتی صفر و یک بسط داده اند که دربدترین حالت به O(2^n/2) تعلق دارد.

اسلاید 166: فصل ششم:راهبرد شاخه و حد

اسلاید 167: راهبرد شاخه و حد ازآن لحاظ به عقبگرد شبا هت دارد که درآن، بریا حل مسئله از درخت فضای حالت استفاده می شود.تفاوت این روش با عقبگرد، اولا ما را به پیمایش خاصی ازدرخت محدود نمی کندوثانیا فقط برای مسائل بهینه سازی به کار می رود.

اسلاید 168: الگوریتم شاخه و حد ، در هر گره عددی را ( حدی ) رامحاسبه می کند تاتعیین شود که آیا این گره امید بخش هست یا خیر.اگر آن حد بهتر از مقدار بهترین حلی که تاکنون یافته شده ، نباشد، گره غیر امید بخش است. در غیر این صورت ، امید بخش است.

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

اسلاید 170: این روش را بهترین جست و جو با هرس کردن شاخه و حد می گویند.پیاده سازی این روش، شکل اصلاح شده ی ساده ای از یک روش دیگر موسوم به جست و جوی عرضی هرس کردن شاخه و حد است.

اسلاید 171: الگوریتم 1-6: الگوریتم جست و جوی عرضی با هرس کردن شاخه و حد برای مسئله کوله پشتی صفر و یک void knapsack ( int n , const int p [ ] , const int w [ ], int W , int & maxprofit ) { queue _of _ node Q; node u , v ; intialize (Q);

اسلاید 172: v.level = 0 ; v.profit = 0 ; v.weight = 0 ; maxprofit = 0 ; enqueue (Q , v); while (!empty (Q)) { dequeue ( Q , v ); u.level = v.level + 1; u.weight = v. weight + w [ u.level]; u. profit = v.profit + p [ u.level]; if ( u.weight <= W && u.profit > maxprofit) maxprofit = u.profit;

اسلاید 173: if ( bound (u) > maxprofit ) enqueue (Q, u) ; u.weight = v. weight; u. profit = v.profit; if ( bound (u) > maxprofit ) enqueue (Q , u); } } float bound ( node u) }

اسلاید 174: index j, k ; int totweight; float result ; if ( u.weight >= W) return 0; else { result = u.profit; j = u.level + 1; totweight = u.weight; while( j <= n && totweight +w [j] <= W) {

اسلاید 175: totweight = totweight + w [j]; result = result + p [j]; j++; } k = j ; if ( k <= n ) result = result +( W – totweight ) * p [k] / w [k]; return result; } }

اسلاید 176: الگوریتم 2-6: بهترین جست و جو با هرس کردن شاخه و حد برای مسئله کوله پشتی صفر و یک void knapsack ( int n , const int p [ ] , const int w [ ], int W , int & maxproit) { priority _ queue_of _node PQ; node u , v ; initialize (PQ) ;

اسلاید 177: v.level = 0 ; v.profit = 0 ; v.weight = 0 ; maxprofit = 0 ; v.bound = bound (v); insert (PQ , v); while (! Empty(PQ)) { remove (PQ , v); if( v.bound > maxprofit ) { u.level = v.level + 1; u.weight = v.weight + w [ u.level ]; u. profit = v.profit + p [ u.level ] ;

اسلاید 178: if ( u.weight <= W && u.profit > maxprofit ) maxprofit = u.profit; u.bound = bound (u); if ( u.bound > maxprofit ) insert (PQ , u); u.weight = v.weight ; u. profit = v.profit ; u.bound = bound (u) ; if ( u.bound > maxprofit ) insert (PQ <u ); } } }

اسلاید 179: 2-6 مسئله فروشنده دوره گردهدف از این مسئله یافتن کوتاهترین مسیر در یک گراف جهت دار با شروع از یک راس مفروض است ، مشروط بر آن که هر راس فقط یک با ر ملاقات شود. چنین مسیری را یک تور می گویند.

اسلاید 180: الگوریتم 3-6: الگوریتم بهترین جستجو با هرس کردن شاخه و حد برای مسئله فروشنده دوره گرد void travel2 ( int n, const number W [ ] [ ] , ordered-set & opttour , number & minlength ) { priority _ queue _ of _ node PQ; node u , v ; initialize ( PQ ) ;

اسلاید 181: v.level = 0 ; v.path = [1]; v.bound = bound (v) ; minlength = ∞ ; insert (PQ , v ) ; while ( ! Empty (PQ)) { remove( PQ, v ); if ( v.bound < minlength ) { u.level = v.level + 1;

اسلاید 182: for (all i such that 2 ≤ i ≤ n && i is not in v.path){ u.path = v.path ; put i at the end of u.path; if ( u.level == n – 2 ) { put index of only vertex put in u.path at the end of path; put 1 at the end of u.path; if ( length (u) < minlength ) { minlength = length (u);

اسلاید 183: opttour = u.path ; } } else { u.bound = bound (u); if ( u.bound < minlength ) insert (PQ , u ); } } } }

اسلاید 184: 2-3استنباط فرضیه ای ( تشخیص بیماری )یک مسئله مهم د رهوش مصنوعی و سیستم های خبره، تعیین محتمل ترین توضیح برای برخی یا فته ها است.برا ی مثال، در پزشکی می خواهیم محتمل ترین مجموعه از بیماری ها را که از یک سری علائم قابل نتیجه گیری است ، تعیین کنیم.

اسلاید 185: فرایند تعیین محتمل ترین توضیح برای یک مجموعه یافته ها را استنباط از طریق فرضیه می نا میم.شبکه باور استانداردی برای نشان دادن روابط احتمالی ، نظیر روابط میان بیماری و نشا نه ها به شمار می رود.

اسلاید 186: الگوریتم 4-6 : الگوریتم بهترین جست و جو با هرس کردن شاخه و حد برای استنباط فرضیه ای ( الگوریتم کوپر) void cooper ( int n , Bayesian_network_of_n_diseases BN, set _ of _symptoms S , set_ of _indices & best , float & pbest ) { priority_queue_of_node PQ ; node u , v ; v.level = 0 ;

اسلاید 187: v.D = Ø ; best = Ø ; pbest = p (Ø | S ); v.bound = bound (v); insert (PQ , v ); while ( ! Empty (PQ)) { remove (PQ , v); if ( v.bound > pbest ) { u.level = v.level + 1; u.D = v.D;

اسلاید 188: put u.level in u.D; if ( p ( u.D | S ) > pbest) { best = u.D; pbest = p ( u.D | S ); } u.bound = bound(u); if ( u.bouond > pbest ) insert (PQ, u); u.D = v.D; u.bound = bound (u); if ( u.bound > pbest )

اسلاید 189: insert (PQ , u ); } } } int bound ( node u ) { if (u.level == n ) return 0 ; else return p(u.D | p (S); }

اسلاید 190: فصل هفتم:مقدمه ای بر پیچیدگی محاسباتی: مسئله مرتب سازی

اسلاید 191: 1- 7 پیچیدگی محاسباتیپیچیدگی محاسباتی عبارت از مطالعه تمام الگوهای امکن پذیر برای حل یک مسئله مفروض است.در تحلیل پیچیدگی محاسباتی کوشش می کنیم تا حد پایینی کارایی همه ی الگوریتم ها را برای یک مسئله مفروض به دست آوریم.

اسلاید 192: تحلیل پیچیدگی محاسباتی را با مطالعه مسئله مرتب سازی معرفی می کنیم.این انتخاب دو دلیل دارد: 1- چند الگوریتم ابداع شده اند که که مسئله را حل می کنند. 2- مسئله مرتب سازی یکی از معدود مسائلی است که در بسط الگوریتم هایی با پیچیدگی زمانی نزدیک به حد پایینی برای آن موفق بوده ایم.

اسلاید 193: 2-7 مرتب سازی درجی و مرتب سازی انتخابیالگوریتم مرتب سازی درجی الگوریتمی اس که مرتب سازی را با درج رکوردها در یک آرایه مرتب شده ی موجود مرتب سازی می کند.

اسلاید 194: الگوریتم 1-7: مرتب سازی درجی void insertionsort ( int n , keytype S[ ] ) { index i , j ; keytype x ; for ( i = 2 ; i <= n ; i ++) { x = S [i]; j = i + 1;

اسلاید 195: while ( j >0 && S [i] > x ) { S [ j + 1 ] = S [j]; j - - ; } S [ j + 1 ] = x ; } }

اسلاید 196: تحلیل پیچیدگی زمانی تعداد مقایسه های کلید ها درا لگوریتم مرتب سازی درجی در بدترین حالتعمل اصلی : مقایسه S [ j] با x .اندازه ورودی : n ، تعداد کلید هایی که باید مرتب شوند.W (n) = n( n - 1) / 2

اسلاید 197: تحلیل پیچیدگی زمانی تعداد مقایسه های کلید ها درا لگوریتم مرتب سازی درجی در حالت میانگینعمل اصلی : مقایسه S [ j] با x .اندازه ورودی : n ، تعداد کلید هایی که باید مرتب شوند. A (n) = n² / 4

اسلاید 198: تحلیل استفاده از فضای اضافی برای الگوریتم 1-7 ( مرتب سازی درجی) تنها فضایی که با n افزایش می یابد، اندازه ی آرایه ورودیS است. پس ،این الگوریتم یک مرتب سازی درجا است و فضای اضافی به(1) θ تعلق دارد.

اسلاید 199: جدول 1- 7 : خلاصه تحلیل مرتب سازی تعویضی ، درجی و انتخابی

اسلاید 200: الگوریتم 2-7: مرتب سازی انتخابی void selectionsort ( int n , keytype S [ ] ) { index i , j , smallest ; for ( i = 1; i <= n-1 ; i ++ ) if ( S [j] < S [ smallest]) smallest = j ; exchange S [i] and S [smsllest ] ; } }

اسلاید 201: قضیه 1-7هر الگوریتمی که n کلید متمایز را فقط از طریق مقایسه کلید ها انجام دهد و پس از هر بار مقایسه ، حد اکثر یک وارونگی را حذف کنید، باید در بدترین حالت حداقل n( n- 1) /4 مقایسه روی کلید ها انجام دهد.

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

اسلاید 203: 4-7 نگاهی دوباره به مرتب سازی ادغامیپیچیدگی زمانی تعداد مقایسه های کلید ها در مرتب سازی ادغامی در بدترین حالت، وقتی که n توانی از 2 است، به طور کلی به θ(n lg n) تعلق دارد: W (n) = n lg n – ( n – 1 )

اسلاید 204: پیچیدگی زمانی تعداد مقایسه های رکورد ها در مرتب سازی ادغامی در حالت معمول تقریبا به صورت زیر است: T ( n) = 2n lg n

اسلاید 205: بهبود بخشیدن به مرتب سازی ادغامیمی توانیم مرتب سازی ادغامی را به سه شیوه بهبود ببخشیم:1- نسخه ای ازمرتب سازی ادغامی به روش برنامه نویسی پویا2- نسخه پیوندی 3- الگوریتم ادغامی پیچیده تر

اسلاید 206: الگوریتم 3-7: مرتب سازی ادغامی 3 ( نسخه برنامه نویسی پویا) void mergesort ( int n , keytype S [ ] ) { int m ; index low , mid , high , size ; m = 2 ^ [ lg n] ; size = 1 ; repeat (lgm times ) { for ( low = 1; low <= m -2 * size + 1 ; low = low + 2 * size ) {

اسلاید 207: mid = low + size -1 ; high = minimun ( low + 2 * size – 1 , n ); merge3 ( low , mid , high , S ); } size = 2 * size ; } }

اسلاید 208: الگوریتم 4-7 : مرتب سازی ادغامی 4 ( نسخه پیوندی)void mergesort4(int low,indexhigh, index&mergedlist) { index mid , list 1 , list 2; if ( low == high ) { mergedlist = low ; S [ mergedlist ].link = 0 ; } else {

اسلاید 209: mid = Į (low + high ) / 2⌡; mergesort4 ( low , mid , list1 ); mergesort4 ( mid + 1, high , list 2); mergesort4 ( list1 , list 2, mergedlist ); } }void merge4(index list1,indexlist2,index& mergedlist) { index lastsorted ;

اسلاید 210: if S [ list 1].key < S [list 2 ] .key { mergedlist = list1; list1 = S [list 2 ].link; } else { mergedlist = list 2; list 2 = S [list 2 ] .link; } lastsorted = mergedlist;

اسلاید 211: while ( list1 != 0 && list2 != 0 ) if S [list 1].key < S [list 2].key { S [ lastsorted ].link = list 1 ; lastsorted = list1; list 1 = S [ list 1] .link; } else { S [ lastsorted ].link = list 2 ; lastsorted = list2;

اسلاید 212: list 2 = S [ list 2] .link; } if ( list 1 ==0) S [ lastsorted ].link = list 2 ; else S [ lastsorted ] .link = list 1 ; }

اسلاید 213: تحلیل استفاده از فضای اضافی برای الگوریتم 4-7(مرتب سازی ادغامی 4)در هر حالت استفاده از فضای اضافی به(n) θ پیوند تعلق دارد.منظور از (n) θ پیونداین است که تعداد پیوند ها به (n) θ تعلق دارد.

اسلاید 214: 5-7 نگاهی دوباره به مرتب سازی سریع void quicksort ( index low , index high ) { index pivotpoint ; if ( high > low ) { partition ( low , high , pivotpoint ) ; quicksort ( low , high , pivotpoint – 1); quicksort (pivotpoint + 1 , high ); } }

اسلاید 215: روش های بهبود بخشیدن به الگوریتم مرتب سازی سریعاستفاده از فضای اضافی در مرتب سازی سریع را می توان به پنج شیوه کاهش داد: 1- در روال quicksort ، تعیین می کنیم کدام زیر آرایه کوچک تراست و همواره آن را در پشته قرار می دهیم و دیگری را نگه می داریم.

اسلاید 216: در این نسخه استفاده از فضای اضافی در بد ترین حالت به (lg n) θ اندیس تعلق دارد.2- نسخه ای از partition وجود دارد که تعداد انتساب های رکورد ها را به طرزی چشمگیر کاهش می دهد.

اسلاید 217: برای این نسخه، پیچیدگی زمانی تعداد انتساب های انجام شده توسط مرتب سازی سریع در حالت میانگین عبارت است از:A (n) = 0.69 ( n + 1 ) lg n

اسلاید 218: 3- مقدار زیادی از اعمال pop و push بی مورد است. می توانیم با نوشتن quicksort به شیوه تکرار و دستکاری پشته در روال، ازعملیات بیهوده پرهیز کنیم، یعنی به جای استفاده از پشته و بازگشتی ، پشته را خودمان می سازیم.

اسلاید 219: 4- الگوریتم های بازگشتی مثل مرتب سازی سریع را می توان با تعیین یک مقدار آستانه که در آن الگوریتم به جای تقسیم بیشتر نمونه ، یک الگوریتم تکراری را فراخوانی می کند ، بهبود بخشید.

اسلاید 220: 5- انتخاب میانه S [low] ، S [ Į low + high )/2⌡ ، S [high] برای نقطه ی محوری است.

اسلاید 221: 6-7 مرتب سازی heapدرخت دودویی کامل یک درخت دودویی است که واجد شرایط زیر باشد:همه ی گره های داخلی دو فرزند داشته باشند.همه ی برگ ها دا رای عمق d باشند.

اسلاید 222: درخت دودویی اساسا کامل یک درخت دودویی است که: تا عمق (n – 1) یک درخت دودویی کامل باشد.گره هایی با عمق d تا حد امکان در طرف چپ واقع شوند.

اسلاید 223: heap یک درخت دودویی اساس کامل است به طوری که:مقادیر نگهداری شده در گره های آن از یک مجموعه مرتب باشند.مقادیر نگهداری شده درهر گره بزرگ تر یا مساوی مقادیر نگهداری شده در فرزندان آن باشد.

اسلاید 224: 2-6-7 پیاده سازی مرتب سازی heap ساختمان داده های heap struct heap { keytype S [1..n]; int heapsize ; }; void siftdown ( heap& H , index i ) {

اسلاید 225: index parent, largerchild; keytype siftkey; bool spotfound; siftkey = H.S[i]; parent = i ; spotfound = false; while (2* parent <= H.hepsize &&! spotfound) { if ( 2 * parent < H.heapsize && H.S [ 2*parent] largerchild = 2 * parent + 1; else largerchild = 2 * parent ;

اسلاید 226: if ( siftkey < H.S[largerchild ]) { H.S [parent] = H.S[largerchild ]; parent = largerhild ; } else spotfound = true; } H.S[parent] = siftkey; }

اسلاید 227: keytype keyout ; keyout = H.S [1]; H.S[1] = H.S[heapsize]; H.heapsize = H.heapsize -1; siftdown (H , 1 ); return keyout; } void removekeys ( int n, heap& H keytype S[ ] )

اسلاید 228: { index i ; for ( i = n; i >= 1 ; i --) S [i] = root (H); } void makeheap ( int n, heap& H) { index i ; H.heapsize = n ;

اسلاید 229: for ( i = Į n/2⌡; i >= 1 ; i --) siftdown (H,i); }

اسلاید 230: الگوریتم 5-7: مرتب سازی heap void heapsort ( int n , heap& H) { makeheap ( n, H ); removekeys ( n, H , H.S ); }

اسلاید 231: 7-7مقایسه مرتب سازی ادغامی، مرتب سازی سریع ومرتب سازی heapمرتب سازی سریع معمولا بر مرتب سازی heap ارجحیت دارد.مرتب سازی سریع معمولا بر مرتب سازی ادغامی ترجیح داده می شود.

اسلاید 232: 1-8-1 درخت ها ی تصمیم گیری برای الگوهای مرتب سازیلم 1-7: متناظر با هر الگوریتم قطعی برای مرتب سازی n کلید متمایز، یک درخت تصمیم گیری دودویی ، معتبر و هرس شده با دقیقا n! برگ وجود دارد.

اسلاید 233: لم 2-7: تعداد مقایسه های انجام شده توسط یک درخت تصمیم گیری در بدترین حالت برابر با عمق درخت است.

اسلاید 234: لم 3-7: اگرm تعداد برگ ها در یک درخت دودویی و d عمق آن باشد، داریم:d ≥ ┌ lg m ┐

اسلاید 235: قضیه 2-7هر الگوریتم قطعی که n کلید متمایزرا فقط با مقایسه کلید ها مرتب سازی می کند، باید در بدترین حالت حد اقل ┌ lg ( n!) ┐ مقایسه کلید ها راانجام دهد.

اسلاید 236: لم 4-7: به ازای هر عدد مثبت و صحیح n، داریم: lg (n!) ≥ n lg n – 1.45 n

اسلاید 237: قضیه 3-7هر الگوریتم قطعی که n کلید متمایز را فقط با مقایسه ی کلید ها انجام می دهد باید در بدترین حالت حداقل ┌ n lg n – 1.45n┐ مقایسه کلید ها را انجام دهد.

اسلاید 238: 3-8-7 حدود پایینی برای رفتار در حالت میانگینلم 5-7: متنا ظر با هر درخت تصمیم گیری دودویی معتبر هرس شده برای مرتب سازی n کلید متمایز، یک درخت -2 تصمیم گیری معتبر هرس شده وجود دارد که حد اقل به اندازه درخت اول کارایی دارد.

اسلاید 239: لم 6-7: هر الگوریتم قطعی که n کلید متمایز را فقط با مقایسه کلید ها مرتب سازی می کند، حد اقل تعداد محاسبه کلید های که انجام می دهد به طور میانگین برابر است با:mimEPL (n!) / n!

اسلاید 240: لم 7-7: هر درخت دودویی-2 که دارای m برگ باشد و EPLآن برابر minEPL(m) باشد، باید همه ی برگ های آن در پایین ترین سطح باشند.

اسلاید 241: لم 8-7: هر درخت -2 که دارای m برگ وEpl آن برابر minEPL(m) باشد ، باید 2^d – m برگ در سطح d – 1 و 2m – 2 ^d برگ درسطح d داشته باد و برگ دیگری نداشته باشد، d عمق درخت است.

اسلاید 242: لم 9-7: به ازای هر درخت -2 که m برگ و EPL آن برابرباminEPL(m) باشد، عمق d عبارت است از:d = ┌ lg m ┐

اسلاید 243: لم 10-7: به ازای همه ی مقادیر m ≥ 1 داریم :mimEPL(M) ≥ m Į lg m⌡

اسلاید 244: قضیه 4-7هر الگوریتم قطعی که n کلید متمایزرا تنها با مقایسه کلیدها مرتب سازی کند، به طور میانگین باید حداقل این تعداد مقایسه ها را انجام دهد:n lg n – 1.45n⌡ Į

اسلاید 245: 9-7 مرتب سازی از طریق توزیع (مرتب سازی مبنایی)الگوریتم 6-7: مرتب سازی مبنایی void radixsort ( node_pointer& mastrrlist; int numdigits) { index i ; node_pointer list [0..9] for ( i = 1 ; i <= numdigits ; i ++) {

اسلاید 246: disteibute (i); coalesce ; } } void distrebute ( index i ) { index j ; node_pointer p ; for ( j = 0 ; j <= 9 ; j++)

اسلاید 247: list [j] = NULL; p = masterlist ; while ( p != NULL) { j = value of ith digit (from the right)in p -> key; link p to the end of list [j]; p = p -> link ; } } void coalesce()

اسلاید 248: { index j; masterlist = NULL; for ( j = 0 ; j <= 9 ; j++) link the nodes in list [j] to the end of masterlist; }

اسلاید 249: با تشکرپایان