تقسيم-و-ﻏﻠﺒﻪ (Divide-and-Conquer)

توضیحات

در جلسه بیستم درس طراحی الگوریتم دکتر حمید حاج سیدجوادی که اهمیت به سزایی در کنکور ارشد کامپیوتر و کنکور ارشد آی تی و نیز کنکور دکتری کامپیوتر و کنکور دکتری آی تی دارد، مطالب مهمی درباره مبحث تقسيم-و-ﻏﻠﺒﻪ (Divide-and-Conquer) ارائه می‌شود. ابتدا روش تقسیم-و-غلبه به عنوان یک روش برای طراحی الگوریتم‌های کارآمد شرح داده می‌شودو مثال Binary search در مورد آن زده می‌شود. سپس مسئله ضرب دو چندجمله‌ای بزرگ (با درجه بزرگ) شرح داده می‌شود. بعد از آن مسئله ضرب ماتریس‌های مربعی به روش تقسیم-و-غلبه تدریس می‌شود. آنگاه الگوریتم استراسن (Strassen’s algorithm) تشریح می‌گردد. پس از آن مرتب‌سازی ادغامی (Merge sort) به روش تقسیم-و-غلبه تشریح می‌شود. آنگاه مبحث مرتب سازی سریع (Quick sort) به روش تقسیم-و-غلبه تدریس می‌شود و پارتیشن‌بندی آرایه مورد بحث قرار داده می‌شود. کارایی مرتب سازی سریع (Quick sort) وپارتیشن‌بندی در بدترین حالت، بهترین حالت و متعادل مورد بحث و بررسی قرار می‌گیرند. مسئله یافتن k امین کوچکترین عنصر در یک آرایه دلخواه n عنصری مطرح و شرح داده می‌شود. در انتها 11 تست کنکور ارشد و دکترای طراحی الگوریتم در خصوص مطالب این جلسه مطرح و حل تشریحی آنها ارائه می‌گردد.