پرش به مطلب اصلی

طراحی و تحلیل الگوریتم‌ها

Design & Analysis of Algorithms​

نام درس:طراحی و تحلیل الگوریتم‌هامقطع:کارشناسی
پیش‌نیاز:ساختمان داده‌هاگروه درس:تخصصی الزامی
هم‌نیاز:نداردنوع درس:نظری
تعداد واحد:3تعداد ساعت:48
حل تمرین:دارد

سرفصل درس:

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/