صفحه محصول - پاورپوینت برنامه نویسی پویا

پاورپوینت برنامه نویسی پویا (pptx) 87 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 87 اسلاید

قسمتی از متن PowerPoint (.pptx) :

کوئیز از جلسه قبل) در کامپیوتری برای ضرب استراسن فرایند تقسیم نمونه‌‌ای به اندازه n به نمونه‌های کوچکتر، بارگذاری در پشته، فراخوانی از آن، جمع‌ها و تفریق‌ها همگی 12n2 μs طول می‌کشد. چنانچه با الگوریتم استانداردی n3 μs ضرب دو ماتریس با ابعاد n × n طول بکشد، حد آستانه‌ای بیابید که بهتر است از الگوریتم استاندارد به جای الگوریتم استراسن استفاده کنیم. آیا در این حل حد آستانه واحدی وجود دارد؟ 2 برنامه نویسی پویا (Dynamic Programming) یادآوری: روش تقسیم و حل برای محاسبه جمله n ام فیبوناجی روش تقسیم و حل، روشی بالا به پایین است. این روش در مسائلی مانند مرتب سازی ادغامی جواب می‌دهد چراکه نمونه‌های کوچکتر به مرتبط نیستند. ولی در محاسبه جمله nام فیبوناجی، نمونه‌ها کوچکتر به هم مرتبطند 3 برنامه نویسی پویا برنامه نویسی پویا از این نظر که نمونه به نمونه‌های کوچکتر تقسیم می‌شود، مشابه روش تقسیم و حل است ولی 1- ابتدا نمونه‌های کوچکتر را حل می‌کنیم 2- نتایج را ذخیره می‌کنیم و 3- بعدا هرگاه به آنها نیاز شد به جای محاسبه مجدد تنها آنها را بازیابی می‌کنیم بنابراین روشی پایین به بالا است 4 برنامه نویسی پویا مراحل بسط یک الگوریتم برنامه نویسی پویا: 1- ارائه یک ویژگی بازگشتی برای نمونه‌ای از مسئله 2- حل مسئله به شیوه پایین به بالا با حل نمونه‌های کوچکتر 5 الف) ضریب دوجمله‌ای 6 الف) ضریب دوجمله‌ای حل با استفاده از روش تقسیم‌وحل: function [result]=binCoef(n,k) if (k==0 || k==n) result=1; else result=binCoef(n-1,k-1)+binCoef(n-1,k); end end 7 الف) ضریب دوجمله‌ای همانند محاسبه جمله nام فیبوناجی، این الگوریتم نیز کارایی کمی دارد. مثلا binCoef(n-1,k-1) و binCoef(n-1,k) هر دو نیاز به نتیجه binCoef(n-2,k-1) دارند و این نمونه در هر فراخوانی بازگشتی به صورت جداگانه محاسبه می‌شود. 8 الف) ضریب دوجمله‌ای حل با روش پویا: 1- یک ویژگی بازگشتی ایجاد می‌کنیم 2- مسئله را به صورت پایین به بالا حل می‌کنیم ... 9