روش تقسیم و حل (Divide and Conquer)

صفحه 1:


صفحه 2:
روش تقسیم و حل (3130 ‎Divide‏ ‎(Conquer‏ 

صفحه 3:
(Divide and Conquer) J> 5 pits, شيوه حل در اين روش به اين صورت است که: به صورت بازگشتی ... مساله به دو یا بیشتر زير مساله از نوع همان مساله (يا مساله‌ای که در حل مساله اصلی مرتبط است) تقسیم (011۷1016) می‌شود و ... اینکار (شکستن و تقسیم‌کردن) تا آنجایی ادامه می‌یابد که ... مساله به اندازه‌ای ساده شود که بتواند مستقیما حل شود ‎cCONquUer)‏ سيس ... ياسخهاى زيرمسالدها با هم تركيب مىشوند تا ياسخى براى مساله اصلى فراهم سازند. 

صفحه 4:
(Divide and Conquer) J> 5 pits, فهم و طراحی الگوریتم‌های ‎Slee DEC‏ پیچیده‌ای است که نیازمند فهم خوب از ماهیت مساله دارد. 

صفحه 5:
(Divide and Conquer) J> 5 pits, ‏توجه:‎ *به هنگام نوشتن الگوریتم‌های بازگشتی در سطح مسئله فکر می‌کنیم 5 "می‌گذاريم تا جزئیات را زبان برنامه نویسی با استفاده از ‎٩13016‏ بر عهده كيرد *هنگام طراحی الگوریتم‌های تفسیم و حل معمولا همین گونه فکر می‌کنيم و آن را به صورت یک روال بازگشتی می‌نویسیم 

صفحه 6:
روش تقسيم و حل (0110[11©1© ‎(Divide and‏ برخی از مولفین می‌گویند که عنوان روش تقسيم و حل حتما می‌بایست به روش‌هایی تعلق گیرد که مساله را به دو يا بیشتر زیرمساله تقسیم می‌کند و ... چنانچه مساله به تنها یک زیرمساله دیگر شکسته شود به آن روشء کاهش و ‎(Decrease and Conquer) J>‏ می‌گویند. 

صفحه 7:
کوئیز از جلسه قبل) ‎ai Bie |) ob a‏ ‎oti if n is even‏ نشان فهید کف ‎ifnis odd‏ 1 ‎not in o(n).‏ جوز( ‎but that‏ 6 610۵00 00 )ب( )الف( 

صفحه 8:
روش تقسیم و حل سابقه تاریخی علت نام گذاری این روش: در سال ۰۱۸۰۵ ارتشی از سربازان روسی و اتریشی با بیش از ۱۵ هزار نفر به جنگ با ناپلئون آمدند. ناپلئون با حمله به قلب سپاه آنها و تقسیم نیروهای دشمن به دو بخش بر آنها پیروز شد. در واقع ناپلئون با تقسیم (01۷106]) سپاه بزرگ به دو سپاه کوچکتر و پیروز شدن بر تک‌تک آنها موفق شد بر آن سپاه بزرگ ‎(Conquer) at a‏ 

صفحه 9:
الف) جستجوی دودویی a (2 ۳ 47. أكرا»ز يرابر عبصر :مياق آراله يود جستجو امام أسث ودر قيزاين صورة م آرایه را به دو زیر آرایه تقسیم کن که هریک حدودا نصف آرایه اولیهاند. اگر 26 کوچکتر از عنصر میانی بود کار را در زیرآرایه چپی و اگر 26 بزرگتر از عنصو ميان بود«.کار را در ژیز آرایهراستی انامه مي‌ذهيم حل مسئله را از حل مسئله زیر آرایه به دست آور 10 12 13 14 18 20 25 27 30 35 40 45 1 Middle item 

صفحه 10:
الف) جستجوی دودویی 10 12 13 14 18 20 25 27 30 35 40 45 47 x=18 Choose left subarray ite: because x < 25. Compare x with 25. 

صفحه 11:
الف) جستجوی دودویی function position=recbinsearch(x,low,high) global A; توجه: ‎mid=floor((low+high)/2); 5 ۲ =‏ ‎lp‏ تعریف متغیر به صورت عمومی به ۱ ‎iF ad‏ ۴ 5 9 شده ‎position=mid;‏ ‏كوندايكه در تمامی تبع‌ها قابل دسترسی باشد. ‎ae‏ ‏ابتدا آن را عمومی تعریف می‌کنیم: ‎if x<A(mid)‏ ‎newlow=low; newhigh=midt; global A;‏ ‎else‏ newhigh=high; newlow=mid+1; ‏سپس مقداردهی می‌کنیم:‎ end A=[10 12 13 14 18 20 25 27 30 if (newhigh>=newlow) high=newhigh; low=newlow, 35 40 45 47]; postion=recbinsearch(slow.highhiay 5 jl eolizel jl Jad Galt 7 ‏در‎ ; else position=0; ‏آن استفاده می‌کنیم:‎ sie end global A; end end 

صفحه 12:
الف) جستجوی دودویی پیچیدگی در بدترین حالت: سوال) بدترین زمان کی رخ می‌دهد؟ الف) المان مورد جستجو در لیست نباشد؟ ب #پی مورد جستجو از تمامی المان‌های لیست بزرگتر باشد؟ ‎mid=floor((low+high)/2); ....‏ مثلا در لیست [۱ ۲ ۳ ۴ ۵] چنانچه دنبال ۶ بگردیم چند جستجو نیاز است؟ دنبال ‎٠‏ بكرديم چند جستجو نیاز است؟ 

