درباره دوره:
درس طراحی و تحلیل الگوریتمها یکی از مهمترین و پایهایترین دروس در رشتههای علوم کامپیوتر و همچنین مهندسی کامپیوتر است. هدف از این درس، مطالعه و بررسی روشهای طراحی الگوریتمها برای حل مسائل مختلف و چگونگی تحلیل و اثبات درستی الگوریتمهای ارائه شده برای حل آنها است. آشنایی هرچه بیشتر با مسائل در حوزههای مختلف علمی باعث افزایش توانایی افراد در ارائه راهحلهای الگوریتمی برای مسائل جدید خواهد شد. همچنین بسیاری از مسائل محاسباتی مطرح در حوزههای مختلف علم جزء مسائلی هستند که حل الگوریتمی آنها در زمان قابلقبول بهراحتی امکانپذیر نمیباشد، در نتیجه دستهبندی مسائل و شناسایی مسائل محاسباتی سخت که در زمان قابلقبول نمیتوان جواب آنها را به دست آورد، نیز از اهمیت ویژهای برخوردار است. در این دوره آموزشی، ابتدا به مفاهیم مقدماتی در حوزه طراحی و تحلیل الگوریتمها پرداخته شده و روشهای کلاسیک برای حل مسائل مختلف به همراه مثالهای متنوع ارائه میشود. برای این منظور روشهایی همچون روش تقسیم و غلبه، برنامهریزی پویا، روش حریصانه، بازگشت به عقب و روش شاخه و تحدید موردبحث قرار میگیرند. به شکل ویژه، الگوریتمهای مطرح در حوزه نظریه گراف و همچنین تطابق رشتهها مورد بررسی قرار میگیرند. پس از آن، به بررسی سختی مسائل با استفاده از نظریههای موجود پرداخته میشود. سپس روشهای الگوریتمی موجود برای حل مسائل سخت معرفی و در مورد هر یک از روشها نمونههایی نیز موردبحث قرار میگیرند، از جمله این روشها میتوان به الگوریتمهای قطعی، الگوریتمهای تقریبی، الگوریتمهای تصادفی، روشهای مکاشفهای و روشهای محاسباتی نوین اشاره کرد. در بسیاری از این روشها، درستی الگوریتمهای ارائه شده اثبات و منابع موردنیاز برای اجرای این الگوریتمها بهصورت دقیق تحلیل میشوند.
این درس برای تمامی علاقهمندان به کامپیوتر، مخصوصاً حوزه طراحی و تحلیل الگوریتمها، میتواند مفید باشد. آشنایی با ریاضیات، برنامهنویسی و داده ساختارها میتواند در درک بهتر مفاهیم این درس کمککننده باشد. محتوای این دوره در نیمسال اول سال تحصیلی ۰۱-۱۴۰۰ در گروه علوم کامپیوتر دانشگاه تهران ارائه شده است.
***این دوره درحال تکمیل است***
فصل اول: مفاهیم مقدماتی:
1 – جلسه 0 – بخش اول: مقدمهای بر درس و سرفصلها
2 – جلسه 0 – بخش دوم: مقدمهای بر درس و سرفصلها
3 – جلسه 1: مقدمهای بر الگوریتمها
4 – جلسه 2: تحلیل الگوریتمها
5 – اسلایدهای طراحی و تحلیل الگوریتم
فصل دوم: روشهای کلاسیک طراحی الگوریتمها:
1 – جلسه 3: روش تقسیم و غلبه
2 – جلسه 4: حل معادلات بازگشتی
3 – جلسه 5: توابع مولد
4 – جلسه 6: ضرب سریعتر اعداد
5 – جلسه 7: ضرب سریعتر ماتریسها (روش استراسن)
6 – جلسه 8: مرتبسازی سریع
7 – جلسه 9: حد پایین برای مسئله مرتبسازی
8 – جلسه 10: مسئله انتخاب کوچکترین عدد
9 – جلسه 11: برنامهریزی پویا
10 – جلسه 12: ضرب دنبالهای از ماتریسها
11 – جلسه 13: درخت جستجوی دودویی بهینه
12 – جلسه 14: طولانیترین زیررشته مشترک (LCS)
13 – جلسه 15: روش حریصانه
14 – جلسه 16: مسئله انتخاب فعالیتها
15 – جلسه 17: مسئله کولهپشتی
16 – جلسه 18: کدگذاری هافمن
17 – جلسه 19: روش بازگشت به عقب
18 – جلسه 20: الگوریتم بازگشت به عقب برای مسئله کوله پشتی
19 – جلسه 21: روش شاخه و تحدید
فصل سوم: نظریه گراف و الگوریتمهای آن:
1 – جلسه 22: مفاهیم اولیه گرافها
2 – جلسه 23: پیمایش سطحی گراف (BFS)
3 – جلسه 24: پیمایش عمقی گراف (DFS)
4 – جلسه 25: مرتبسازی توپولوژیکی
5 – جلسه 26: مؤلفههای همبند گراف
6 – جلسه 27: کوتاهترین مسیر در گراف
7 – جلسه 28: الگوریتم دایکسترا
8 – جلسه 29: الگوریتم بلمن-فورد
9 – جلسه 30: کوتاهترین مسیر بین همه رئوس با ضرب ماتریسها
10 – جلسه 31: کوتاهترین مسیر بین همه رئوس با روش فلوید-وارشال
11 – جلسه 32: درخت پوشای کمینه
12 – جلسه 33: الگوریتمهای درخت پوشای کمینه
فصل چهارم: تطابق رشتهها:
1 – جلسه 34: تطابق دقیق رشتهها
2 – جلسه 35: تطابق رشتهها به کمک همنهشتی (الگوریتم رابین-کارپ)
3 – جلسه 36: تطابق رشتهها به کمک اتوماتا
4 – جلسه 37: تطابق رشتهها به روش KMP
فصل پنجم: نظریه NP-Completeness و شناسایی مسائل سخت:
1 – جلسه 38: الگوریتمهای غیرقطعی
2 – جلسه 39: نظریه NP-Completeness
3 – جلسه 40: اثبات سختی مسئله k-Clique
4 – جلسه 41: اثبات سختی مسئله k-Vertex-Cover
5 – جلسه 42: اثبات سختی مسئله Subset-Sum
6 – جلسه 43: اثبات سختی مسئله دور همیلتونی
7 – جلسه 44: اثبات سختی مسئله Coloring
فصل ششم: روشهای قطعی برای حل مسائل سخت:
1 – جلسه 45: الگوریتمهای شبهچندجملهای
2 – جلسه 46: روش پارامتری
3 – جلسه 47: روش شاخه و تحدید
4 – جلسه 48: روش کاهش نرخ رشد پیچیدگی الگوریتمها
5 – جلسه 49: جستجوی محلی
6 – جلسه 50: جستجوی محلی با عمق متغیر
7 – جلسه 51: دستهبندی مسائل از دیدگاه روشهای جستجوی محلی
فصل هفتم: الگوریتمهای تقریبی:
1 – جلسه 52: مقدمهای بر الگوریتمهای تقریبی
2 – جلسه 53: الگوریتم تقریبی برای مسئله Makespan Scheduling
3 – جلسه 54: الگوریتم تقریبی برای مسئله Vertex Cover
4 – جلسه 55: الگوریتم تقریبی برای مسئله Set Cover
5 – جلسه 56: الگوریتم تقریبی برای مسئله Subset Sum
6 – جلسه 57: مفهوم پایداری الگوریتمهای تقریبی
7 – جلسه 58: الگوریتم تقریبی برای مسئله کولهپشتی ساده
8 – جلسه 59: الگوریتمهای تقریبی برای مسئله کولهپشتی و پایداری آنها
9 – جلسه 60: مفهوم L-Reduction و دستهبندی مسائل از دیدگاه الگوریتمهای تقریبی
فصل هشتم: الگوریتمهای تصادفی:
1 – جلسه 61: مقدمهای بر الگوریتمهای تصادفی
2 – جلسه 62: الگوریتم تصادفی لاسوگاس برای مرتبسازی سریع
3 – جلسه 63: الگوریتم تصادفی لاسوگاس برای انتخاب کوچکترین عدد
4 – جلسه 64: الگوریتم تصادفی لاسوگاس برای Choice روی ماشین ارتباطی
5 – جلسه 65: الگوریتم تصادفی مونتکارلو با خطای یکطرفه
6 – جلسه 66: الگوریتم تصادفی مونتکارلو با خطای دوطرفه
7 – جلسه 67: الگوریتم تصادفی مونتکارلو با خطای نامحدود
8 – جلسه 68: الگوریتمهای تصادفی برای مسائل بهینهسازی
9 – جلسه 69: الگوریتم تصادفی برای مسئله Max-kSAT
10 – جلسه 70: الگوریتم تصادفی برای مسئله Max-Cut
فصل نهم: سایر روشها:
1 – جلسه 71: روش Simulated Annealing
2 – جلسه 72: روش Tabu Search
3 – جلسه 73: الگوریتم ژنتیک
4 – جلسه 74: مقدمهای بر محاسبات مولکولی
5 – جلسه 75: الگوریتم مولکولی یافتن مسیر همیلتونی