دانلود پاورپوینت روش های حل مسئله ، تقسیم و حل

PowerPoint قابل ویرایش
54 صفحه
11900 تومان
119,000 ریال – خرید و دانلود

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

1-در این مطلب، متن اسلاید های اولیه دانلود پاورپوینت روش های حل مسئله ، تقسیم و حل قرار داده شده است

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

اسلاید ۱ :

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

مطالب فوق فقط متون اسلاید های ابتدایی پاورپوینت بوده اند . جهت دریافت کل ان ، لطفا خریداری نمایید .
PowerPoint قابل ویرایش - قیمت 11900 تومان در 54 صفحه
119,000 ریال – خرید و دانلود
سایر مقالات موجود در این موضوع
دیدگاه خود را مطرح فرمایید . وظیفه ماست که به سوالات شما پاسخ دهیم

پاسخ دیدگاه شما ایمیل خواهد شد