صفحه 13:
الف) جستجوی دودویی تحلیل پیچیدگی در بدترین حالت: 11 ]| ۷ ‎W(n)= (5) + J‏ Comparisons in Comparison at recursive call top level W(1)=1 

صفحه 14:
الف) جستجوی دودویی اثبات پیچیدگی در بدترین حالت با استقرا: ۲ 5 ]اه هر ما دسا واه فرمول روبرو را درنظر بگیرید: | ‎fot Power F2‏ برای تعدادی از ‎N‏ ها 00 را می‌توانيم محاسبه کنیم: te =te +1=t)+1=14+1=2 testy tl=t+1=2+1=3 ty = tea tl=tyt1=3+1 ‏و6 1+ ورورا < مرا‎ + 1 < 4+1 5 به نظر می‌رسد که رابطه زیر برقرار باشد: 1۰ + 109 ع< با 

صفحه 15:
ty =tnat1 — forn> 1, 1a power of 2 الف) جستجوی دودویی ‎tid‏ ‏اثبات پیچیدگی در بدترین حالت: ب استقرا نشان مىدهيم كه اين رابطه صحبح است. 1۰ + 1810 < «1 پایه استقرا: (برای 1<-0) t) =1=lg1+1. فرض استقرا: فرض می‌کنیم پرای 0< دلخواهی که توانی از ۲ است رابطه زیر پرقرارباشد: 1۰+ 161 < «ر 

صفحه 16:
الف) جستجوی دودویی گام استقر: به دلیل آنکه فرمول بازگشتی که به دنبال اثبات آن هستیم تنها برای اعدادی که توانی از ۲ هستند مصداق دارد بنابراین ..- عدد بعدى كه بعد از ‎1١‏ درنظر م ىكيريم بايد ... 0 باشد بنابراین باید نشان دهیم که : .1+ ‎ton = Ig (2n)‏ چنانچه 20 را در رابطه بازگشتی قرار دهیم ... 1 وزرا مب tan = tanyj2atl=ty+l=iIgn+1+4+1 < ۱ +۱2 +1 < ‏و[‎ )2( + 1 

صفحه 17:
الف) جستجوی دودویی تحلیل پیچیدگی در بدترین حالت: ‎W (3) + 1‏ - 17 ~ كيه ‎Comparisons in Comparison at‏ ‎recursive call top level‏ 1 > (1) 1۳ با استقرا نشان دادیم که رابطه زیر برای زمانیکه ۰۱ توانی از ۲ باشد برقرار است: W (n) =Ign+1. ‏در حالت کلی چنانچه این شرط محدودکننده را برداریم رابطه زیر اثبات خواهد شد که:‎ W (n) = [Ign] +1€ O (Ign), 

