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

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

صفحه 2:
فصل دوم: روش تقسيم و حل 

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

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

صفحه 5:
ن<ظني5ْئظجعْقَج5حصَّّئقّْقأ ييا سس الگوریتم۲-۱: جست و جوی دودویی (بازگشتی) ( ۱ب رسای ) مرا بط ‘ terdx wid; B (ow > bk) vetura O; vbw { wal = (ow + kick) (2 J; B= = 6 [wad]) vetwa wid; ebe P(x <6 [wxl]) retards (lw , word — 1); ‏اه‎ yetura boca (wad + 4, hich); } } location(1, n) ‏فراخوانی اولیه:‎ 

صفحه 6:
I ‏لحي بجحتت ردت وكين حالت براك الگوریتم جست و جوی دودویی‎ ‏باز‎ عمل اصلی: مقایسه » با [0] 5) اندازه ورودی: ۰. تعداد عناصر آرایه. (9/) 0 2 (و) ۵ برای ۰6 6< ‎٩‏ توانی از ۲ است + (۱9) ۵ ۶ ) ۵ 2 () ۵ 0۵ ‏وا ع (و)‎ [+ 06 (ys) 

صفحه 7:
OO ‏۲-۳مرتب سازی ادغامی‎ * ادغام دوطرفه به معنای ترکیب دو آرایه مرتب شده در یک آرایه ی مرلب است. 

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

صفحه 9:
مراحل انجام شده توسط انسان در هنگام مرتب سازی ادغامی ااإإِؤِ3إؤؤة ا وإ لإل3زة7ة7ةك ا 

صفحه 10:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏الگوریتم ۲-۲: مرتب سازی ادغامی ([ ] ۵ مهوها , ۰ ) ی لس ۰-۷ عم , | 2۵ ماس 0.0 10.110 0 مهجا: (0< مم ( ‎OK)‏ ۰ ۵1 سس [0]© ندر ‎ory © [k +d] took Gl] & O[d] hrouk Of] jwereesori(k, D) ‎wercesori(w,O) ‎jweree (kw, O,0,6) ‎{ ‎1 

صفحه 11:
‎oO "‏ الگوریتم۲-۳: ادغام ‎Lord erg (tot, toto, covet eye D ,] ‏اس‎ ape O ‏۵ مهو ]) ‎7 ‎iodex it, j,k ‎۱ 2۶ ۱2 1:۳0 ‎} while (i <= k && | <= ‏(ه‎ ‎}PON<Of) ‎GH=00 ‎vet 

صفحه 12:
{ } ebe OW =O vat 1 اب جر 1 <ا)ع [> + ط] © عيعمط [] 5< [م] 0 مس ‎cop O [i]‏ عام ‎G[k +a]‏ مسا [] 6۵ ۲[ 0ص [] () وه 1 

صفحه 13:
OO ‏تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم ۲-۳(ادغام)‎ عمل اصلی: مقایسه![] 0 با. 0 اندازه ورودی:۳ و « .تعداد عناصر موجود در هر یک از دو آرایه ورودی. 0 - وم +2۷ ( ,۲۱) 0 

صفحه 14:
۰ دربدترین حالت برای الگوریتم ۲-۲( مرتب سازی ادغامی) عمل اصلی: مقایسه ای که درادغام صورت می پذیرد. اندازه ورودی: ۰ تعداد عناصر آرایه ‎S‏ ‎O() = Of) + O(w) + k+w-4‏ 4 4 4 زمان لازم براى ادغام ‎١‏ زمان لازم براى مرتب سازى ‎1١‏ زمان لازم برای مرتب سازی ۲ براى 1< 2 كه 8 توانی از 2 است ‎W(n) =2W(n/2) +n-‏ 1 20 (1) ۷۷ وواه) 69 (0)0 

صفحه 15:
* مرتب سازی درجا: روشی که از فضایی بیشتر از آنچه مورد نیاز ورودی است استفاده نمی ‎WS‏ ‏" الگوریتم گفته شده درجا نیست ‏ زیرا از آرایه 10و 7 به همرا آرایه ورودی 5 استفاده می کند. * میزان حافظه اضافی: ‎n +n/2 +n/4+ ...=2n‏ * کاهش مقدار حافظه اضافی به ۲ 

