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

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

اسلاید 1: روش تقسیم و حل (Divide and Conquer)

اسلاید 2: روش تقسیم و حل (Divide and Conquer)شیوه حل در این روش به این صورت است که:به صورت بازگشتی ...مساله به دو یا بیشتر زیر مساله از نوع همان مساله (یا مساله‌ای که در حل مساله اصلی مرتبط است) تقسیم (divide) می‌شود و ...اینکار (شکستن و تقسیم‌کردن) تا آنجایی ادامه می‌یابد که ...مساله به اندازه‌ای ساده شود که بتواند مستقیما حل شود (conquer). سپس ...پاسخ‌های زیرمساله‌ها با هم ترکیب می‌شوند تا پاسخی برای مساله اصلی فراهم سازند.

اسلاید 3: روش تقسیم و حل (Divide and Conquer)فهم و طراحی الگوریتم‌های D&C، مهارت پیچیده‌ای است که نیازمند فهم خوب از ماهیت مساله دارد.

اسلاید 4: روش تقسیم و حل (Divide and Conquer)توجه: به هنگام نوشتن الگوریتم‌های بازگشتی در سطح مسئله فکر می‌کنیم ومی‌گذاریم تا جزئیات را زبان برنامه نویسی با استفاده از Stack بر عهده گیردهنگام طراحی الگوریتم‌های تقسیم و حل معمولا همین گونه فکر می‌کنیم و آن را به صورت یک روال بازگشتی می‌نویسیم

اسلاید 5: روش تقسیم و حل (Divide and Conquer)برخی از مولفین می‌گویند که عنوان روش تقسیم و حل حتما می‌بایست به روش‌هایی تعلق گیرد که مساله را به دو یا بیشتر زیرمساله تقسیم می‌کند و ...چنانچه مساله به تنها یک زیرمساله دیگر شکسته شود به آن روش، کاهش و حل (Decrease and Conquer) می‌گویند.

اسلاید 6: کوئیز از جلسه قبل)تابع زیر را درنظر بگیرید:نشان دهید که:)الف()ب(

اسلاید 7: روش تقسیم و حلسابقه تاریخی علت نام‌گذاری این روش:در سال 1805، ارتشی از سربازان روسی و اتریشی با بیش از 15 هزار نفر به جنگ با ناپلئون آمدند.ناپلئون با حمله به قلب سپاه آنها و تقسیم نیروهای دشمن به دو بخش بر آنها پیروز شد.در واقع ناپلئون با تقسیم (Divide) سپاه بزرگ به دو سپاه کوچکتر و پیروز شدن بر تک‌تک آنها موفق شد بر آن سپاه بزرگ غبه یابد (Conquer)

اسلاید 8: الف) جستجوی دودوییاگر x برابر عنصر میانی آرایه بود جستجو تمام است. در غیر این صورت ...آرایه را به دو زیر آرایه تقسیم کن که هریک حدودا نصف آرایه اولیه‌اند.اگر x کوچکتر از عنصر میانی بود کار را در زیرآرایه چپی و اگر x بزرگتر از عنصر میانی بود، کار را در زیر آرایه راستی ادامه می‌دهیمحل مسئله را از حل مسئله زیر آرایه به دست آور

اسلاید 9: الف) جستجوی دودوییx=18

اسلاید 10: الف) جستجوی دودوییfunction position=recbinsearch(x,low,high) global A; mid=floor((low+high)/2); if (A(mid)==x) position=mid; else if x<A(mid) newlow=low; newhigh=mid-1; else newhigh=high; newlow=mid+1; end if (newhigh>=newlow) high=newhigh; low=newlow; position=recbinsearch(x,low,high); else position=0; end endendتوجه:برای تعریف متغیر به صورت عمومی به گونه‌ایکه در تمامی تابع‌ها قابل دسترسی باشد،ابتدا آن را عمومی تعریف می‌کنیم: global A;سپس مقداردهی می‌کنیم:A=[10 12 13 14 18 20 25 27 30 35 40 45 47];و سپس در هر تابعی قبل از استفاده، از تعریف عمومی آن استفاده می‌کنیم: global A;

