برنامه‌نویسی پویا (Dynamic Programming)

توضیحات

در جلسه بیست و یکم درس طراحی الگوریتم دکتر حمید حاج سیدجوادی که اهمیت به سزایی در کنکور ارشد کامپیوتر و کنکور ارشد آی تی و نیز کنکور دکتری کامپیوتر و کنکور دکتری آی تی دارد، مطالب مهمی درباره مبحث برنامه‌نویسی پویا (Dynamic Programming) ارائه می‌شود. ﺑﺮﻧﺎﻣﻪﻧﻮیسی پویا مانند روش تقسیم- و-ﻏﻠﺒﻪ،ﻣﺴﺎﺋﻞ را ﺑﺎ ترکیب راه حلﻫﺎی‌ زیرﻣﺴﺎﺋﻞ حل می‌كند با این تفاوت که به جای حل زیرمسائل به روش بازگشتی و ترکیب آنها (در روش تقسیم- و-ﻏﻠﺒﻪ)، زیر مسائل را که ممکن است با هم همپوشانی داشته باشند هر کدام فقط یک بار حل می‌کند و سپس پاسخ‌ها را در یک جدول ذخیره می‌کند. برنامه نویسی پویا در مسائل بهینه سازی (Optimization) کاربرد دارد. ابتدا مراحل برنامه نویسی پویا با یک مثال شرح داده می‌شود. سپس مثال ضرب زنجیره‌ای ماتریس‌ها در سه گام تشریح و الگوریتم آن ارائه می‌گردد. پس از آن درخت جستجوی دودویی بهینه و الگوریتم آن شرح داده می‌شود. سپس الگوریتم فلوید وارشال، مرحله به مرحله شرح داده شده و شبه‌کد آن ارائه می‌گردد. بعد از آن مسئله خرد کردن پول با یک مثال، مرحله به مرحله شرح داده شده و شبه‌کد آن ارائه می‌گردد. آنگاه مسئله کوله‌پشتی 0 و 1 مرحله به مرحله شرح داده شده و شبه‌کد آن ارائه می‌گردد. در تمامی موارد الگوریتم ها تحلیل و در مورد پیچیدگی و Order آنها بحث می‌شود. در انتها 9 تست کنکور ارشد و دکترای طراحی الگوریتم در خصوص برنامه‌نویسی پویا مطرح و حل تشریحی آنها ارائه می‌گردد.