تکنیک های حل مسئله problem solving

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

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

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

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

اسلاید ۱ :

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

۱- استقرا ( 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

Þ

 

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

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