لطفا به نکات زیر در هنگام خرید تکنیک های حل مسئله problem solving توجه فرمایید.

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

اسلاید ۱ :

الگوریتم های حل

۱- استقرا ( induction)

۲- تقسیم و حل(Divide & Conquer)

۳- حریصانه( Greedy)

۴- برنامه نویسی پویا Dynamic Programining))

۵- عقبگرد( Back Tracking ) ، انشعاب و تحديد (Branch & Bound)

۶- گراف ( بسياری از مسائل دنيای واقع با گراف قابل مدل سازی است)

 

در پایان این فصل انتظار داریم که دانشجو با دیدن مسئله تشخیص دهد که آیا مسئله حل شدنی است یا خیر؟ چه تکنیکی هایی برای حل آن وجود دارد و کدام تکنیک بهینه است ؟

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

اسلاید ۲ :

استقرا

 

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

اسلاید ۳ :

مسئله ۱

ما به کمک اسقرا ثابت می کنیم “همه صندلی های دنیا کرم رنگ است”. به نظر شما اشتباه این اثبات در چیست؟

اثبات:

پایه : n=1

فرض : n=k هر k صندلی ، کرم رنگ است

حکم : n=k+1 ادعا : هر k+1 صندلی کرم رنگ است

اسلاید ۴ :

حل

ما در پایه از سور وجودی ∃ استفاده کردیم اما در فرض از سور عمومی ∀ استفاده کردیم که این اشتباه است . فرض باید به گونه ای انتخاب شود که همان پایه باشد و فقط ۱ تبدیل به k شود.

اسلاید ۵ :

مسئله ۲

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

نفر اول به دوم : نمی دانم روی کارت تو چه چیز نوشته شده است !

نفر دوم به اول : نمی دانم روی کارت تو چه چیز نوشته شده است !

اسلاید ۶ :

حل

کلمه ” نمی دانم ” در اینجا بسیار پر معناست ، زیرا اگر یکی از اعداد ۱ باشد مسلما عدد دیگر ۲ است اما چون نفر اول گفته است نمی دانم پس کارت او قطعا عدد ۱ نیست . در ادامه اگر طرف مقابل بگوید نمی دانم مشخص می شود کارت شخص دوم نیزعدد ۲  نیست زیرا عدد ۲ ، دو حالت بیشتر ندارد که یا ۱ است و یا ۳ و چون قبلا مشخص شد که ۱ نیست پس تنها حالت ممکن ۳ است و با گفتن کلمه نمی دانم این حالت هم از بین می رود. این کار را به صورت استقرایی همچنان ادامه می دهیم تا به اعداد مورد نظر برسیم.

                                            نمی دانم ⇐ عدد ۱ نیست

                                  نمی دانم ⇐ عدد ۲ نیست  

                     نمی دانم ⇐ عدد ۳ نیست 

 

اسلاید ۷ :

مسئله ۳  ( برج هانوی )

همان گونه که در شکل می بینید می خواهیم n ديسك را از میله  S(مبدا) به میله D( مقصد ) به کمک میله H انتقال دهیم. اما محدودیت های زیر را داریم :

.۱در هر انتقال تنها یک ديسك را می توانیم جابه جا کنیم  .

.۲ هیچگاه ديسك بزرگ تر روی ديسك کوچک تر قرار نمی گیرد.

اسلاید ۸ :

حل

پایه : n=1

فرض استقرا : فرض کنید روشی برای انتقال n دیسک از یک میله به میله دیگر وجود داشته باشد

حکم استقرا : ارائه روش برای n+1 دیسک

الگوریتم :

.۱انتقال n-1 دیسک بالای S به H به کمک D (زمان T(n-1)) 

.۲انتقال بزرگ ترین دیسک از S به D ( 1 واحد زمان )

.۳انتقال n-1 دیسک بالای H به D به کمک S (زمان T(n-1))

در اسلاید بعد عملکرد حل این مسئله با ۳ دیسک نمایش داده شده است .

اسلاید ۹ :

آنالیز زمانی

T (n ) = 2T(n-1) + 1

X – ۲ =۰ Þ 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

نکته :

  گام استقرا لزوما ۱ نیست . در مثال های قبل به علت اینکه پارامتر استقرا اعداد طبیعی مثبت بوده و این اعداد با گام های یک حرکت می کنند در نتیجه گام های استقرا را يك در نظر می گیریم.

اسلاید ۱۰ :

حل 

.۱انتقال n-1 دیسک از S به D

.۲انتقال دیسک بزرگ از S به H

.۳انتقال n-1 دیسک از D به S

.۴انتقال دیسک بزرگ از H به D

.۵انتقال n-1 دیسک از S به D

T(n ) = 3T(n -1) +2

Þ