پاورپوینت کامل روش‌های حل مسئله با رویکرد تقسیم و حل و کاربرد آنها در طراحی الگوریتم‌ها

توجه : این پروژه به صورت فایل power point (پاور پوینت) ارائه میگردد

 پاورپوینت کامل روش‌های حل مسئله با رویکرد تقسیم و حل و کاربرد آنها در طراحی الگوریتم‌ها دارای ۵۴ اسلاید می باشد و دارای تنظیمات کامل در Power Point می باشد و آماده پرینت یا چاپ است

فایل پاور پوینت پاورپوینت کامل روش‌های حل مسئله با رویکرد تقسیم و حل و کاربرد آنها در طراحی الگوریتم‌ها  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

---

لطفا به نکات زیر در هنگام خرید

دانلودپاورپوینت کامل روش‌های حل مسئله با رویکرد تقسیم و حل و کاربرد آنها در طراحی الگوریتم‌ها

توجه فرمایید.

۱-در این مطلب، متن اسلاید های اولیه 

دانلودپاورپوینت کامل روش‌های حل مسئله با رویکرد تقسیم و حل و کاربرد آنها در طراحی الگوریتم‌ها

قرار داده شده است

۲-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید

۳-پس از پرداخت هزینه ، حداکثر طی ۱۲ ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد

۴-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد

۵-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار داده نشده است

---

بخشی از متن پاورپوینت کامل روش‌های حل مسئله با رویکرد تقسیم و حل و کاربرد آنها در طراحی الگوریتم‌ها :

اسلاید ۱ :

               یکی از روش های حل مسئله ، تقسیم و حل است . اساس این روش به صورت حل بالا به پایین ( Top down ) است .در این روش مسئله ای با سایز بزرگ را آن قدر کوچک می کنیم که حل آن مقدور یا بدیهی شود . سپس از ترکیب زیر مسائل حل شده    به حل مسئله اصلی می رسیم.

    استفاده از این روش در طراحی الگوریتم ممکن است به یکی از دلایل زیر باشد :

.۱حل مسئله با روش دیگری امکان پذیر نباشد

.۲الگوریتم آن نسبت به روش های دیگر کارا تر باشد.

    اما قبل از اعمال این روش باید به چند سوال پاسخ دهیم:

.۱مسئله اصلی را به چند زیر مسئله تقسیم کنیم ؟

.۲هر زیر مسئله چه سایزی داشته باشد؟ ( زیر مسائل هم اندازه باشند یا خیر؟ )

.۳نوع شکستن (از بالا به پایین مسئله شکسته شود یا از پایین به بالا زیر مسائل کوچکتر ترکیب شوند.)

اسلاید ۲ :

الگوریتم کلی تقسیم و حل :

الگوریتم DandC در آغاز به صورت DandC (P) فراخوانی می شود . که در آن P مسئله اصلی است که می بایست حل شود . Small(P) بررسی می کند که مسئله به اندازه کافی کوچک است که بتوان آنرا مستقیماً حل کرد یا خیر . اگر نتیجه کار مثبت باشد زیر مسئله P محاسبه می شود .) مثلاً توسط تابعی به نام S(P) ) .

در غیر این صورت مسئله P به زیز مسئله های کوچکتر تقسیم می شود . حاصل اینکار تولید زیر مسئله های  , P2 , P1 ;  ,  Pk می باشد که حاصل بازگشت های پی در پی می باشد . در نهایت تابع Combine برای ترکیب راه حل های زیر مسئله برای محاسبه راه حل مسئله اصلی به کار می رود .

اسلاید ۳ :

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

    هدف این مسئله جست و جوی کلید در یک آرایه مرتب است .

         در حل این مسئله از روش تقسیم و حل استفاده می شود به صورتی که ابتدا یک آرایه n عنصری رابه دو قسمت مساوی تقسیم کرده و کلیدرابا عنصر وسط آرایه مقایسه می کنیم اگر مساوی بود که مسئله حل شده است در غیر این صورت با توجه به کوچک تر یا بزرگ تر بودن کلید این روند را در یکی از نیم آرایه های  چپ یا راست ادامه می دهیم.

         الگوریتم جست و جوی دودویی به روش بازگشتی را در ادامه پس از مثال مشاهده    می کنید .

اسلاید ۴ :

بررسی مرتبه زمانی الگوریتم جست و جوی دودویی

در این مسئله ،یک آرایه n عنصری را با انجام یک مقایسه به دو زیر مسئله دیگر تقسیم می کنیم اما فقط یکی از این زیر مسائل را حل می کنیم بنابراین داریم

1. T) n ( = T ) n /2 ( +1 O ) logn (

اسلاید ۵ :

مسئله ۱

اگر در مسئله جست وجوی کلید ، آرایه را به k  قسمت تقسیم کنیم مقدار k را برای بهینه شدن مرتبه زمانی به دست آورید؟

اسلاید ۶ :

حل

اگر مسئله را به k قسمت مساوی تقسیم کنیم داریم :

1. T) n ( = T) n/k ( + k-1
2. O) lognk (

اما ضریب log nk در مرتبه زمانی برای ما اهمیت دارد. با توجه به اینکه در هر سطح از درخت جست و جو در بدترین حالت نیاز به k-1 مقایسه داریم در نتیجه ضریب مرتبه زمانی برابر k-1 است .

1. T) n ( = ) k-1( lognk = ) k-1(

با توجه به اینکه k یک عدد طبیعی است و با افزایش آن میزان رشد k-1 بیشتر از log k است در نتیجه هر چه k کوچک تر باشد مرتبه زمانی کمتر خواهد بود . پس با توجه به اینکه ۲kn ،  k بهینه برابر ۲ است.

اسلاید ۷ :

مسئله ۲

آیا برابر بودن سایز زیر مسائل در کمتر شدن مرتبه زمانی مسئله جست و جوی کلید مفید است یا خیر؟

اسلاید ۸ :

حل

اگر آرایه را به دو قسمت با سایز های مختلف تقسیم کنیم احتمال اینکه کلید مورد نظر در قسمت بزرگ تر قرار بگیرد بیشتر است. در نتیجه ما مجبوریم در اکثر مراحل آرایه ای با سایز مثلا ۷۰%  ورودی را جستجو کنیم که این مناسب نیست زیرا در مسئله جست و جوی  دودویی کلید ، در هر مرحله تنها ۵۰% آرایه جستجو می شود .  

اسلاید ۹ :

مرتب سازی به روش D & C :

می خواهیم مسئله مرتب سازی را با استفاده از روش تقسیم و حل ، حل کنیم. به نحوی که در هر مرحله مسئله را به دو زیر مسئله دیگر تقسیم می کنیم .دراین مرتب سازی ابتدا عنصری را به عنوان محور در نظر گرفته سپس دو زیر مسئله تشکیل می دهیم به نحوی که یکی از این زیر مسائل حاوی عناصر کوچک تر از محور و دیگری حاوی عناصر بزرگ تر از محور با شد. زیر مسائل تشکیل شده را به روش مشابه حل می کنیم.

 این روش مرتب سازی را  مرتب سازی quick sort  گویند .

اسلاید ۱۰ :

مثال

        در آرایه A عنصر۱۰ را به عنوان عنصر محوری انتخاب می کنیم. با فراخوانی تابع Quick Sort تمام اعداد کوچکتر از عنصر محور (۱۰) سمت چپ آن و اعداد بزرگتر از آن در سمت راست قرار می گیرند. سپس در آرایه سمت چپ و راست عناصر محوری انتخاب شده و برای هر کدام تابع Quick Sort  فراخوانی می شود.