صفحه 18:
ب) مرتب‌سازی ادغامی (50۲0 0۸۵۳۵6 8 8 1 ۲ 7 ‏لقا‎ ‎Toy ‎| ‏لبي‎ ‎3 ‎Po] ‎=) KE 8 8 8 1 0 aL] 

صفحه 19:
ب) مرتب‌سازی ادغامی ‎(Merge Sort)‏ function fey if ia>lena result=merge(A,B) lena=max(size(A));lenb=max(size(B)); result(k:lena+lenb)=B(ib:len result=zeros(1,lena+lenb); 0) ia=1ii 1; else while(ia<=lena && ib<=lenb) if A(ia)<B(ib) 1 result(k)=A(ia); result(k:lena+lenb)=A(ia:len ia=iat1; a); else end result(k)=B(ib); ib=ib+1; end end kek+1; end 

صفحه 20:
(Merge Sort) ‏ب) مرتب‌سازی ادغامی‎ function [result]=mergeSort(A) len=length(A); mid=round(len/2); if (len==1) result=A; else L=mergeSort(A(1:mid)); R=mergeSort(A(mid+1:len)); result=merge(L,R); end end 

صفحه 21:
روش تقسیم و حل کوئیز از جلسه قبل) با استقرا نشان دهید که پیچیدگی زمانی در الگوربتم جستجوی دودویی در بدترین حالت با روش تقسیم و حل برابر است با ‎W(n)=logn+1‏ (اثبات را برای زمانیکه ۲0ها توانی از ۲ هستند انجام دهید) توجه: مراحل در شیوه اثبات استقرایی را با دقت بیان کنید. 

صفحه 22:
ب) مرتب‌سازی ادغامی ‎(Merge Sort)‏ پیچیدگی زمانی در بدترین حالت: بدترین زمان مربوط به حالتی است که ... حلقه ۷۷۱16 در تابع 6 06۲9] به اتمام برسد در حالیکه ... پکی از ایند کس‌ها مانند 13 به مقدار 1 + 16108 برسد در حالیکه ایندکس دیگری مانند 0 برابر با 16108 باشد. چراکه عملیات اصلی (مقایسه المانها با هم) بیشترین تکرار را خواهد داشت 

صفحه 23:
ب) مرتب‌سازی ادغامی ‎(Merge Sort)‏ پیچیدگی زمانی در بدترین حالت: 3 0 3 S Resut) 1 0722027 19152225 10 2 10122027 13 162228 10 12 3 10722027 19152225 wee 4 0122027 13152225 10121316 5 10722027 1918225 1012191520 6 40122027 43162225 40 12 19 16 2022 7 100027 13182225 10 12 13 16 20 22 26 = 10122027 13.15 2225 [to 12 19 16 20 20 26 27 — Final values tome compared ao in boldface. Rams just exchanged appoar in squaioe Tnalyais of Worse Case Time Complexity (erga) 

صفحه 24:
ب) مرتب‌سازی ادغامی ‎(Merge Sort)‏ پیچیدگی زمانی در بدترین حالت: ‎W(n)=W(5)+W(F)+n‏ ‎+n‏ )3( ۲ < W(1)=0 

صفحه 25:
ب) مرتب‌سازی ادغامی ‎(Merge Sort)‏ تابع ييجيدكى (1)11 كه بصورت افزایشی است و شرایط زیر را درد را درنظر بگیرید: T(n)=aT (7) +en* form > 1, na power of b 20-4 که 2 < و 0 < 6 ثابت‌های صحیحی هستند و ۲ .2 و 6 ثابت‌هایی هستند که 0 <6 ,0 < 2و0 < 0 آزکام ‎Q(n*) 1] 6 > ۴‏ ۴ عم از ‎T(n)€¢ O(n*ign)‏ ‎O(n! +) if a > ۴‏ 

