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

بخشی از پاورپوینت

اسلاید 2 :

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

اسلاید 3 :

فهم و طراحی الگوریتمهای D&C، مهارت پیچیدهای است که نیازمند فهم خوب از ماهیت مساله دارد.

اسلاید 4 :

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

اسلاید 5 :

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

اسلاید 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 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
end
end
توجه:
برای تعریف متغیر به صورت عمومی به گونهایکه در تمامی تابعها قابل دسترسی باشد،
ابتدا آن را عمومی تعریف میکنیم:
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) result(k)=A(ia);
ia=ia+1;
else
result(k)=B(ib);
ib=ib+1;
end
k=k+1;
end
if ia>lena
result(k:lena+lenb)=B(ib:lenb);
else
result(k:lena+lenb)=A(ia:lena);
end
end

اسلاید 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);
end
end

اسلاید 20 :

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