پاورپوینت کامل برنامه‌نویسی پویا (Dynamic Programming) و تحلیل علمی اصول بهینه‌سازی و کاربردهای الگوریتمی

توجه : این پروژه به صورت فایل power point (پاور پوینت) ارائه میگردد

 پاورپوینت کامل برنامه‌نویسی پویا (Dynamic Programming) و تحلیل علمی اصول بهینه‌سازی و کاربردهای الگوریتمی دارای ۲۶ اسلاید می باشد و دارای تنظیمات کامل در Power Point می باشد و آماده پرینت یا چاپ است

فایل پاور پوینت پاورپوینت کامل برنامه‌نویسی پویا (Dynamic Programming) و تحلیل علمی اصول بهینه‌سازی و کاربردهای الگوریتمی  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

---

لطفا به نکات زیر در هنگام خرید

دانلودپاورپوینت کامل برنامه‌نویسی پویا (Dynamic Programming) و تحلیل علمی اصول بهینه‌سازی و کاربردهای الگوریتمی

توجه فرمایید.

۱-در این مطلب، متن اسلاید های اولیه 

دانلودپاورپوینت کامل برنامه‌نویسی پویا (Dynamic Programming) و تحلیل علمی اصول بهینه‌سازی و کاربردهای الگوریتمی

قرار داده شده است

۲-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید

۳-پس از پرداخت هزینه ، حداکثر طی ۱۲ ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد

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

۵-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار داده نشده است

---

بخشی از متن پاورپوینت کامل برنامه‌نویسی پویا (Dynamic Programming) و تحلیل علمی اصول بهینه‌سازی و کاربردهای الگوریتمی :

اسلاید ۱ :

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

üدر این روش مسئله با سایز ورودی n را به انواع زیر مسائل می شکنیم ( انواع روش های شکستن را آزمایش می کنیم ) . این شکستن را ادامه می دهیم تا به مرحله ای برسیم که مسئله دیگر قابل شکستن نباشد و یا پاسخ بدیهی به نظر برسد .

ü  معمولا با کوچک ترین و در نتیجه ساده ترین نمونه حل را آغاز می کنیم . سپس از ترکیب حل نمونه های کوچک تر حل نمونه های بزرگ تر به دست می آید و این روند ادامه می یابد تا سرانجام حل نمونه اصلی یا کامل حاصل شود .

ü  این روش زمانی مفید است که معیار حریصانه ای وجود نداشته باشد و مسئله اصلی قابل شکستن باشد .

ü

اسلاید ۲ :

üانواع شکستن مسئله باعث می شود که تعدادی زیر مسائل تکراری تولید شود . هزینه حل یا محاسبه این تعداد از مرتبه نمایی است .

üدر روش برنامه نویسی پویا برای کاهش این مرتبه زمانی هر زیر مسئله در حافظه نگهداری شده و در مواقع تولید، زیر مسائل تکراری دیگر حل    نمی شوند و تنها عمل واکشی اطلاعات صورت می گیرد .

üتفاوت اصلی بین روش حریصانه و برنامه نویسی پویا آن است که در روش حریصانه فقط یک مجموعه ی انتخا ب ها ( جوابها ) تولید می شود در حالی که در برنامه نویسی پویا ممکن است مجموعه ی زیادی از انتخاب ها  ( جوابها ) تولید شود.هر چند که مجموعه های شامل زیر مجموعه های بهینه نمی تواند بهینه باشند ( اگر اصل بهینه سازی برقرار باشد ) و       بنا براین تا حد امکان نباید تولید شوند .

اسلاید ۳ :

حل مسئله به روش برنامه نویسی پویا

گام اول : مشخص کردن انواع روش های شکستن مسئله و ارائه این موضوع در یک طرح درخت واره ای

ü این فاز یکی از مهمترین فازها می باشد و یک طرح واحد نیست ولی بهینه ترین در نظر گرفته می شود .

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

گام سوم : جلوگیری از محاسبات تکراری ، با طراحی یک جدول و ثبت جواب هر زیر مسئله در آن در ادامه کار اگر آن زیر مسئله دوباره تکرار شد از جدول استفاده می کنیم .

گام چهارم : پیاده سازی برنامه

گام پنجم : تحلیل زمانی / حافظه ای

اسلاید ۴ :

