درباره دوره:
بسیاری از مسائل محاسباتی مطرح در حوزههای مختلف علم جزو مسائلی هستند که حل آنها به راحتی امکانپذیر نمیباشد. در درس نظریه الگوریتم پیشرفته، ابتدا مسائل محاسباتی مختلف مطرح و سختی آنها با استفاده از نظریههای موجود مورد بررسی و اثبات قرار میگیرد. پس از آن، روشهای الگوریتمی موجود برای حل مسائل سخت معرفی و در مورد هر یک از روشها نمونههایی نیز مورد بحث قرار میگیرد. از جمله این روشها میتوان به الگوریتمهای قطعی، الگوریتمهای تقریبی، الگوریتمهای تصادفی، روشهای مکاشفهای و روشهای محاسباتی نوین (مانند محاسبات مولکولی) اشاره کرد. در بسیاری از این روشها، درستی الگوریتمهای ارائه شده اثبات و منابع مورد نیاز برای اجرای این الگوریتمها به صورت دقیق تحلیل میشود.
اسلایدهای کامل درس را میتوانید از این اینجا دانلود نمایید.
کلمات کلیدی درس: مسائل NP-سخت، مسائل NP-کامل، الگوریتمهای شبه چند جملهای، روشهای پارامتریسازی، الگوریتمهای تقریبی، الگوریتمهای تصادفی
فیلم های آموزشی:
1 – جلسه اول – مقدمه ای بر طراحی الگوریتمها
2 – جلسه دوم – مقدمهای بر طراحی و تحلیل الگوریتمها (روش تقسیم و غلبه، روش برنامه ریزی پویا)
3 – جلسه سوم – مقدمهای بر طراحی و تحلیل الگوریتمها (روش حریصانه، روش برگشت به عقب، روش شاخه و تحدید)
4 – جلسه چهارم – رده بندی مسائل محاسباتی (مسائل NP-Hard ، NP ، P و NP-Complete)
5 – جلسه پنجم – اثبات NP-کامل بودن مسائل محاسباتی (۱)
6 – جلسه ششم – اثبات NP-کامل بودن مسائل محاسباتی (۲)
7 – جلسه هفتم – الگوریتمهای شبه چندجملهای
8 – جلسه هشتم – مسائل قویا NP-سخت، الگوریتمهای پارامتری سازی شده
9 – جلسه نهم – الگوریتمهای پارامتری سازی شده، روش شاخه و تحدید
10 – جلسه دهم – کاهش نرخ رشد توابع مربوط به پیچیدگی الگوریتمها
11 – جلسه یازدهم – جستجوی محلی و جستجوی محلی با عمق متغیر
12 – جلسه دوازدهم – رده بندی مسائل از دیدگاه روش جستجوی محلی
13 – جلسه سیزدهم – الگوریتمهای تقریبی (۱) و انواع مختلف آنها
14 – جلسه چهاردهم – الگوریتمهای تقریبی (۲)
15 – جلسه پانزدهم – الگوریتمهای تقریبی (۳) و پایداری آنها
16 – جلسه شانزدهم – الگوریتمهای تقریبی (۴)
17 – جلسه هفدهم – الگوریتمهای تقریبی (۵)
18 – جلسه هجدهم – رده بندی مسائل از دیدگاه الگوریتمهای تقریبی
19 – جلسه نوزدهم – الگوریتمهای تصادفی (۱) و انواع مختلف آنها
20 – جلسه بیستم – الگوریتمهای تصادفی (۲)
21 – جلسه بیست و یکم – الگوریتمهای تصادفی (۳)
22 – جلسه بیست و دوم – الگوریتمهای تصادفی (۴)
23 – جلسه بیست و سوم – الگوریتمهای تقریبی-تصادفی
24 – جلسه بیست و چهارم – الگوریتمهای تصادفی (تشخیص اول بودن اعداد)