درباره دوره: درس طراحی و تحلیل الگوریتم‌ها یکی از مهم‌ترین و پایه‌ای‌ترین دروس در رشته‌های علوم کامپیوتر و همچنین مهندسی کامپیوتر است. هدف از این درس، مطالعه و بررسی روش‌های طراحی الگوریتم‌ها برای حل مسائل مختلف و چگونگی تحلیل و اثبات درستی الگوریتم‌های ارائه شده برای حل آن‌ها است. آشنایی هرچه بیشتر با مسائل در حوزه‌های مختلف علمی باعث افزایش توانایی افراد در ارائه راه‌حل‌های الگوریتمی برای مسائل جدید خواهد شد. همچنین بسیاری از مسائل محاسباتی مطرح در حوزه‌های مختلف علم جزء مسائلی هستند که حل الگوریتمی آن‌ها در زمان قابل‌قبول به‌راحتی امکان‌پذیر نمی‌باشد، در نتیجه دسته‌بندی مسائل و شناسایی مسائل محاسباتی سخت که در زمان قابل‌قبول نمی‌توان جواب آن‌ها را به دست آورد، نیز از اهمیت ویژه‌ای برخوردار است. در این دوره آموزشی، ابتدا به مفاهیم مقدماتی در حوزه طراحی و تحلیل الگوریتم‌ها پرداخته شده و روش‌های کلاسیک برای حل مسائل مختلف به همراه مثال‌های متنوع ارائه می‌شود. برای این منظور روش‌هایی همچون روش تقسیم و غلبه، برنامه‌ریزی پویا، روش حریصانه، بازگشت به عقب و روش شاخه و تحدید موردبحث قرار می‌گیرند. به شکل ویژه، الگوریتم‌های مطرح در حوزه نظریه گراف و همچنین تطابق رشته‌ها مورد بررسی قرار می‌گیرند. پس از آن، به بررسی سختی مسائل با استفاده از نظریه‌های موجود پرداخته می‌شود. سپس روش‌های الگوریتمی موجود برای حل مسائل سخت معرفی و در مورد هر یک از روش‌ها نمونه‌هایی نیز موردبحث قرار می‌گیرند، از جمله این روش‌ها می‌توان به الگوریتم‌های قطعی، الگوریتم‌های تقریبی، الگوریتم‌های تصادفی، روش‌های مکاشفه‌ای و روش‌های محاسباتی نوین اشاره کرد. در بسیاری از این روش‌ها، درستی الگوریتم‌های ارائه شده اثبات و منابع موردنیاز برای اجرای این الگوریتم‌ها به‌صورت دقیق تحلیل می‌شوند. این درس برای تمامی علاقه‌مندان به کامپیوتر، مخصوصاً حوزه طراحی و تحلیل الگوریتم‌ها، می‌تواند مفید باشد. آشنایی با ریاضیات، برنامه‌نویسی و داده ساختارها می‌تواند در درک بهتر مفاهیم این درس کمک‌کننده باشد. محتوای این دوره در نیمسال اول سال تحصیلی ۰۱-۱۴۰۰ در گروه علوم کامپیوتر دانشگاه تهران ارائه شده است. ***این دوره درحال تکمیل است*** فصل اول: مفاهیم مقدماتی: 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: الگوریتم مولکولی یافتن مسیر همیلتونی

درباره دوره: بسیاری از مسائل محاسباتی مطرح در حوزه‌های مختلف علم جزو مسائلی هستند که حل آنها به راحتی امکان‌پذیر نمی‌باشد. در درس نظریه الگوریتم پیشرفته، ابتدا مسائل محاسباتی مختلف مطرح و سختی آنها با استفاده از نظریه‌های موجود مورد بررسی و اثبات قرار می‌گیرد. پس از آن، روش‌های الگوریتمی موجود برای حل مسائل سخت معرفی و در مورد هر یک از روش‌ها نمونه‌هایی نیز مورد بحث قرار می‌گیرد. از جمله این روش‌ها می‌توان به الگوریتم‌های قطعی، الگوریتم‌های تقریبی، الگوریتم‌های تصادفی، روش‌های مکاشفه‌ای و روش‌های محاسباتی نوین (مانند محاسبات مولکولی) اشاره کرد. در بسیاری از این روش‌ها، درستی الگوریتم‌های ارائه شده اثبات و منابع مورد نیاز برای اجرای این الگوریتم‌ها به صورت دقیق تحلیل می‌شود. اسلایدهای کامل درس را می‌توانید از این اینجا دانلود نمایید. کلمات کلیدی درس: مسائل 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 - جلسه بیست و چهارم - الگوریتم‌های تصادفی (تشخیص اول بودن اعداد)