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

1-در این مطلب، متن اسلاید های اولیه دانلود پاورپوینت روش های حل مسئله ، تقسیم و حل قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 12 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

اسلاید ۱ :

               یکی از روش های حل مسئله ، تقسیم و حل است . اساس این روش به صورت حل بالا به پایین ( 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 کوچک تر باشد مرتبه زمانی کمتر خواهد بود . پس با توجه به اینکه ۲≤k≤n ،  k بهینه برابر ۲ است.

اسلاید ۷ :

مسئله ۲

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

اسلاید ۸ :

حل

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

اسلاید ۹ :

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

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

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

اسلاید ۱۰ :

مثال

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