صفحه 26:
ب) مرتب‌سازی ادغامی ‎(Merge Sort)‏ در قضیه گفته شده داشتیم: ‎0۴٩‏ 000 ۵ 1,0 < 070 غم + () که - (7 20-0 O(nk) > 1) ٩ ۵) ‏ه 6 («ع۱‎ #۴ (nl) if a > *. همچنین چنانچه رابطه بازگشتی به دوصورت زیر تغییر کند: T(n) > aT (7) +enk or T(n) > a0 (F) ten, در این صورت نتایج با ‎“big O"‏ يا ؟ به جاى © تغيير خواهد کرد. 

صفحه 27:
ب) مرتب‌سازی ادغامی ‎(Merge Sort)‏ پیچیدگی زمانی در بدترین حالت: ‎n‏ ‎W (n= 2 (5) +n‏ 177 T(n)=aP (F) tent for n> 1, na power of} 1)1( 2 > معز مه ۴ 1 («و۱ )9 ‎6٩1‏ (12 ‎ifa > UA,‏ (مصم) و W (n) € O(nign). 

صفحه 28:
ج) مرتب‌سازی سريع 50۳0 > ‎Partition L‏ ‎Exchange Sort‏ فرض کنید آرایه زیر شامل لیستی از اعداد به صورت زیر باشد: ‎Pivot item‏ 1 25 20 10 12 27 13 22 15 آرايه را به گونه‌ای پارتیشن‌بندی می‌کنیم که تمامی المان‌های که کوچکتر از المان محوری هستند در سمت چپ آن و المان‌های بزرکتر از آن در سمت راستش قرار بگیرند Pivot item 1 1013 19 15 22_27 20 25 All smaller All larger ‏هرکدام از زیرآرایه‌ها را مرتب مى كنيم:‎ Pivot item 1 10713 12 15 20 22 25 27 Sorted Sorted 

صفحه 29:
)© ‏ج) مر تب‌سازی سربع ©5016 عاء أن‎ function [A,ppoint]=partition(A) len=length(A); pitem=A(1); ppoint=1,; for i=2:len if A(i)<pitem ppoint=ppoint+1; temp=A(ppoint);A(ppoint)=A(i);A(i)=temp; end end temp=A(1);A(1)=A(ppoint);A(ppoint)=temp; end 

صفحه 30:
)© ‏ج) مر تب‌سازی سربع ©5016 عاء أن‎ function S=quickSort(A) len=length(A); if (len>1) [A, ppoint]=partition(A); S(1:ppoint-1)=quickSort(A(1:ppoint-1)); S(ppoint)=A(ppoint); S(ppoint+1:len)=quickSort(A(ppoint+1:len)); else S=A; end end 

صفحه 31:
ج) مرتب‌سازی سریع 50۳6 ‎Quick‏ ‏تحلیل پیچیدگی زمانی در بدترین حالت: Tin)= 20 + ‏لمع + روج‎ Time to sort ‘Time to sort borg left subarray right subarray penis T(n)=T(n-1)+n-1 — forn>0 T(0)=0 ‏۳ج‎ as 2 

صفحه 32:
ج) مرتب‌سازی سریع 5070 0:6۷ تحلیل پیچیدگی زمانی در حالت میانگین: ‎Probability‏ pivotpoint is p 1 A(n) => 1 ]40-۱(+ ۸ -(( + 1 p= ۲ “— Time to Average time to a sort subarrays when partition pivotpoint is p 

صفحه 33:
ج) مرتب‌سازی سریع 5070 0:6۷ تحلیل پیچیدگی زمانی در حالت میانگین: « 21 (1 + ) نم () ۸ یکی از ویژگی‌های توابع لگاربتمی: ‎log, (2)‏ _ ‎log, (6)‏ = (n+ 1) 2(In2) (Ig n) = 1.38(n+1)lg n € O(nlg n) log, (x) 

صفحه 34:
ج) مرتب‌سازی سریع کوئیز از جلسه قبل) لطفا برای لیست [4 8 9 3 2 07 6 1 ۸<۶]5: الگوریتم مرتب‌سازی سریع را اجرا كنيد و ليست مرتب شده را بدست آورید. برای این منظور گام‌های شکل‌گیری تقسیم و حل را بر اساس دو الگوریتم 0016160۲ و 0۵۲1101 به صورت درخت ترسیم نمایید. توجه: نیازی به نشان دادن گام‌های الگوریتم 03۲1110۳ نمی‌باشد. بلکه در هر بخش از درخت تقسیم و حل نتیجه آن را بیاورید. 

