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