بخشی از پاورپوینت
اسلاید 1 :
طراحي الگوريتم ها
Computer algorithms
فصل چهارم
تقسم و حل
اسلاید 2 :
Computer algorithms
مساله مرتب سازی ادغام
مساله مرتب سازی سریع
مساله ضرب ماتریس استراسن
اسلاید 3 :
حل مسأله مرتبسازي ادغام به روش تقسيم و حل
فرض كنيد ليست نامرتبي با n عنصر داريم كه ميخواهيم اين ليست را به ترتيب صعودي مرتب كنيم.
در عمل combine هم مرتب سازی و هم ترکیب صورت می گیرد
اسلاید 4 :
ليست زير را با استفاده از الگوريتم merge sort مرتب كنيد
حل: ابتدا ليست اعداد را به صورت زير در آرايهاي قرار ميدهيم:
اسلاید 5 :
الف) براي مرتب كردن ليست فوق درخت فراخوانيهاي تابع mergesort به صورت زير ميباشد:
تعداد كل فراخوانيها برابر با تعداد small (p) ها + تعداد merge ها يعني 10 + 9 = 19 مي باشد.
تعداد فراخواني بازگشتي برابر 18 است .
اسلاید 6 :
دومين مقايسه در آخرين merge انجام شده ، مقايسه (285 , 254) ميباشد.
اولين مقايسه در آخرين merge انجام شده، مقايسه (179 , 254) ميباشد.
اسلاید 7 :
پيچيدگي الگوريتم merge sort
اسلاید 8 :
حل مسأله مرتبسازي سريع به روش تقسيم و حل
☺به عنوان مثال فرض كنيد آرايه حاوي عناصر زير باشد. نحوه عمل مرتبسازي سريع را نشان ميدهيم:
1- ابتدا محل واقعی عنصر اول یعنی 15 را در لیست مرتب مشخص میکنیم:
اسلاید 9 :
الگوريتم Quick Sort
فرض كنيد آرايه اي با نام a داريم كه تعداد عناصر آن n مي باشد و مي خواهيم اين عناصر را به ترتيب صعودي مرتب كنيم.
براي اينكار ميتوان از الگوريتم زير استفاده نمود:
مقایسه ها در تابع partition انجام می شود و در ضمن تابع combine هم نداریم
وظيفه تابع partition پيدا كردن انديس عنصري مانند K است كه تمام عناصر قبل از آن
كوچكتر از K و تمام عناصر بعد از آن بزرگتر از K ميباشند.
اسلاید 10 :
تابع partition براي تقسيم ليست
خروجي الگوريتم partition انديس عنصر محور (v)خواهد بود.
تعداد مقايسه ها در الگوريتم پارتيشن n – 1 مي باشد.
الگوريتم partition در هر مرحله چندين جابجايي عناصر در ليست انجام ميدهد.
تعداد جابجاييها در الگوريتم پارتيشن به چگونگي قرار گرفتن عناصر ليست نامرتب بستگي دارد.
پيچيدگي الگوريتم partition از مرتبه O(n) مي باشد.
در هر مرحله كه الگوريتم اجرا ميشود، يكي از عناصر در جاي اصلي خود fix خواهد شد.
اسلاید 11 :
ليست زير را با استفاده از الگوريتم Quick Sort مرتب كنيد.
جواب:
اولين فراخواني به صورت QuickSort( 1 , 7 ) مي باشد. عنصر محور پيدا كرده و ليست را به دو قسمت تقسيم ميكنيم:
اولين اجراي تابع partition براي مشخص كردن محل دقيق عنصر 65 در ليست ميباشد، در اين فراخواني جابجايي هاي زير انجام ميشود:
1) تعويض 75 و 50
2) تعويض 85 و 55
3) تعويض 55 و عنصر محور
اسلاید 14 :
مرتبه زماني الگوريتم Quick Sort در حالت متوسط
فرض ميكنيم عناصر آرايه به طور تصادفي توليد شوند،
بنابراين احتمال آنكه عنصر محور بازگردانده شده، توسط تابع partition ، هر يك از اعداد 1 تا n باشد، يكسان است.
اثبات کامل رابطه فوق به عهده دانشجو مي باشد.؟
متوسط = n/2
اسلاید 15 :
مرتبه زماني الگوريتم Quick Sort در حالت متوسط
فرض ميكنيم عناصر آرايه به طور تصادفي توليد شوند،
بنابراين احتمال آنكه عنصر محور بازگردانده شده، توسط تابع partition ، هر يك از اعداد 1 تا n باشد، يكسان است.
متوسط = n/2
T(n) = T(n/2)+ T(n/2)+ O(n)
اسلاید 16 :
مرتبه زماني الگوريتم Quick Sort در بدترين شرايط
در الگوريتم Quick Sort ، بدترين حالت هنگامي رخ ميدهد كه آرايه از قبل مرتب شده باشد. (به صورت صعودی)
T(0) : زمان لازم براي مرتبسازي زيرآرايه طرف چپ
T(n – 1) : زمان لازم براي مرتبسازي زيرآرايه طرف راست
n – 1 : زمان لازم براي افراز (Partition) . در تابع پارتيشن حداكثرn – 1 مقايسه انجام مي شود.
اسلاید 17 :
ضرب سريع ماتريس استراسن به روش تقسيم و حل
روش استراسن در مورد ضرب ماتریس های 2×2 ارزش چندانی ندارد.
تعیین حاصلضرب دو ماتریس n ×n که در آن n توانی از 2 است
پیچیدگی این الگوریتم از لحاظ تعداد ضرب، جمع و تفریق مورد نیاز کمتر از روش استاندارد است.
اسلاید 19 :
حل مسأله ضرب سريع ماتريس استراسن به روش تقسيم و حل
حاصل ضرب دو ماتريس 2 × 2 يك ماتريس 2 × 2 است كه به صورت زير نشان داده ميشود:
مؤلفههاي حاصل عبارتند از:
استراسن معين كرد كه اگر فرض كنيم:
حاصل ضرب C به صورت زير داده ميشود: دیده می شود که تعداد ضرب ها 7 است
اسلاید 20 :
به همين شيوه M2 تا M7 را محاسبه ميكنيم، سپس رابطه زير را بدست ميآوريم و با استفاده از فرمول استراسن خواهیم داشت :