صفحه 35:
Strassen's Matrix) ‏ضري مانرسوقاي استراسن‎ )5 (Multiplication فرض کنید که می‌خواهیم ماتریس :) که حاصلضرب دو ماتریس ۲۶۲ ۸۸ و 9 است را بدست آوریم. ‎bir bia‏ | پ | عده ره | ب زعت نت ‎C21 ۵ 021 2 boi boo ‏استراسن فرمول‌هایی به صورت زیر ارائه کده‌است که با بهرهگیری از آنها م‌توان ماتریس 2 را محاسبه نمود. ‎m, = (an +22) (1: +2) ned that if we let‏ ‎(a1 +22) br‏ ‎mg = a1 (biz ~ bea)‏ ‎bir)‏ ~ روا ويه = ‎ma‏ ‎ms = (a1 + 12) bee‏ ‎me = (a21 ~ 411) (bir + bia)‏ ‎(ba + bez),‏ (ووه - ‎‘mr = (a32‏ ‎ ‎ ‎oo 171 + 14 - 75 + mz 173 ۲ 5 ‏و171‎ ۰۴ ۵4 m, + ‏و۲ - و۷۷‎ + ۵ ‎ ‎ 

صفحه 36:
د) ضرب ماتریس‌های استراسن * این روش برای ماتریس‌های ۲۶۲ چندان جالب نیست فرمول‌های استراسن به گونه‌ای هستند که می‌توائیم ماتریس‌های بزرگتر رل به صورت افراز ۴ ماتریس کوچکتر در نظر كرفت 611 ۵2 ‏مه‎ | ۸ = (Aji + Aza) (Bu + Baz), 021 ۵ Au = “Ci = Mi + My — Ms + Mz اف 

صفحه 37:
د) ضرب ماتریس‌های استراسن 2 1 9 8 3456 7891] 2345 Rolas 