اسلاید 11: الف) جستجوی دودوییتحلیل پیچیدگی در بدترین حالت:سوال) بدترین زمان کی رخ می‌دهد؟الف) المان مورد جستجو در لیست نباشد؟ب) المان مورد جستجو از تمامی المان‌های لیست بزرگتر باشد؟ mid=floor((low+high)/2); ….مثلا در لیست [1 2 3 4 5] چنانچه دنبال 6 بگردیم چند جستجو نیاز است؟دنبال 0 بگردیم چند جستجو نیاز است؟

اسلاید 12: الف) جستجوی دودوییتحلیل پیچیدگی در بدترین حالت:

اسلاید 13: الف) جستجوی دودوییاثبات پیچیدگی در بدترین حالت با استقرا:فرمول بازگشتی روبرو را درنظر بگیرید:برای تعدادی از n ها tn را می‌توانیم محاسبه کنیم:به نظر می‌رسد که رابطه زیر برقرار باشد:

اسلاید 14: الف) جستجوی دودوییاثبات پیچیدگی در بدترین حالت:با استقرا نشان می‌دهیم که این رابطه صحیح است. پایه استقرا: (برای n=1)فرض استقرا: فرض می‌کنیم برای n>0 دلخواهی که توانی از 2 است رابطه زیر برقرار باشد:

اسلاید 15: الف) جستجوی دودوییگام استقرا:به دلیل آنکه فرمول بازگشتی که به دنبال اثبات آن هستیم تنها برای اعدادی که توانی از 2 هستند مصداق دارد بنابراین ...عدد بعدی که بعد از n درنظر می‌گیریم باید ...2n باشد. بنابراین باید نشان دهیم که :چنانچه 2n را در رابطه بازگشتی قرار دهیم ...

اسلاید 16: الف) جستجوی دودوییتحلیل پیچیدگی در بدترین حالت:با استقرا نشان دادیم که رابطه زیر برای زمانیکه n، توانی از 2 باشد برقرار است:در حالت کلی چنانچه این شرط محدودکننده را برداریم رابطه زیر اثبات خواهد شد که:

اسلاید 17: ب) مرتب‌سازی ادغامی (Merge Sort)

اسلاید 18: ب) مرتب‌سازی ادغامی (Merge Sort)function result=merge(A,B) lena=max(size(A));lenb=max(size(B)); result=zeros(1,lena+lenb); ia=1;ib=1;k=1; while(ia<=lena && ib<=lenb) if A(ia)<B(ib) result(k)=A(ia); ia=ia+1; else result(k)=B(ib); ib=ib+1; end k=k+1; endif ia>lena result(k:lena+lenb)=B(ib:lenb); else result(k:lena+lenb)=A(ia:lena); endend

اسلاید 19: ب) مرتب‌سازی ادغامی (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); endend

اسلاید 20: روش تقسیم و حلکوئیز از جلسه قبل) با استقرا نشان دهید که پیچیدگی زمانی در الگوریتم جستجوی دودویی در بدترین حالت با روش تقسیم و حل برابر است با W(n)=logn+1(اثبات را برای زمانیکه nها توانی از 2 هستند انجام دهید)توجه: مراحل در شیوه اثبات استقرایی را با دقت بیان کنید.

اسلاید 21: ب) مرتب‌سازی ادغامی (Merge Sort)پیچیدگی زمانی در بدترین حالت:بدترین زمان مربوط به حالتی است که ...حلقه while در تابع merge به اتمام برسد در حالیکه ...یکی از ایندکس‌ها مانند ia به مقدار lena+1 برسد در حالیکه ایندکس دیگری مانند ib برابر با lenb باشد.چراکه عملیات اصلی (مقایسه المانها با هم) بیشترین تکرار را خواهد داشت

اسلاید 22: ب) مرتب‌سازی ادغامی (Merge Sort)پیچیدگی زمانی در بدترین حالت:

اسلاید 23: ب) مرتب‌سازی ادغامی (Merge Sort)پیچیدگی زمانی در بدترین حالت:

