پاورپوینت کامل برنامه نویسی پویا ۹۲ اسلاید در PowerPoint

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

 پاورپوینت کامل برنامه نویسی پویا ۹۲ اسلاید در PowerPoint دارای ۹۲ اسلاید می باشد و دارای تنظیمات کامل در PowerPoint می باشد و آماده ارائه یا چاپ است

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

لطفا نگران مطالب داخل پاورپوینت نباشید، مطالب داخل اسلاید ها بسیار ساده و قابل درک برای شما می باشد، ما عالی بودن این فایل رو تضمین می کنیم.

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

بخشی از مطالب داخلی اسلاید ها

پاورپوینت کامل برنامه نویسی پویا ۹۲ اسلاید در PowerPoint

اسلاید ۴: پاورپوینت کامل برنامه نویسی پویا ۹۲ اسلاید در PowerPointمراحل بسط یک الگوریتم پاورپوینت کامل برنامه نویسی پویا ۹۲ اسلاید در PowerPoint:1- ارائه یک ویژگی بازگشتی برای نمونه‌ای از مسئله۲- حل مسئله به شیوه پایین به بالا با حل نمونه‌های کوچکتر۵

اسلاید ۵: الف) ضریب دوجمله‌ای۶

اسلاید ۶: الف) ضریب دوجمله‌ایحل با استفاده از روش تقسیم‌وحل:function [result]=binCoef(n,k) if (k==0 || k==n) result=1; else result=binCoef(n-1,k-1)+binCoef(n-1,k); endend7

اسلاید ۷: الف) ضریب دوجمله‌ایهمانند محاسبه جمله nام فیبوناجی، این الگوریتم نیز کارایی کمی دارد.مثلا binCoef(n-1,k-1) و binCoef(n-1,k) هر دو نیاز به نتیجه binCoef(n-2,k-1) دارند و این نمونه در هر فراخوانی بازگشتی به صورت جداگانه محاسبه می‌شود.۸

اسلاید ۸: الف) ضریب دوجمله‌ایحل با روش پویا:۱- یک ویژگی بازگشتی ایجاد می‌کنیم۲- مسئله را به صورت پایین به بالا حل می‌کنیم …۹

اسلاید ۹: الف) ضریب دوجمله‌ایحل با روش پویا:۱- یک ویژگی بازگشتی ایجاد می‌کنیم۲- مسئله را به صورت…. پایین به بالا حل می‌کنیم:۱۰

اسلاید ۱۰: الف) ضریب دوجمله‌ایحل با روش پویا:function [result]=binCoef2(n,k) for i=0:n for j=0:min([i k]) if ((j==0)||(j==i)) B(i,j)=1; else B(i,j)=B(i-1,j-1)+B(i-1,j); end end end result=B(n,k);end11تمرین: تابع فوق را به گونه‌ای تغییر دهید که اجرای آن در Matlab صحیح باشد

اسلاید ۱۱: الف) ضریب دوجمله‌ایپیچیدگی محاسباتی و مرتبه آن:for i=1:n for j=1:min([i k]) endend12

اسلاید ۱۲: الف) ضریب دوجمله‌ایتمرین: مسئله ضریب دو جمله‌ای را با برنامه‌نویسی پویا با آرایه یک بعدی حل کنید۱۳

اسلاید ۱۳: کوئیز از جلسه قبل)برای یافتن ضریب kام دوجمله‌ای رابطه زیر برقرار است.الف) ویژگی بازگشتی ارائه دهید که ضریب kام با روش پاورپوینت کامل برنامه نویسی پویا ۹۲ اسلاید در PowerPoint بدست آید.ب) تابع متناظر با ویژگی بازگشتی در بخش الف را بنویسید۱۴