صفحه 38:
د) ضرب ماتریس‌های استراسن 1 = (an +n) (br + 0 ‏ما او | رن‎ mg = ani (bra — baa) ‏و1۲1‎ ۳ ۵ 7 ٩ ‏و1‎ - ۵ + ۵ amg = an (bas — b11) mg = (a1 + ‏و زمره‎ me = (a21 ~a11) (bx + Pra) mr = (012 ~ ax) (bar + bea), M, = (Ani + Agz) x (Bir + B22) ~([ee]+ Eee) (4-1) Lie) [75] 

صفحه 39:
د) ضرب ماتریس‌های استراسن Mi=sterasen(A11+A22,B11+B22); M2=sterasen(A21+A22,B11); M3=sterasen(A11,B12-B22); M4=sterasen(A22,B21-B11, M5= 16 M7 C11=M1+M4-M5+M7; 62 62 622 C(1:n/2,1:n/2)=C11; C(1:n/2,n/2+1:n) C1: C(n/2+1:n, C(n/2+1:n,n/2+1:n)=C22; end end function C=sterasen(A,B) max(size(A)); if ( A21=A(n/2+1:n,1:n/2); A22=A(n/2+1:n,n/2+1: B11=B(1:n/2,1:n/2); B12=B(1:n/2,n/2+1:n); B21=B(n/2+1:n,1:n/2); B22=B(n/2+1:n,n/2+1:n); 

صفحه 40:
د) ضرب ماتریس‌های استراسن تحلیل پیچیدگی زمانی تعداد جمع‌ها و تفریق‌ها در حالت معمول اين روش برای ضرب دو ماتریس ۲:۲, به ۷ عمل ضرب و ۱۸ عمل جمع و تفریق نیاز دارد T(r) =77 (2)+18(2)° form > 1, na power of 2 T(Q)=0 با توجه به قضیه خواهیم داشت: T (n) =€ Q (n?*') 

صفحه 41:
کوئیز از جلسه قبل) اگر فرمول‌های استراسن برای ضرب دو ماتریس ۲۸۲ به صورت زیر باشد. تابعی با نام 0 بنویسید که دو ماتریس ۸۵ و 8 را از ورودی بگیرد و حاصلضرب آن دو را در با شیوه تقسیم‌وحل برگرداند. 611 612 | _ | 611 2 x bir bia C21 C22 421 2 bai bea my = (an + 22) (Dus + baa) ma = (aa1 +429) br my = a1 (biz ~ bea) mg = ana (bay — bit) ms = (ani + a2) baa mg = (aan — 411) (Dir + ba) mz = (a12 — a2) (boi + boa), cau | mt ma—ms + mz ms + ms my +g my +m — mz +m 

صفحه 42:
۰) اعمال محاسباتی روی اعداد صحیح بزرگ انجام اعمال محاسباتی روی اعداد صحیحی که بزرگتر از حدی هستند که سخت‌افزار کامپیوتر مى تواند آنها را نمايش دهد. ماقي وى ولس يمني هقد بخ ‎Sy’‏ لاه زثاه لاه [قا5 [قاى نوشتن الگوریتمی با زمان خطى كه جمع و تفريق اعدادى صحيح با جنين ساختارى را انجام دهند مشکل نمی‌باشد. نمی: 

صفحه 43:
اعمال محاسباتی روی اعداد صحیح بزرگ ضرب اعداد صحیح بزرگ: ‎O87, x 103+ 832‏ 567,832 ‎digits 3 digits 3 digits‏ 223 + ههور ؤقدة _ 9,423,723 Tdigits 4 digits Sle = 6 y n u Ww x 10"+ ‏د‎ m=(=|. ndigits [n/2] digits [n/2) digits 2 

صفحه 44:
۰) اعمال محاسباتی روی اعداد صحیح بزرگ بنابراین چنانچه دو عدد با 1۱ رقم به صورت زیر داشته باشیم: + 10 2۲ ع به ‎٩4 2,‏ 10۳ < نا عدن در اين صورت ضرب آنها ,| به صورت زير مي توا ‎uv = («x 10" +y) 5 x ‏ول‎ +2) = aw x 10?" + (xz + wy) x 10™ + yz. ‏به عنوان مثال دو عدد زیر را در نظر بگیرید: ‎567,832 x 9, 423,723 = (567 x 10° + 832) (9423 x 10° + 723) = 567 x 9423 x 10° + (567 x 723 + 9423 x 832) x 10% + 832 x 723 ‎ ‎ 

صفحه 45:
ه) اعمال محاسباتی روی اعداد صحیح بزرگ function R=largeintProd(U,V) uy = (x x 10” + y) (w x 10" + 2) nulengtn(Uinv=tengen(rin=maxtlOu = ay x 10 4 (xe + wy) x 10 + ye ‏,2عو‎ %The value of threshold if (n<=s) result=U'V; else m=floor(n/2); [x y]=devision(U,m); [w,z]=devision(V,m); R=largeintSum( largelntsum( shift(largetntProd(x,w),2*m), shift(largeintSum(largeintProd(x,2),largeintProd(w,y)),m) » largeintProd(y.2) i end end 

صفحه 46:
۰) اعمال محاسباتی روی اعداد صحیح بزرگ تحلیل پیچیدگی زمانی در بدترین حالت: زمانی اتفاق می‌افتد که هیچکدام از دو عدد صحیح هیچ رقمی برابر صفر نداشته باشند. W(n)=4W(T)+or — forn > s, na power of 2 W(s)=0 T(n)=ar (F) en form > 1, na power of 5 20-0 ‏بر اساس قضیه بیان شده:‎ ‎O(n) >‏ “زا عم عز («ما ام 9 ( 2 ۰ <ه از (عصطم) و ‎W (n) ‏ع‎ 6 (n'84) = O(n’). ‎ ‎ 

صفحه 47:
۰ اعمال محاسباتی روی اعداد صحیح بزرگ بهبود: در تبع ۵۲961۳۱۳۲0۵0 که نوشته شد. می‌بایست سه مقدار زیر را محاسبه می‌کردیم .. ‎and yz‏ بلالا + ند ‎rw,‏ ‏كه عملا اين تابع به صورت بازگشتی می‌بایست چهار بار صدا زده می‌شد: ‎rw, 22 yw, and yz,‏ چنانچه تفییر متغیری به صورت زیر انجام دهیم ... آنگاه خواهیم داشت .. rz+yw =r— rw — yz. ‏در اين حالت برای محاسبات دیگر نیاز به چها ضرب نیست. بلکه تنها سه ضرب انجام‎ ‏می‌شود. هرچند که تعدادی جمع و ضرب انجام می‌شود ولی زمان آنها در محاسبات‎ ‏خطی است.‎ 

صفحه 48:
ه) اعمال محاسباتی روی اعداد صحیح بزرگ روج "10 عام حي تحليل بيجيدكى زمانى در بدترين حالت: به + "10 ع سحن زمانى أست كه هيج يك ازردو عدد صحيح رقمى برابر نا صفر نداشته باشند اكر ‎1١‏ توانی از ۲ باشد آنگاه ۰۷/۰۷۷ و 2 همكى 11/2 رقم خواهند داشت با توجه به مثالى كه در جدول زير آورده شده است: 7 x y kez Mumberotbigns inx4y 4 0 10 2 ‏ویو‎ ‎4 * 3 ‏الى هد‎ 8 000 1000 2000 ‏ویر‎ ‎0 00 000 1999 ‏بقع‎ ‏ین‎ n < digits inz+y< 5+ digits in w+2< 541 تاه خانم ‎IA‏ 

صفحه 49:
ه) اعمال محاسباتی روی اعداد صحیح بزرگ در آخرین الگوریتم ارائه شده ۳ بار فراخوانی ۲۵6 را داریم: ‎Input Size‏ ‎prod(x+y,w+z) %<inputsiee< B41 ۰ ۱‏ v=wxl0™ +2, prod2(x,w) vis ‏داد‎ prod2(y, z) همانند تحلیل پیچیدگی که برای حالتی که دارای ۴ بار فراخولنی ‎POM‏ 99 2549 عملیات‌ها نظیر 501۲0 و 501۴۴ دارای پیچیدگی زملنی خطی (17©) نسبت به 13 می‌باشند. aw G) +en SW (n) <3W G + 1) + ‏بنابراین رابطه زیر را داریم:‎ 

صفحه 50:
۰) اعمال محاسباتی روی اعداد صحیح بزرگ بر اساس قضیه بیان شده در ‎W (n) € Q (n'823) BW ($) ten SIV (n)‏ نشان مىدهيم كه در © + )+3( ‎W (n) € O (n'#29) W(n) <3W‏ يس درنيايت: (58لو) © بج ‎W (n) € 0 (nl823)‏ 

صفحه 51:
۰) اعمال محاسباتی روی اعداد صحیح بزرگ برای مرتبه پیچیدگی محاسباتی در 00 + (1 + )318 > (0)"#ایان می‌کنیم که (۰۱۸+۵+ ((۱ + )۵0۷ > + ۷ روم "ا ‎<3w (542) +en42c‏ ‎+en + 2c‏ )5( ۲ > براساس قضيه بيان شنده خواهيم ناشت ‎W1 (n) € O (n'°823)‏ و همجنين: W (n) = W’ (n — 2) € O (n*825) 

صفحه 52:
کوئیز از جلسه قبل) قف آخ ات قابرای ضرب اغذالا صحيج:يؤركك :با رويكرة تقسیم وخل الگوریتمی ارائه دهیم. رابطه زیر داده شده است: ‎uv = (x x 10" + y) (w x 10 + 2)‏ ‎aw x 10?" + (xz + wy) x 10" + yz‏ = الف) رابطه را به گونه‌ای تغییر دهید که در رابطه جدید پیچیدگی محاسباتی کاهش يابد. ب) سپس براساس رابطه (الف) تابعی با نام 0۲06 بنویسید که با رویکرد تقسیم‌وحل مساله را ضرب دو عدد صحیح بزرگ را حل می‌کند 

صفحه 53:
و) تعیین مقادیر آستانه فرآیند بازگشتی از لحاظ زمانی سربار به همراه دارد: ‎)١‏ قرار دادن پارامترها در پشته قبل از فراخوانی ۲ بازیابی پارامترها از پشته پس از پایان فراخوانی ن است که اگر مثلا می‌خواهيم ۸ عدد را مرتب کنیم آیا سربار اضافه شده ارزش به جاى ‎Metis GL Gp) O(N?)‏ از ( 0۳09 «مرتب سازی ادغامی) استفاده کنیم؟ بنابراین در این بخش روشی را بیان می‌کنیم که تعیین می‌کند که الگوریتم به ازای چه مقلدیری از (] (مقدار آستانه», آنقدر سریع است که دیگر نیاز به تقسیم کردن نمونه نباشد. 

صفحه 54:
و) تعيين مقادير آستانه جون تعيين مقدار آستانه به هزينه سربار مربوط مىشود. بنابراين تعيين مقدار آستانه به کامپیوتری بستگی دارد که برنامه در آن اجرا می‌شود پس از تعیین مقدار آستانه (۱۲65/۱0/01 می‌گویی برای ۸ > از الگوریتم بدون بازگشتی و برای ] < از روش بازگشتی (تقسیم‌وحل) استفاده می‌کنیم. 