صفحه 16:
الگوریتم۲-۴: مرتب سازی ادغامی 2(۲ ۳6۲650۲۸ ) (۱ ۲ ,سا ی هچ و } ۳ ( 8 (ow <bxk) ع / وه + سط)1 = ‎cod‏ )3 ‎(low, wid)‏ © جدود ‎jweryesort © (cid +4, Kick)‏ ‎werteG (lew, <td, bak)‏ ‎1 ‎{ 

صفحه 17:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏الگوریتم۲-۵:ادغام۲ مسثله: ادغام دو آرایه ی مرتب 5) که دراسسمج ایجاد شده اند. vord core (tarde low, todo ctl, tarde hich) } ۳ i, ‏عا‎ ‎low..hick]‏ [ © مهو ‎= bw} j= wd +k Eb ‎} while (1 <= wid && 1 <= hick) ‏(600> [] مام ر ‎:0 1 - © ][ ‎+ ‎1 

صفحه 18:
اه ( 9 1 - ۵ ][ atti i jek { P(i> wid) wove © [ij] trouk G [ich] 7 © [Keak © [kh] ele wove © fi] tro © [rod] to O [k] took © [hick] wove D [ow] tours D [high] to © Dow] tous G [hick] { 

صفحه 19:
I ‏م-«اروش تقسیم و حل‎ راهبرد طراحى تقسيم و حل شامل مراحل زیر است: ‎-١‏ تقسيم نمونه ایب ازیک مسئله به یک یا چند نمونه کوچکتر ‏۳- حل هر نمونه کوچکتر. اگر نمونه های کوچک تر به قدر کوچک تر به قدر کافی کوچک نبودند. برای اين منظور از باز گشت استفاده کنید. ‏۳- در صورت نیا حل نمونه های کوچک تر را تر کیب کنید نا حل نمونه اولیه به دست آید. ‎ 

صفحه 20:
I )10101660۳( ‏مرتب سازی سریع‎ ۴-۲ * در مرتب سازی سریع. ترتیب آنبا از چگونگی افراز آرایه ها ناشی می شود " همه عناصر کوچک تر آز عنصر محورى در طرف جب آن وهمه عناصربزرگ تر. درطرف راست آن واقع هستند. 

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

صفحه 22:
مراخل انجام شده توسط آنتتان در هنگام مرئت سازی سریع ط«_«_« ”ك0 

صفحه 23:
OO ‏الگوریتم ۲-۶ :مرتب سازی سریع‎ مسثله: مرتب سازی « کلید با ترتیب غیر نزولی. ‎wold quicksort (index lous , tack hich)‏ } سس بل ‎}R (heh > baw)‏ ‎portiva (low , hick , piuoipotal)‏ ‎Nicksort (law , peoiport — (1)‏ اه , 0 + ‎(pvotport‏ وصور 1 1 

صفحه 24:
‎oO "‏ الگوریتم۲-۷: افراز آرایه ‏مسئله: افراز آرایه 2 برای مرتب سازی سریع. ‎votd portiiza (tedex low, terdex hich)‏ سپس 6 ‎(torderx‏ ‏} ‎Horde ti‏ سم مها ‎CG [ow]‏ = محص سا[ ‎Por (1 = bw 40151 <= hich 1 ++)‏ 

صفحه 25:
(مسمم > [] ۵) 6 } vel ‎od 6 [i]‏ (] ۵ اس ‎1 ‏> سر ‎jexckange G flow] oad G [ puvipvinl] 1 

صفحه 26:
ن<ظني5ْئظجعْقَج5حصَّّئقّْقأ ييا سس تحليل بيجيدكى زمانى در حالت معمول برای الگوریتم ۲-۷( افراز) عمل اصلى: مقايسه[1] 5 با 215701366122 . اندازه ورودى: + ‎ca = higk — haw‏ تعداد عناصرموجود در زير آرايه. 4)( 2-0 

صفحه 27:
‎oe‏ پیچیدگی زمانی در بدترین حالت برای الگوریتم ۲-۶(مرتب سازی ‎co‏ ‏عمل اصلی: مقایسه [1] 5 با سم در رولل ۳0۳۲۸۳۰ ‏اندازه ورودی: ۰۰ تعداد عناصر موجود درآرایه 65 ‎Ma) = DO) + ۰-۵ + ۰-0‏ ‎+ 4 4 ‏زمان لازم برای افراز زمان لازم برای مرتب سازی زمان لازم برای مرتب سازی زیرآرایه طرف راست ‏زیر آرایه طرف چپ 

