نوع فایل: power point

قابل ویرایش 37 اسلاید

قسمتی از اسلایدها:

• يک نمونه از مسأله را به دو يا چند قسمت کوچکتر تقسيم ميکند که معمولا نمونه هايی از مسأله اصلی هستند. اگر جواب مسأله های کوچکتر به راحتی محاسبه شود, می توان جواب نمونه اصلی را با ترکيب اين جوابها به دست آورد, در غير اين صورت ميتوان آنها را به نمونه های کوچکتر تقسيم کرد .
• يک روش بالا به پايين است.

Algorithm DAndC(P)

{ if Small(P) return Solve(P);

else

{ divide P into smaller instances P1,P2,…,Pk, k>=1;

Apply DAndC to each of these subproblems;

return Combine(DAndC(P1),DAndC(P2),…,DAndC(Pk);

فهرست مطالب و اسلایدها:

روش تقسيم و حل Divide and Conqure

زمان محاسبه تابع DAndC

جستجوی دودويی

الگوريتم binary search

تحليل پيچيدگی زمانی الگوريتم binary search

Merge sort

مرتب سازی ادغامی

الگوريتم مرتب سازی ادغامی

الگوريتم ادغام

تحليل پيچيدگی زمانی الگوريتم mergesort

تحليل پيچيدگی فضا الگوريتم mergesort

الگوريتم دوم مرتب سازی ادغامی (با صرفه جویی در فضا:n)

الگوريتم ادغام

مرتب سازی سریع Quicksort

الگوریتم Quicksort

روال تقسیم برای زیرآرایه A[p..r]

اجرای روال partition

تحلیل پیچیدگی زمان برای quicksort

اثبات درستی رابطه بدست آمده:

تحلیل پیچیدگی حالت میانی الگوریتم quicksort

Quicksort به روش تصادفی

Partition به روش تصادفی

الگوریتم ضرب ماتریس Strassen

ضرب ماتریس 2×2 به روش استراسن

مثال ضرب ماتریس با روش تقسیم و حل

روش تقسیم و حل برای ضرب ماتریس

مثالی از ضرب ماتریس با روش تقسیم و حل

ضرب ماتریس n×n به روش استراسن با تقسیم و حل

مثالی از ضرب ماتریس n×n به روش استراسن با تقسیم و حل

الگوریتم ضرب ماتریس به روش strassen

تحلیل پیچیدگی زمانی الگوریتم استراسن