صفحه 55:
و) تعیین مقادیر آستانه ‎w(n)=w(|5]) +W ([F]) +n-1.‏ فرض می‌کنیم روی کامپیوتر مورد نظر. زمانی که مرتب‌سازی ادغامی برای ۱- تقسیم (فرخوانی پشته) ۲- ترکیب (بازیابی مقادیر از پشته و 6 ۲06۲9) نياز دارد. 321145 باشد. مر + ([]) ۷+( رم ”از ‎forn<t‏ مراد ۱ ‎W(n) = 1 x‏ ‎W([E]) +0 ([§]) +32 us forn>t‏ 

صفحه 56:
و) تعیین مقادیر آستانه 3 ۳9 forn<t تحمس 20+ ‎wg) +0 (GD)‏ می‌خواهیم مقدار بهینه أ را پیدا کنیم. مقدار بهینه برای *. مقداری است که عبارت بالایی و پایینی را در معادله بالابه هم مساوی‌اند. چون و هر دواز * کوچکترند. پس زمان آنها از رابطه محاسبه می‌شود. ‎Jus 1)‏ هون لات ‎Lea‏ ات لقا لقان حل این معادله زمانیکه © زوج است با زمانیکه # فرد است متفاوت می‌باشد 

صفحه 57:
و) تعیین مقادیر آستانه پس یکبار فرض می‌کنیم که: زوج‌لستی عنی... پسراز حلمعادله داریم 2128 فردلستی عنی... پسراز حلعادله داییم 128.008 1 پس 2128 ‎ger $1‏ از حل معادله مفاهی ویر زا دست آوزیمه ‏] زوج‌لستی عنی.. يساز حلمعادله داييم 64 -] ‏6 فرد مسمتيعنى... يسراز حلمعادله داييم 70 -] ‏چون دو مقدار ] با هم برابر نيستند يس هيج مقدار آستانه‌ای وجود ندارد ‏اگر 9 عددی زوج بین ۶۴ و ۷۰ باشد باید یکبار دیگر تقسیم کرد و ‏اكر 13 عددی فرد بین ۶۴ و ۷۰ باشد از رویکرد بدون بازگشتی استفاده می‌کنیم ‎ ‎ ‎ 

صفحه 58:
کجا نمی‌توان از روش تقسیم‌وحل استفاده کرد؟ در موارد زیر باید از روش تقسیم و حل پرهیز کرد: ۱- نمونه‌ای به اندازه (] به دو يا چند نمونه به اندازه تقریبا (] تقسیم می‌شود ۲- نمونه‌ای به اندازه 0] به 0 نمونه به اندازه تقریبا ۲0/۴ (> مقدار ثابتی تقسیم می‌شود