دانلود پاورپوینت با موضوع برنامه نویسی پویا،
در قالب ppt و در 87 اسلاید، قابل ویرایش.
بخشی از متن پاورپوینت:
برنامه نویسی پویا (Dynamic Programming)
یادآوری: روش تقسیم و حل برای محاسبه جمله n ام فیبوناجی
روش تقسیم و حل، روشی بالا به پایین است.
این روش در مسائلی مانند مرتب سازی ادغامی جواب میدهد چراکه نمونههای کوچکتر به مرتبط نیستند.
ولی در محاسبه جمله nام فیبوناجی، نمونهها کوچکتر به هم مرتبطند
برنامه نویسی پویا از این نظر که نمونه به نمونههای کوچکتر تقسیم میشود، مشابه روش تقسیم و حل است ولی
1- ابتدا نمونههای کوچکتر را حل میکنیم
2- نتایج را ذخیره میکنیم و
3- بعدا هرگاه به آنها نیاز شد به جای محاسبه مجدد تنها آنها را بازیابی میکنیم
بنابراین روشی پایین به بالا است
مراحل بسط یک الگوریتم برنامه نویسی پویا:
1- ارائه یک ویژگی بازگشتی برای نمونهای از مسئله
2- حل مسئله به شیوه پایین به بالا با حل نمونههای کوچکتر
الف) ضریب دوجملهای
همانند محاسبه جمله nام فیبوناجی، این الگوریتم نیز کارایی کمی دارد.
مثلا binCoef(n-1,k-1) و binCoef(n-1,k) هر دو نیاز به نتیجه
binCoef(n-2,k-1)
دارند و این نمونه در هر فراخوانی بازگشتی به صورت جداگانه محاسبه میشود.
مسائل بهینه سازیدر ریاضیات و علوم کامپیوتر مساله بهینهسازی به صورت زیر تعریف میشود:
مسالهای است که در آن به دنبال یافتن بهترین راه حل در بین…
تمامی راه حلهای ممکن هستیم.
این مسائل باتوجه متغیرهای موثر در حل مسئله به دو گروه زیر تقسیم میشوند:
متغیرهای پیوسته مساله بهینهسازی پیوسته
متغیرهای گسستهمساله بهینهسازی ترکیبی
یادآوری: روش تقسیم و حل برای محاسبه جمله n ام فیبوناجی
روش تقسیم و حل، روشی بالا به پایین است.
این روش در مسائلی مانند مرتب سازی ادغامی جواب میدهد چراکه نمونههای کوچکتر به مرتبط نیستند.
ولی در محاسبه جمله nام فیبوناجی، نمونهها کوچکتر به هم مرتبطند
برنامه نویسی پویا از این نظر که نمونه به نمونههای کوچکتر تقسیم میشود، مشابه روش تقسیم و حل است ولی
1- ابتدا نمونههای کوچکتر را حل میکنیم
2- نتایج را ذخیره میکنیم و
3- بعدا هرگاه به آنها نیاز شد به جای محاسبه مجدد تنها آنها را بازیابی میکنیم
بنابراین روشی پایین به بالا است
مراحل بسط یک الگوریتم برنامه نویسی پویا:
1- ارائه یک ویژگی بازگشتی برای نمونهای از مسئله
2- حل مسئله به شیوه پایین به بالا با حل نمونههای کوچکتر
الف) ضریب دوجملهای
همانند محاسبه جمله nام فیبوناجی، این الگوریتم نیز کارایی کمی دارد.
مثلا binCoef(n-1,k-1) و binCoef(n-1,k) هر دو نیاز به نتیجه
binCoef(n-2,k-1)
دارند و این نمونه در هر فراخوانی بازگشتی به صورت جداگانه محاسبه میشود.
مسائل بهینه سازیدر ریاضیات و علوم کامپیوتر مساله بهینهسازی به صورت زیر تعریف میشود:
مسالهای است که در آن به دنبال یافتن بهترین راه حل در بین…
تمامی راه حلهای ممکن هستیم.
این مسائل باتوجه متغیرهای موثر در حل مسئله به دو گروه زیر تقسیم میشوند:
متغیرهای پیوسته مساله بهینهسازی پیوسته
متغیرهای گسستهمساله بهینهسازی ترکیبی