صفحه 28:
u>O T (a) = T )6-0( + ۰ - ) ‏به ازای‎ (0) = © 0 ©( --6-0(/6 66 )2 

صفحه 29:
ري ًنت”ن”بضظي*ضي>يض»ي”ي”ي5يوَيَ_ََم ‎I‏ ‏تحلیل پیچیدگی زمانی در حالت میادگین برای الگوریتم ۲-۶(مرتب سازی سریع) عمل اصلی: مقلیسه[1] 5 با ماس در م۳ اندازه ورودی: ۰. تعداد عناصر موجود در ظ) مه 1-م+ [(م-م4 + 1 -مم] = ‎A@=)‏ P probability of Pivotpoint=p Ybe-» +A(n—p)]) =2) A@-1) = ot aq) =2) ap) tn 1 

صفحه 30:
OO ‏تحلیل پیچیدگی زمانی در حالت میادگین برای الگوریتم ۲-۶(مرتب سازی‎ سریع) حال با کسر (9)0) و (۵)740) و ساده سازی رابطه زیر بدست می آید )2-1 , ‎Af) A(n-1)‏ ‎n(n+ 1)‏ ۲ 70:1 _ ‎Pawel‏ ‎anf)‏ 3 ‎mee ea ee‏ 0 < وه A(n) © (n + 1)2Inn = (n + 1)2(Inn)(Ign) © 1.38(n + 1)lgn EO (nlg n) 

صفحه 31:
‎oO "‏ ۲-هالگوریتم ضرب ماتریس استراسن ‏* پیچیدگی این الگوریتم از لحاظ ضرب. جمع و تفریق بیتر از پیچیدگی درجه سوم است ‏* روش استراسن در مورد ضرب ماتریس های 2۲ ارزش چندانی ندارد. 

صفحه 32:
مروری بر ضرب ماتریس * حاصلضرب ماتریسهای مربعی ۸ و 3 به صورت زیر تعریف ‎Cen 22 a‏ دراه مورب ۵ ب(بعا< قعدمده6 * یه عنوان مثال در حالت 2 = 1 داریم: برای محاسبه هر درايه نياز به 2 عمل ضرب داري ‎fe. A ts‏ تمامی ۲ « درایه ماتریس 7 7 عمل ضرب نیاز خواهیم داشت. ‎ay ay i by _ ۵ ۳‏ بك 2 ‎ay ay, 1 by | a,b, +4,b,,‏ 

صفحه 33:
C,,=P,+P,-P; +P, C,, = P, + P, C,, = P,P, C,, =P, + P,- P, +P 6 By) eee = (A,,+ A,,)(B,,+B,,) = (A, + A.) * By, = A,, * (B,, - B,,) = A,, * (B,, - ‏(ررظ‎ ‎= (A,, + A,,) * B,, = (A, - A.) * By + 

صفحه 34:
I ‏الگوریتم ۲-۸: استراسن‎ مسئله : تعبین حاصلضرب دو ماتریس ۱ 1 که در آن " توانی از 2 است. ۱ ‏ره لما‎ ot X a _ wart @, aX u_ wort @, aX a_ ware & O){ P (a <= hreshokd) ‎O = ۷ @ ustey the stradard dort;‏ سوه ‏عه ( 6 ), 909 ,00) هی و ط ط موز 9 , 969) ,000) نی عمد ط ظ) موز ‎joowpuie 6) < 0 ۷ 6 usicy Gtarsseu's Detkod‏ 1 ‎1 

صفحه 35:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏تحلیل پیچیدگی زمانی تعداد ضرب ها در الگوریتم ۲-۸ (استرسن)در حالت معمول ‎Jor‏ اصلی: یک ضرب سلده. اندازه ورودی:» . تعداد سطرها و ستون ها در ملتریس. ‏به ازای ) < ۰ که ۰ توانی از ۲است ‏ (0/8) 2 (و) * )1 ‎۱) © ۵60 