اسلاید ۱۴: مسائل بهینه سازیدر ریاضیات و علوم کامپیوتر مساله بهینه‌سازی به صورت زیر تعریف می‌شود:مساله‌ای است که در آن به دنبال یافتن بهترین راه حل در بین…تمامی راه حل‌های ممکن هستیم.این مسائل باتوجه متغیرهای موثر در حل مسئله به دو گروه زیر تقسیم می‌شوند:متغیرهای پیوسته مساله بهینه‌سازی پیوستهمتغیرهای گسستهمساله بهینه‌سازی ترکیبی ۱۵

اسلاید ۱۵: مسائل بهینه سازیمساله بهینه‌سازی پیوستهفرم استاندارد این مسائل به صورت زیر است:که …تابع هدفی است که می‌خواهیم xای را برایش بیابیم که آن را کمینه کند.محدودیت‌هایی هستند که به صورت عدم تساوی بیان می‌شوند.محدودیت‌هایی هستند که به صورت تساوی بیان می‌گردند.۱۶

اسلاید ۱۶: مسائل بهینه سازیمسائل بهینه‌سازی ترکیبیمانند ….مساله یافتن کوتاه‌ترین مسیر بین دو شهراین مسائل به صورت چهارتایی (I, f, m, g) بیان می‌شوند که ….I مجموعه نمونه‌ها است مانند …مجموعه شهرها به صورت دوبه‌دوxای که عضو I است را در نظر بگیرید مانند … (یزد و کرمانشاه)f(x) مجموعه راه حل‌های ممکن برای این x است مانند …مسیرهای مختلف جاده‌ای بین این دو شهر۱۷

اسلاید ۱۷: مسائل بهینه سازیمسائل بهینه‌سازی ترکیبی (I, f, m, g)فرض کنید که y، یکی از راه حل‌های ممکن باشد مانند… یزد-ابرکوه-اصفهان-بروجرد-کنگاور-کرمانشاهm(x,y) تابعی است که اندازه y به ازای x که معمولا عددی مثبت است را برمی‌گرداند.g، تابع هدف است که معمولا یا min و یا max است.هدف در این مسائل بهینه‌سازی آن است تا ….برای هر x، …بهینه‌ترین راه حل (y) با توجه به تابع هدف را پیدا کنیم.۱۸

اسلاید ۱۸: حل مسائل بهینه‌سازی ترکیبی با برنامه‌نویسی پویابرای حل مسائل بهینه‌سازی ترکیبی روش‌های مختلفی وجود دارد که با رویکردهای حل آنها با روش‌های برنامه‌نویسی پویا، حریصانه، عقبگرد و شاخ‌وحد انشاا… در طول ترم آشنا خواهیم شد.مسائل بهینه‌سازی ترکیبی ای را می‌توان با پاورپوینت کامل برنامه نویسی پویا ۹۲ اسلاید در PowerPoint حل کرد به شرط آن‌که اصل بهینگی در مورد آن برقرار باشد۱۹

اسلاید ۱۹: اصل بهینگی (Principle of Optimality)تعریف: مساله‌ای شرایط اصل بهینگی را داردچنانچه در آن مساله …زیر راه‌حل‌های یک راه‌‌حل بهینه برای هر نمونه مساله‌ …خودشان راه‌حل‌های بهینه برای زیرمسائلی متناظر باشند.۲۰حل مسائل بهینه‌سازی ترکیبی با برنامه‌نویسی پویا

اسلاید ۲۰: مثال: آیا شرایط بهینگی در مساله کوتاه‌ترین مسیر برقرار است؟ روش بررسی ….اگر برای مساله کوتاه‌ترین مسیر از هر a به هر bای، …a,x1,x2,…,xn,b راه‌حل بهینه باشد …در این‌صورت هر بخش xi to xj در این راه‌حل بهینه …خود را حل بهینه برای کوتاه‌ترین مسیر از xi به xj می‌باشد …چراکه اصلا ممکن نیست بخشی از راه‌حل کوتاه‌ترین مسیر نباشد ولی کل راه حل بهینه گردد.۲۱حل مسائل بهینه‌سازی ترکیبی با برنامه‌نویسی پویا

