دانلود پاورپوینت روش تقسيم و حل Divide and Conqure 2021

پاورپوینت روش تقسيم و حل Divide and Conqure

قسمتی از متن
 يک نمونه از مسأله را به دو يا چند قسمت کوچکتر تقسيم ميکند که معمولا نمونه هايی از مسأله اصلی هستند. اگر جواب مسأله های کوچکتر به راحتی محاسبه شود, می توان جواب نمونه  اصلی را با ترکيب اين جوابها به دست آورد, در غير اين صورت ميتوان آنها را به نمونه های کوچکتر تقسيم کرد . 
 يک روش بالا به پايين است. 
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;
  جستجوی دودويی
 مسأله: تعيين اين که آيا x در آرايه مرتب s با اندازه n وجود دارد يا خير.
مثال:n=14                                                                                                
-15,-6,0,7,9,23,54,82,101,112,125,131,142,151
x=9
low   high   mid    s[mid] 1        14       7           54
1         6        3         0
4       6        5         9       found
x=-14
Merge sort
مراحل مرتب سازی ادغامی برای آرايه ای با n عنصر:
       1. تقسيم آرايه به دو زير آرايه هريک با n/2 عضو
         2. حل هر زير آرايه با مرتب کردن آن. اگر آرايه به اندازه کافی کوچک نباشد, از بازگشت برای انجام اين کار استفاده می کنيم.
         3. ادغام زير آرايه های مرتب شده

فهرست مطالب:
روش تقسيم و حل Divide and Conqure
زمان محاسبه تابع DAndC
جستجوی دودويی
الگوريتم binary search
تحليل پيچيدگی زمانی الگوريتم binary search
Merge sort
مرتب سازی ادغامی
الگوريتم مرتب سازی ادغامی
الگوريتم ادغام
تحليل پيچيدگی زمانی الگوريتم mergesor
الگوريتم دوم مرتب سازی ادغامی (با صرفه جویی در فضا:n) 
مرتب سازی سریع   Quicksort
الگوریتم  Quicksort
روال تقسیم برای زیرآرایه A[p..r
تحلیل پیچیدگی زمان برای quicksor
اثبات درستی رابطه بدست آمده
مقایسه زمان متوسط برای الگوریتمهای mergesort و quicksort با ورودی های تصادفی
Quicksort به روش تصادفی
Partition به روش تصادفی
الگوریتم ضرب ماتریس Strassen
تحلیل پیچیدگی زمانی الگوریتم استراسن