پاورپوینت تکنیک های حل مسئله (pptx) 26 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 26 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
1
تکنیک های حل مسئله
2
الگوریتم های حل
1- استقرا ( induction)
2- تقسیم و حل(Divide & Conquer)
3- حریصانه( Greedy)
4- برنامه نویسی پویا Dynamic Programining))
5- عقبگرد( Back Tracking ) ، انشعاب و تحديد (Branch & Bound)
6- گراف ( بسياری از مسائل دنيای واقع با گراف قابل مدل سازی است)
در پایان این فصل انتظار داریم که دانشجو با دیدن مسئله تشخیص دهد که آیا مسئله حل شدنی است یا خیر؟ چه تکنیکی هایی برای حل آن وجود دارد و کدام تکنیک بهینه است ؟
در برخی از مسائل ما مجبوریم از الگوهای حل ترکیبی استفاده کنیم و هر کدام از قسمت های حل مسئله را با یک تکنیک حل کنیم.
3
استقرا
این روش حل مسئله یک راه کاملا ریاضیاتی اما پر کاربرد است . در این نوع مسائل ما سعی می کنیم با استفاده از منطق ریاضی به مسئله پاسخ دهیم. مطمئنا اگرمسئله ای در حل استقرا پذیر باشد ، آنگاه قطعا در اثبات و آنالیز نیز استقرا پذیر خواهد بود.
4
مسئله 1
ما به کمک اسقرا ثابت می کنیم "همه صندلی های دنیا کرم رنگ است". به نظر شما اشتباه این اثبات در چیست؟
اثبات:
پایه : n=1
فرض : n=k هر k صندلی ، کرم رنگ است
حکم : n=k+1 ادعا : هر k+1 صندلی کرم رنگ است
5
حل
ما در پایه از سور وجودی ∃ استفاده کردیم اما در فرض از سور عمومی ∀ استفاده کردیم که این اشتباه است . فرض باید به گونه ای انتخاب شود که همان پایه باشد و فقط 1 تبدیل به k شود.
6
مسئله 2
دو عدد متوالی روی دو کارت نوشته شده است . دو نفر وارد می شوند و هر کدام یک کارت را انتخاب می کنند. آن دو نفر باید عدد نوشته شده روی کارت یکدیگر را حدس بزنند، اما حق مکالمه ی عددی ندارند و همچنین تنها جملاتی را هم که می توانند به کار ببرند به شرح زیر است .
نفر اول به دوم : نمی دانم روی کارت تو چه چیز نوشته شده است !
نفر دوم به اول : نمی دانم روی کارت تو چه چیز نوشته شده است !
7
حل
کلمه " نمی دانم " در اینجا بسیار پر معناست ، زیرا اگر یکی از اعداد 1 باشد مسلما عدد دیگر 2 است اما چون نفر اول گفته است نمی دانم پس کارت او قطعا عدد 1 نیست . در ادامه اگر طرف مقابل بگوید نمی دانم مشخص می شود کارت شخص دوم نیزعدد 2 نیست زیرا عدد 2 ، دو حالت بیشتر ندارد که یا 1 است و یا 3 و چون قبلا مشخص شد که 1 نیست پس تنها حالت ممکن 3 است و با گفتن کلمه نمی دانم این حالت هم از بین می رود. این کار را به صورت استقرایی همچنان ادامه می دهیم تا به اعداد مورد نظر برسیم.
نمی دانم ⇐ عدد 1 نیست
نمی دانم ⇐ عدد 2 نیست
نمی دانم ⇐ عدد 3 نیست
8
مسئله 3 ( برج هانوی )
همان گونه که در شکل می بینید می خواهیم n ديسك را از میله S(مبدا) به میله D( مقصد ) به کمک میله H انتقال دهیم. اما محدودیت های زیر را داریم :
در هر انتقال تنها یک ديسك را می توانیم جابه جا کنیم .
هیچگاه ديسك بزرگ تر روی ديسك کوچک تر قرار نمی گیرد.
9