اسلاید ۲۱: مثال: همان مساله قبلی را به جای کوتاه‌ترین مسیر، طولانی‌ترین مسیر ساده درنظر بگیرید.مسیر ساده: مسیری که هیچگاه دوبار از یک راس نگذرد.حالا چرا مسیر ساده ؟ ….اصل بهینگی برقرار است؟آیا نمی‌توان همان توجیه کوتاه‌ترین مسیر را اینجا نیز مطرح کنیم؟ امکان دارد بین دو راس میانی طولانی‌ترین مسیر ساده‌ای وجود داشته باشد که اگر طولانی‌ترین مسیر مساله اصلی بخواهد از همان بگذرد دیگر ساده نشود یعنی مجبور است از یک راس دوبار بگذرد.۲۲حل مسائل بهینه‌سازی ترکیبی با برنامه‌نویسی پویا

اسلاید ۲۲: به مثال زیر توجه کنید:طولانی‌ترین مسیر از v1 به v4، ….[v1, v3, v2, v4] هست ولی …طولانی‌ترین مسیر از v1 به v3 دیگر …[v1, v3] نیست بلکه ….[v1,v2,v3] است.۲۳حل مسائل بهینه‌سازی ترکیبی با برنامه‌نویسی پویا

اسلاید ۲۳: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافنمایش یک گراف وزن‌دار جهت‌دار در شکل زیر آمده است:۲۴

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

اسلاید ۲۵: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافبا این الگوریتم می‌خواهیم کوتاه‌ترین مسیر بین هر دو گره را به‌دست بیاوریم.یک الگوریتم واضح: تعیین طول همه مسیر‌ها برای هر راس از آن راس به همه رئوس دیگر۲۶

اسلاید ۲۶: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافیک گراف وزن‌دار حاوی n راس را با آرایه W نشان می‌دهیم:۲۷

اسلاید ۲۷: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافدر این الگوریتم، در نهایت می‌خواهیم ماتریس D را که دربرگیرنده کوتاه‌ترین مسیر بین هر دو گره است را پیدا کنیم۲۸

اسلاید ۲۸: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافD(k) [i][j] را برابر طول کوتاه‌ترین مسیری قرار می‌دهیم که vi را به vj وصل می‌کند و فقط هم از راس‌های موجود در مجموعه {v1,v2,…,vk} به عنوان رئوس میانی استفاده می‌کند. ۲۹

اسلاید ۲۹: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافبنابراین برای پیداکردن D بایستی به دنبال راه حلی باشیم که …D(n) را از D(0) به دست بیاوریم.همانگونه که در جلسه قبل بیان شد در پاورپوینت کامل برنامه نویسی پویا ۹۲ اسلاید در PowerPoint باید ابتدا …ویژگی بازگشتی بنویسیم که …D(k) را از D(k-1) بدست بیاورد.سپس …برنامه‌ای بنویسیم که مساله را به صورت پایین به بالا حل کند. یعنی در برنامه …k را ابتدا صفر قرار دهیم و تا n این فرایند را تکرار کنیم.۳۰

اسلاید ۳۰: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافگام اول: ویژگی بازگشتی بنویسیم که D(k) را از D(k-1) بدست بیاورد.برای حل این گام می‌توانیم دو حالت را در نظر بگیریم:حالت اول: …استفاده از راس kام در مرحله kام سبب کوتاه‌ترشدن مسیر نمی‌شود.حالت دوم: …استفاده از راس kام سبب کوتاه‌ترشدن مسیر می‌شود.۳۱

اسلاید ۳۱: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافگام اول: ویژگی بازگشتی بنویسیم که D(k) را از D(k-1) بدست بیاورد.حالت دوم: …استفاده از راس kام سبب کوتاه‌ترشدن مسیر می‌شود.از آنجایی که vk نمی‌تواند راس میانی در زیر مسیرها از vi به vk و همچنین از vk به vj باشد بنابراین …در این مسیرها تنها از مجموعه رئوس {v1,…,vk-1} به عنوا