نظریه الگوریتم پیشرفته

دوره‌های دانشگاهی
24 جلسه

سرفصل‌ها

بسیاری از مسائل محاسباتی مطرح در حوزه‌های مختلف علم جزو مسائلی هستند که حل آنها به راحتی امکان‌پذیر نمی‌باشد. در درس نظریه الگوریتم پیشرفته، ابتدا مسائل محاسباتی مختلف مطرح و سختی آنها با استفاده از نظریه‌های موجود مورد بررسی و اثبات قرار می‌گیرد. پس از آن، روش‌های الگوریتمی موجود برای حل مسائل سخت معرفی و در مورد هر یک از روش‌ها نمونه‌هایی نیز مورد بحث قرار می‌گیرد. از جمله این روش‌ها می‌توان به الگوریتم‌های قطعی، الگوریتم‌های تقریبی، الگوریتم‌های تصادفی، روش‌های مکاشفه‌ای و روش‌های محاسباتی نوین (مانند محاسبات مولکولی) اشاره کرد. در بسیاری از این روش‌ها، درستی الگوریتم‌های ارائه شده اثبات و منابع مورد نیاز برای اجرای این الگوریتم‌ها به صورت دقیق تحلیل می‌شود.

اسلایدهای کامل درس را می‌توانید از این اینجا دانلود نمایید.

کلمات کلیدی درس: مسائل NP-سخت، مسائل NP-کامل، الگوریتم‌های شبه چند جمله‌ای، روش‌های پارامتری‌سازی، الگوریتم‌های تقریبی، الگوریتم‌های تصادفی

مدرس دوره
محمد گنج تابش
دکتر محمد گنج‌تابش عضو هیئت علمی گروه علوم کامپیوتر دانشگاه تهران است. ایشان دوره کارشناسی خود را در رشته ریاضی محض (دانشگاه تبریز) و دوره‌های کارشناسی ارشد و دکتری را در رشته علوم کامپیوتر (دانشگاه تهران) به اتمام رسانده است. ایشان همچنین دکتری دوم خود را در رشته بیوانفورماتیک (دانشگاه اکول پلی تکنیک فرانسه) گذرانده است. زمینه‌های تحقیقاتی مورد علاقه وی الگوریتم‌های بیوانفورماتیک (مسائل مربوط به ساختار‌های RNA) و علوم اعصاب محاسباتی (در زمینه بینایی) می‌باشد.
فیلم های آموزشی
ساعت
28:59 ساعت
Combined Shape Created with Sketch. 24 جلسه
جلسه اول - مقدمه ای بر طراحی الگوریتم‌ها
"64:49
جلسه دوم - مقدمه‌ای بر طراحی و تحلیل الگوریتم‌ها (روش تقسیم و غلبه، روش برنامه ریزی پویا)
"79:53
جلسه سوم - مقدمه‌ای بر طراحی و تحلیل الگوریتم‌ها (روش حریصانه، روش برگشت به عقب، روش شاخه و تحدید)
"73:20
جلسه چهارم - رده بندی مسائل محاسباتی (مسائل NP-Hard ، NP ، P و NP-Complete)
"80:24
جلسه پنجم - اثبات NP-کامل بودن مسائل محاسباتی (۱)
"93:10
جلسه ششم - اثبات NP-کامل بودن مسائل محاسباتی (۲)
"88:30
جلسه هفتم - الگوریتم‌های شبه چندجمله‌ای
"83:54
جلسه هشتم - مسائل قویا NP-سخت، الگوریتم‌های پارامتری سازی شده
"71:51
جلسه نهم - الگوریتم‌های پارامتری سازی شده، روش شاخه و تحدید
"77:50
جلسه دهم - کاهش نرخ رشد توابع مربوط به پیچیدگی الگوریتم‌ها
"73:48
جلسه یازدهم - جستجوی محلی و جستجوی محلی با عمق متغیر
"85:50
جلسه دوازدهم - رده بندی مسائل از دیدگاه روش جستجوی محلی
"66:22
جلسه سیزدهم - الگوریتم‌های تقریبی (۱) و انواع مختلف آنها
"78:49
جلسه چهاردهم - الگوریتم‌های تقریبی (۲)
"77:50
جلسه پانزدهم - الگوریتم‌های تقریبی (۳) و پایداری آنها
"79:30
جلسه شانزدهم - الگوریتم‌های تقریبی (۴)
"88:13
جلسه هفدهم - الگوریتم‌های تقریبی (۵)
"79:51
جلسه هجدهم - رده بندی مسائل از دیدگاه الگوریتم‌های تقریبی
"58:51
جلسه نوزدهم - الگوریتم‌های تصادفی (۱) و انواع مختلف آن‌ها
جلسه بیستم - الگوریتم‌های تصادفی (۲)
"59:10
جلسه بیست و یکم - الگوریتم‌های تصادفی (۳)
"72:41
جلسه بیست و دوم - الگوریتم‌های تصادفی (۴)
"76:01
جلسه بیست و سوم - الگوریتم‌های تقریبی-تصادفی
"72:01
جلسه بیست و چهارم - الگوریتم‌های تصادفی (تشخیص اول بودن اعداد)
"56:58