صفحه 36:
تحلیل پیچیدگی زمانی تعدادجمع هاو تفریقهای الگوریتم (استرسن)درحالت معمول عمل اصلی: یک جمع یا تفریق ساده. اندازه ورودی:» . تعداد سطرها و ستون ها در ملتریس. به ازای 4 < ۰ که " توانی از ۲است۱۸ (260 (و) )+ 2 21 (۰)4* T(a)E 0(a* 6.00) 

صفحه 37:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏ضرب اعداد بزرگ * دربرخی از مسایل لازم است با اعداد بسیار بزر گ محاسباتی انجام دهیم. * ضرب دو عدد بسیار بزرگ نمونه ای از این موارد است که می توان الگوریتم آن را به روش تقسبم و حل تییه کرد. 

صفحه 38:
2ة## ‎OO‏ ‏روند الگوریتم * دو عدد او ۷ با تعداد ارقام بالا و متفاوت را می نوان به دو بخش عددی تفکیک کرد. قسمت اول هر دو عدد ۲ رقم دارند. ‎U 2۳238‏ 7 7۷ UV=(W*10"4X)(Y*10"+Z)=WY*102"+ (WZ+XY)*10"+XZ, 

صفحه 39:
ن<ظني5ْئظجعْقَج5حصَّّئقّْقأ ييا سس الگوریتم۳-۹: ضرب اعداد صحيح بزرك مسقله: ضرب دو عدد صحیح بزرگ او ۷ (ن عصيجم_حيمها إن تا ) مس _ ها } سار اهاز عار ‎oP digis itv)‏ مرن معا اه ام )موی < و ‎ ۵(‏ دس || © د دمم)ا م ‏0 و 

صفحه 40:
be P (<= tvestoh)) ‎nthe wud way‏ ون ند ند بو ‎} ebe ‎| ۸9 ‏اه * 000 صم د بر زاج 04( ‎eS ubads‏ ‎jw Suche (OD 4S @ ‏اه > 000 صر 2 د زر‎ ‎vetwra prod (x w) * (OD “Ow + ( prod (x, 2) + prod ; (wv )) * WD 4 ww + prod (y, 2) ‎1 ‎1 

صفحه 41:
ا | لگوریتم٩-۲(‏ ضرب اعداد ‎ave‏ عمل اصلی: دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در هنگام جمع کردن . تفریق کردن. یا انجلم اعمالب ‎AD ٩‏ عبط ‎x brew AD Ao‏ ” > هر يك از اين اعمال زا © بار انجام می دهد. اندازه ورودى: 10 . تعداد ارقام هر یک از دو عدد صحیح. ‎oO (a) = © (a/ ©) + cacounl? 5I sigs a oF ۰ < ‏به ازای ع‎ ۵ )۶( - © ‎W(n) € 0(n?) ‎ 

صفحه 42:
OO ۲ ‏الگوریتم ۱۰ -۳: ضرب اعداد صحیح بزرگ‎ | ‏(ن تا دا ها‎ 1 ‏سار زر از‎ et, 7 ja = waxtwur (uber of digits ‏وا‎ uyaucober oF dais itv) & (u==O||v==0) : ‏ده‎ 0 vee P («<= trestoll) ‏مور‎ * vobtaced inthe wudway 

صفحه 43:
[ ‏اه‎ ‎: 2 ‏طمف : 2 عر‎ 0٩۰ : ‏مور ير‎ 0۰ ‏طجظ ن 2 بير‎ (O04 a ‏حير 2 د ز‎ 000 ao i moped (ety +=) mere 2 ‏رك‎ ‎n= prod? (vz) jretwa p XID “Ga + (r-p—q) ۷ 10۰ + { 1 

صفحه 44:
تحلیل پیچیدگی زمانی در بدترین حالت برای الگوریتم۰ ۲-۱( ضرب اعداد محیح۲) عمل اصلی: دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در هنكام جمع كردن . تفريق كردن. يا انجلم اعماله “ 000 طبظ . ‎x brew AD Ao‏ ” > هر يك از اين اعمال زا © بار انجام مى دهد. اندازه ورودى: 10 . تعداد ارقام هر یک از دو عدد صحیح. ‏به ازای < < ۰ که " توانی از ۲است ‎SO(We)+ vu <=O (a) <= 90 (a/ 8 +) +00‏ © - (و) ۵ ‎W (@) = 0 (@@ * 1.58)‏ ‎