اسلاید 24: ب) مرتب‌سازی ادغامی (Merge Sort)قضیه: تابع پیچیدگی T(n) که بصورت افزایشی است و شرایط زیر را دارد را درنظر بگیرید:که b ≥ 2 و k ≥ 0 ثابت‌های صحیحی هستند و a، c و d ثابت‌هایی هستند که a > 0, c > 0 و d ≥ 0 آنگاه:

اسلاید 25: ب) مرتب‌سازی ادغامی (Merge Sort)در قضیه گفته شده داشتیم:همچنین چنانچه رابطه بازگشتی به دوصورت زیر تغییر کند:در این صورت نتایج با big O“ یا Ω به جای Θ تغییر خواهد کرد.

اسلاید 26: ب) مرتب‌سازی ادغامی (Merge Sort)پیچیدگی زمانی در بدترین حالت:

اسلاید 27: ج) مرتب‌سازی سریع (Quick Sort) یا Partition Exchange Sortفرض کنید آرایه زیر شامل لیستی از اعداد به صورت زیر باشد:آرایه را به گونه‌ای پارتیشن‌بندی می‌کنیم که تمامی المان‌های که کوچکتر از المان محوری هستند در سمت چپ آن و المان‌های بزرگتر از آن در سمت راستش قرار بگیرند:هرکدام از زیرآرایه‌ها را مرتب می‌کنیم:

اسلاید 28: ج) مرتب‌سازی سریع (Quick Sort)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

اسلاید 29: ج) مرتب‌سازی سریع (Quick Sort)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; endend

اسلاید 30: ج) مرتب‌سازی سریع (Quick Sort)تحلیل پیچیدگی زمانی در بدترین حالت: …

اسلاید 31: ج) مرتب‌سازی سریع (Quick Sort)تحلیل پیچیدگی زمانی در حالت میانگین:...

اسلاید 32: ج) مرتب‌سازی سریع (Quick Sort)تحلیل پیچیدگی زمانی در حالت میانگین:یکی از ویژگی‌های توابع لگاریتمی:...

اسلاید 33: ج) مرتب‌سازی سریعکوئیز از جلسه قبل)لطفا برای لیست A=[5 1 6 0 7 2 3 9 8 4]; الگوریتم مرتب‌سازی سریع را اجرا کنید و لیست مرتب شده را بدست آورید. برای این منظور گام‌های شکل‌گیری تقسیم و حل را بر اساس دو الگوریتم quickSort و partition به صورت درخت ترسیم نمایید.توجه: نیازی به نشان دادن گام‌های الگوریتم partition نمی‌باشد، بلکه در هر بخش از درخت تقسیم و حل نتیجه آن را بیاورید.

اسلاید 34: د) ضرب ماتریس‌های استراسن (Strassens Matrix Multiplication )فرض کنید که می‌خواهیم ماتریس C که حاصلضرب دو ماتریس 2*2 A و B است را بدست آوریم.استراسن فرمول‌هایی به صورت زیر ارائه کرده‌است که با بهره‌گیری از آنها می‌توان ماتریس C را محاسبه نمود.Strassen determined that if we let

اسلاید 35: د) ضرب ماتریس‌های استراسناین روش برای ماتریس‌های 2*2 چندان جالب نیستفرمول‌های استراسن به گونه‌ای هستند که می‌توانیم ماتریس‌های بزرگتر را به صورت افراز 4 ماتریس کوچکتر در نظر گرفت

اسلاید 36: د) ضرب ماتریس‌های استراسن

اسلاید 37: د) ضرب ماتریس‌های استراسن

اسلاید 38: د) ضرب ماتریس‌های استراسنfunction C=sterasen(A,B) n=max(size(A)); if (n==2) C=A*B; else A11=A(1:n/2,1:n/2); A12=A(1:n/2,n/2+1:n); A21=A(n/2+1:n,1:n/2); A22=A(n/2+1:n,n/2+1:n); 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); M1=sterasen(A11+A22,B11+B22); M2=sterasen(A21+A22,B11); M3=sterasen(A11,B12-B22); M4=sterasen(A22,B21-B11); M5= M6 M7 C11=M1+M4-M5+M7; C12 C21 C22 C(1:n/2,1:n/2)=C11; C(1:n/2,n/2+1:n)C12; C(n/2+1:n,1:n/2)=C21; C(n/2+1:n,n/2+1:n)=C22; endend