ضرب زنجیره ای ماتریس ها

 مسئله اینست که ماتریس های زیر را به چه روشی با یکدیگر ضرب کنیم تا کمترین هزینه ضرب و جمع را بپردازیم ؟

 M1 ×  M2 × M3 × … × Mn

مثال

فرض می کنیم چهار ماتریس داریم به طوری که سطر و ستون آن به ترتیب زیر باشد :

اسلاید ۵ :

 روشن است که روش های مختلف محاسبه ،  هزینه های مختلف را در بر دارد .

    به عنوان مثال :

((M1 × M2) × M3) × M4 =   (۲ × ۵ × ۳) + (۲ × ۳ × ۸) +(۲ × ۸ × ۱)

                                    =  ۳۰ + ۴۸ + ۱۶ = ۹۴

(M1 × M2) ×(M3 × M4)  =  (۲ × ۵ × ۳) +(۳ × ۸ × ۱) + (۲ × ۳ × ۱)

                                    =  ۳۰ + ۲۴ + ۶ = ۶۰

با توجه به مثال بالا تعداد کل حالات ضرب n ماتریس از رابطه ی بازگشتی ذیل محاسبه   می شود :

ریاضیات رابطه بازگشتی بالا را حل کرده است.

اسلاید ۶ :

اگر n برابر ۴ باشد آنگاه عدد کاتالان برابر ۵ است. به عبارت دیگر تعداد کل حالات ممکن ضرب زنجیره ای ۴ ماتریس برابر ۵ است .

( (M1 × M2) × M3 ) × M4

( M1 × (M2 × M3) ) × M4

( M1 × M2 ) × ( M3 × M4 )

M1 × ( (M2 × M3) × M4 )

M1 × ( M2 × (M3 × M4) )

ü در این مسئله هدف یافتن بهینه ترین حالت ضرب است از نظر کمترین تعداد اعمال محاسباتی

اسلاید ۷ :

گام دوم : نحوه ترکیب یا محاسبه ی هزینه ضرب در طرح درخت واره ای

M11=M22=M33=M44=0

M12 = min ( M11 + M22 + 2 × ۵ × ۳)=۳۰

M23 = min ( M22 + M33 + 5 × ۳ × ۸)=۱۲۰

M34 = min ( M33 + M44 +3 × ۸ × ۱)=۲۴

M13 = min ( M11 + M23 + 2 × ۵ × ۸ , M12 + M33 + 2 × ۳ × ۸)

        = min (120+80 , 30+48) = min(200 , 78)=۷۸

M24 = min ( M22 + M34 + 5 × ۳ × ۱ , M23 + M44 + 5 × ۸ × ۱)

        = min ( 24+15 , 120+40)=min(39 , 160)=۳۹

 

M14 = min(M11 + M24 + 2×۵×۱,M12+M34 +2×۳×۱,M13+M44+ 2×۸ ×۱)          = min (39+10 , 30+24+6 , 78+16)=min(49,60,94)=۴۹

اسلاید ۸ :

گام چهارم  : پیاده سازی

برای پیاده سازی طرح و ساختار حافظه ای مطرح شده ( برای نگهداری عناصر تکراری ) نیاز به یک آرایه دو بعدی جهت ذخیره کردن حالت بهینه در هر گذر و همچنین نیاز به یک آرایه یک بعدی جهت نگهداری ابعاد ماتریس ها داریم :

به عنوان مثال داریم :

آرایه ابعاد ماتریس ها :

A :

اسلاید ۹ :

 for (i=1 ; i<= n ; i++)

  m[i][i] = 0;

for (r=2 ; r<= n ; r++)

  for(c=r-1 ; c>=1 ; c–)

  {

  min = 99999 ; // +

  for (k=c ; k<r ; k++)

  {

        if (m[c][k]+m[k+1][r]+ A[c-1]*A[k]*A[r] < min)

  min = m[c][k]+m[k+1][r]+ A[c-1]*A[k]*A[r];

  m[c][r]= min;

  }

  }

اسلاید ۱۰ :

گام پنجم: هزینه زمانی/ حافظه ای

هزینه حافظه ای :

با توجه به ساختارهای حافظه ای استفاده شده داریم :

هزینه حافظه ای = هزینه آرایه دوبعدی ساختار حافظه ای + حافظه یک بعدی ابعاد ماتریس ها

هزینه زمانی:

با توجه به حلقه های for  استفاده شده در کد پیاده سازی برنامه  هزینه زمانی برابر است با