طراحی و تحلیل الگوریتم‌ها
Design & Analysis of Algorithms
نظری
نوع درس:
ندارد
هم‌نیاز:
48
تعداد ساعت:
3
تعداد واحد:
دارد
حل تمرین:
سرفصل درس:
1- آنالیز و ارزیابی الگوریتم‌ها (مقدمه ای بر پیچیدگی)
2- رویکرد تقسیم و غلبه و حل مسائل مربوط به آن، مانند الگوریتم‌های مرتب‌سازی سریع و ادغامی، الگوریتم استراسن برای ضرب ماتریس های بزرگ
3- رویکرد برنامه‌نویسی پویا و حل مسائل مربوط به آن، مانند بزرگترین زیررشته مشترک و هم تراز کردن دنباله ها، ضرب زنجیره ای ماتریس ها، درخت جستجوی بهینه
4- رویکرد حریصانه و حل مسائل مربوط به آن، مانند الگوریتمی حریصانه برای مسائل زمان بندی، الگوریتمی حریصانه برای مسأله انتخاب فعالیت های بیشینه، درخت پوشای کمینه.
5- رویکرد برگشت به عقب و حل مسائل مربوط به آن، مانند مسأله‌ی N-وزیر، رنگ‌آمیزی گراف
6- رویکرد شاخه و کران و حل مسائل مربوط به آن، مانند کوله پشتی
7- الگوریتم‌های گراف، پیمایش سطحی و عمقی، کوتاهترین مسیر، درخت پوشای مینیم ، مؤلفه های همبندی، مرتب سازی توپولوژیکی
8- انواع الگوریتم‌های جستجو و مقایسه آنها
۹- مقدمه ای بر پیچیدگی محاسبات و کلاس های NP-hard و P,NP,NP – complete
منابع:
Neopolitan, R. (2015). Foundations of algorithms. Jones & Bartlett Learning.
Demaine, E. (2020), MIT Course, Design And Analysis Of Algorithms, https://erikdemaine.org/classes/
Kleinberg, J., & Tardos, E. (2005). Algorithm Design. Addison Wesley.
Cormen, T., Leiserson, C., Rivest, R., & Stein, C. (2009). Introduction to Algorithms (3rd Ed.). MIT Press.
Manber, U. (1989). Introduction to Algorithms: A Creative Approach. Addison-Wesley.
Brassard, G., & Bratley, P. (1988). Algorithmics: Theory and Practice. Prentice-Hall.
Berkeley Course: Efficient Algorithms and Intractable Problems, Fall 2023, https://cs170.org/
Last updated