اسلاید 39: د) ضرب ماتریس‌های استراسنتحلیل پیچیدگی زمانی تعداد جمع‌ها و تفریق‌ها در حالت معمولاین روش برای ضرب دو ماتریس 2×2، به 7 عمل ضرب و 18 عمل جمع و تفریق نیاز داردبا توجه به قضیه خواهیم داشت:

اسلاید 40: کوئیز از جلسه قبل)اگر فرمول‌های استراسن برای ضرب دو ماتریس 2*2 به صورت زیر باشد، تابعی با نام sterasen بنویسید که دو ماتریس A و B را از ورودی بگیرد و حاصلضرب آن دو را در C با شیوه تقسیم‌وحل برگرداند.

اسلاید 41: ه) اعمال محاسباتی روی اعداد صحیح بزرگانجام اعمال محاسباتی روی اعداد صحیحی که بزرگتر از حدی هستند که سخت‌افزار کامپیوتر می‌تواند آنها را نمایش دهد.نوشتن الگوریتمی با زمان خطی که جمع و تفریق اعدادی صحیح با چنین ساختاری را انجام دهند مشکل نمی‌باشد.

اسلاید 42: ه) اعمال محاسباتی روی اعداد صحیح بزرگضرب اعداد صحیح بزرگ:

اسلاید 43: ه) اعمال محاسباتی روی اعداد صحیح بزرگبنابراین چنانچه دو عدد با n رقم به صورت زیر داشته باشیم:در این صورت ضرب آنها را به صورت زیر می‌توان نوشت:به عنوان مثال دو عدد زیر را در نظر بگیرید:

اسلاید 44: ه) اعمال محاسباتی روی اعداد صحیح بزرگfunction R=largeIntProd(U,V) nu=length(U);nv=length(V);n=max([nu nv]); s=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( largeIntSum( shift(largeIntProd(x,w),2*m), shift(largeIntSum(largeIntProd(x,z),largeIntProd(w,y)),m) ), largeIntProd(y,z) ); endend

اسلاید 45: ه) اعمال محاسباتی روی اعداد صحیح بزرگتحلیل پیچیدگی زمانی در بدترین حالت: زمانی اتفاق می‌افتد که هیچکدام از دو عدد صحیح هیچ رقمی برابر صفر نداشته باشند.بر اساس قضیه بیان شده:

اسلاید 46: ه) اعمال محاسباتی روی اعداد صحیح بزرگبهبود:در تابع largeIntProd که نوشته شد، می‌بایست سه مقدار زیر را محاسبه می‌کردیم ...که عملا این تابع به صورت بازگشتی می‌بایست چهار بار صدا زده‌ می‌شد:چنانچه تغییر متغیری به صورت زیر انجام دهیم ...آنگاه خواهیم داشت ...در این حالت برای محاسبات دیگر نیاز به چها ضرب نیست. بلکه تنها سه ضرب انجام می‌شود. هرچند که تعدادی جمع و ضرب انجام می‌شود ولی زمان آنها در محاسبات خطی است.

اسلاید 47: ه) اعمال محاسباتی روی اعداد صحیح بزرگتحلیل پیچیدگی زمانی در بدترین حالت:زمانی است که هیچ یک از دو عدد صحیح رقمی برابر با صفر نداشته باشنداگر n توانی از 2 باشد آنگاه x، y، w و z همگی n/2 رقم خواهند داشتبا توجه به مثالی که در جدول زیر آورده شده است:

اسلاید 48: ه) اعمال محاسباتی روی اعداد صحیح بزرگدر آخرین الگوریتم ارائه شده 3 بار فراخوانی prod را داریم:همانند تحلیل پیچیدگی که برای حالتی که دارای 4 بار فراخوانی prod بود، دیگر عملیات‌ها نظیر sum و shift دارای پیچیدگی زمانی خطی (cn) نسبت به n می‌باشند.بنابراین رابطه زیر را داریم:

اسلاید 49: ه) اعمال محاسباتی روی اعداد صحیح بزرگبر اساس قضیه بیان شده در داریم: همچنین نشان می‌دهیم که در داریم: پس در نهایت:

