درس طراحی الگوریتم ها (روش تقسیم و حل)

درس طراحی الگوریتم ها (روش تقسیم و حل)

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

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

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

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

اسلاید 5: الگوریتم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; else if ( x < S [mid]) return location (low , mid – 1); else return location (mid + 1, high); } } فراخوانی اولیه: location(1, n)

اسلاید 6: تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم جست و جوی دودویی بازگشتی عمل اصلی: مقایسه 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)

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

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

اسلاید 9: مراحل انجام شده توسط انسان در هنگام مرتب سازی ادغامی

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

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

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

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

اسلاید 14: تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم 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)

اسلاید 15: مرتب سازی درجا: روشی که از فضایی بیشتر از آنچه مورد نیاز ورودی است استفاده نمی کند.الگوریتم گفته شده درجا نیست ← زیرا از آرایه U و V به همرا آرایه ورودی S استفاده می کند.میزان حافظه اضافی:n +n/2 +n/4+ ...≈2nکاهش مقدار حافظه اضافی به n ؟

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

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

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

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

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

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

اسلاید 22: مراحل انجام شده توسط انسان در هنگام مرتب سازی سریع

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

اسلاید 24: الگوریتم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 ++)

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

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

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

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

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

اسلاید 30: تحلیل پیچیدگی زمانی در حالت میانگین برای الگوریتم 6-2(مرتب سازی سریع)حال با کسر A(n) و A(n-1) و ساده سازی رابطه زیر بدست می آید

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

اسلاید 32: مروری بر ضرب ماتریسحاصلضرب ماتریسهای مربعی A و B به صورت زیر تعریف می شودیه عنوان مثال در حالت n = 2 داریم: برای محاسبه هر درایه نیاز به n عمل ضرب داریم. بنابراین برای محاسبه تمامی n2 درایه ماتریس C به n3 عمل ضرب نیاز خواهیم داشت.

اسلاید 33: جملات ضرب استراسنP1 = (A11+ A22)(B11+B22) P2 = (A21 + A22) * B11 P3 = A11 * (B12 - B22) P4 = A22 * (B21 - B11) P5 = (A11 + A12) * B22 P6 = (A21 - A11) * (B11 + B12) P7 = (A12 - A22) * (B21 + B22) C11 = P1 + P4 - P5 + P7 C12 = P3 + P5 C21 = P2 + P4 C22 = P1 + P3 - P2 + P6A11 A12A21 A22B11 B12B21 B22C11 C12C21 C22*=

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

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

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

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

اسلاید 38: روند الگوریتمدو عدد u و v با تعداد ارقام بالا و متفاوت را می توان به دو بخش عددی تفکیک کرد. قسمت اول هر دو عدد m رقم دارند.W XY ZUVUV=(W*10m+X)(Y*10m+Z)=WY*102m+(WZ+XY)*10m+XZ

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

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

اسلاید 41: تحلیل پیچیدگی زمانی در بدترین حالت برای ا لگوریتم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² )

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

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

اسلاید 44: تحلیل پیچیدگی زمانی در بدترین حالت برای الگوریتم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)