صفحه محصول - پاورپوینت روش تقسیم و حل در طراحی الگوریتم ها

پاورپوینت روش تقسیم و حل در طراحی الگوریتم ها (pptx) 18 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 18 اسلاید

قسمتی از متن PowerPoint (.pptx) :

روش تقسیم و حل در طراحی الگوریتم ها به نام خدا 2 طراحی الگوریتم ها – اسلاید سوم – صفحه روش تقسیم و حل ناپلئون، امپراتور فرانسه، در یکی از جنگ ها وقتی دید تعداد دشمنان بسیار بیشتر از افراد خود است از روش جالبی استفاده کرد. ناپلئون به قلب سپاه حمله کرد و نیروها را به دو بخش تقسیم کرد. از آنجا که هر یک از دو بخش سپاه به تنهایی از پس ناپلئون بر نمی آمدند، بر آنها تلفات سنگینی وارد آمد. ناپلئون با تقسیم سپاه بزرگ به دو سپاه کوچک تر و پیروز شدن بر تک تک آن ها توانست بر سپاه بزرگ غلبه کند. 3 طراحی الگوریتم ها – اسلاید سوم – صفحه روش تقسیم و حل (Divide and Conquer) یکی از روش های طراحی الگوریتم ، روش تقسیم و حل است: این روش، مسئله را به نمونه های کوچک تر تقسیم میکند، آنقدر این کار را ادامه میدهد تا بتوان نمونه های کوچک شده را به راحتی حل کرد. حل مسئله اصلی از ترکیب کردن همین حل های کوچکتر بدست می آید. روش تقسیم و حل یک روش بالا به پایین است. زیرا برای حل یک نمونه سطح بالا از مسئله، با رفتن به پایین و به دست آوردن حل نمونه های کوچک تر حاصل میشود. 4 طراحی الگوریتم ها – اسلاید سوم – صفحه روش تقسیم و حل (Divide and Conquer) روش تقسیم و حل شامل مراحل زیر است: 1- تقسیم نمونه ای از یک مسئله به یک یا چند نمونه کوچک تر. 2- حل هر نمونه کوچکتر. اگر نمونه های کوچک تر به قدر کافی کوچک نبودند، برای این منظور از بازگشت استفاده کنید. 3- در صورت نیاز، حل نمونه های کوچک تر را ترکیب کنید تا حل نمونه اولیه بدست آید. 5 طراحی الگوریتم ها – اسلاید یکم – صفحه یادآوری الگوریتم جستجوی دودویی   start end mid همانطور که ملاحظه میکنید، الگوریتم جستجوی دودویی که در درس های قبل دیدیم، دقیقا یک مثال از روش تقسیم و حل است. 6 طراحی الگوریتم ها – اسلاید سوم – صفحه روش مرتب سازی ادغامی (Merge Sort) یکی از روش های مرتب سازی که به روش تقسیم و حل کار میکند، روش مرتب سازی ادغامی است. در این روش آرایه را بطور مکرر تقسیم میکنیم تا به زیرآرایه های یک عنصری برسیم. پس از آن زیرآرایه ها دو به دو با هم بصورت مرتب شده ادغام میشوند و این کار تا جایی که حل کل مسئله بدست آید ادامه می یابد. 1 2 3 4 5 7 8 9 7 طراحی الگوریتم ها – اسلاید سوم – صفحه مثال دیگر از روش مرتب سازی ادغامی 8 طراحی الگوریتم ها – اسلاید سوم – صفحه مثال دیگر از روش مرتب سازی ادغامی در تصویر زیر روش مرتب سازی ادغامی بصورت تصویر متحرک نشان داده شده است. 9 طراحی الگوریتم ها – اسلاید سوم – صفحه پیچیدگی زمانی در بدترین حالت برای الگوریتم مرتب سازی ادغامی