اسلاید 50: ه) اعمال محاسباتی روی اعداد صحیح بزرگبرای مرتبه پیچیدگی محاسباتی در اینگونه بیان می‌کنیم که ...بر اساس قضیه بیان شده خواهیم داشت: و همچنین:

اسلاید 51: کوئیز از جلسه قبل)هدف آن است تا برای ضرب اعداد صحیح بزرگ با رویکرد تقسیم‌وحل الگوریتمی ارائه دهیم. رابطه زیر داده شده است:الف) رابطه را به گونه‌ای تغییر دهید که در رابطه جدید پیچیدگی محاسباتی کاهش یابد. ب) سپس براساس رابطه (الف) تابعی با نام prod بنویسید که با رویکرد تقسیم‌وحل مساله را ضرب دو عدد صحیح بزرگ را حل می‌کند

اسلاید 52: و) تعیین مقادیر آستانهفرآیند بازگشتی از لحاظ زمانی سربار به همراه دارد:1) قرار دادن پارامترها در پشته قبل از فراخوانی2) بازیابی پارامترها از پشته پس از پایان فراخوانیبنابراین بحث این است که اگر مثلا می‌خواهیم 8 عدد را مرتب کنیم آیا سربار اضافه شده ارزش آن را دارد که:به جای Ɵ(n2) (مرتب سازی تعویضی)،از Ɵ(nlog n) (مرتب سازی ادغامی) استفاده کنیم؟بنابراین در این بخش روشی را بیان می‌کنیم که تعیین می‌کند که الگوریتم به ازای چه مقادیری از n (مقدار آستانه)، آنقدر سریع است که دیگر نیاز به تقسیم کردن نمونه نباشد.

اسلاید 53: و) تعیین مقادیر آستانهچون تعیین مقدار آستانه به هزینه سربار مربوط می‌شود، بنابراین تعیین مقدار آستانه به کامپیوتری بستگی دارد که برنامه در آن اجرا می‌شودپس از تعیین مقدار آستانه (threshold) می‌گویی برای n<=t از الگوریتم بدون بازگشتی و برای n>t از روش بازگشتی (تقسیم‌وحل) استفاده می‌کنیم.

اسلاید 54: و) تعیین مقادیر آستانهفرض می‌کنیم روی کامپیوتر مورد نظر، زمانی‌که مرتب‌سازی ادغامی برای1- تقسیم (فراخوانی پشته)2- ترکیب (بازیابی مقادیر از پشته و merge)نیاز دارد، 32nµs باشد.پس:

اسلاید 55: و) تعیین مقادیر آستانهمی‌خواهیم مقدار بهینه t را پیدا کنیم.مقدار بهینه برای t، مقداری است که عبارت بالایی و پایینی را در معادله بالا به هم مساوی‌اند. چون و هر دو از t کوچکترند، پس زمان آنها از رابطه محاسبه می‌شود.حل این معادله زمانیکه t زوج است با زمانیکه t فرد است متفاوت می‌باشد

اسلاید 56: و) تعیین مقادیر آستانهپس یکبار فرض می‌کنیم که: t زوج است، یعنی .... پس از حل معادله داریم t=128t فرد است، یعنی .... پس از حل معادله داریم t=128.008پس t=128اگر پس از حل معادله مقادیر زیر را بدست آوریم: t زوج است، یعنی .... پس از حل معادله داریم t=64t فرد است، یعنی .... پس از حل معادله داریم t=70چون دو مقدار t با هم برابر نیستند پس هیچ مقدار آستانه‌ای وجود ندارداگر n عددی زوج بین 64 و 70 باشد باید یکبار دیگر تقسیم کرد واگر n عددی فرد بین 64 و 70 باشد از رویکرد بدون بازگشتی استفاده می‌کنیم

اسلاید 57: کجا نمی‌توان از روش تقسیم‌وحل استفاده کرد؟در موارد زیر باید از روش تقسیم و حل پرهیز کرد:1- نمونه‌ای به اندازه n به دو یا چند نمونه به اندازه تقریبا n تقسیم می‌شود2- نمونه‌ای به اندازه n به n نمونه به اندازه تقریبا n/c (c مقدار ثابتی است) تقسیم می‌شود