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

Advanced Algorithms

شماره درس: ۴۰۷۶۵ تعداد واحد: ۳
مقطع: کارشناسی ارشد نوع درس: نظری
پیش‌نیاز: – هم‌نیاز: –

اهداف درس

هدف اصلی این درس، ارائه چند موضوع‌ مهم و تکمیل بخش‌هایی از درس کارشناسی «طراحی و تحلیل الگوریتم‌ها» است که برای گرفتن درس‌های ارشد نظری بعدی مورد نیاز است. این درس برای دانشجویان سایر رشته‌های ارشد مهندسی کامپیوتر چون هوش مصنوعی و سیستم‌های نرم‌افزاری توصیه می‌شود.

ریز مواد

  1. درهم‌سازی (۲ جلسه)
    • درهم‌سازی کامل (perfect hashing)
    • درهم‌سازی سراسری (universal hashing)
    • جدول‌های پویا (dynamic tables)
  2. رده‌های پیچیدگی (۳ جلسه)
    • تاریخچه کوتاه و تعریف‌ها
    • مفهوم کاهش
    • مسئله‌های کلاسیک و ان‌پی-کامل
    • رده‌های دیگر چون P# و NC و P-complete
  3. آشنایی با الگوریتم‌های تقریبی (۳ جلسه)
    • پوشش گره‌ای (vertex cover)
    • پوشش مجموعه کمینه (min set cover)
    • کوتاه‌ترین ابررشته (shortest superstring)
    • فروشنده دوره‌گرد (TSP)
  4. شبکه شار پیشرفته و الگوریتم‌های شبکه (۴ جلسه)
    • تاریخچه کوتاه و تعریف‌ها
    • الگوریتم‌های push-relabel، relabel-to-front
    • min-cost flow و برخی از الگوریتم‌های شبکه
  5. برنامه‌ریزی خطی (۴ جلسه)
    • معرفی
    • محدودیت تفاضل
    • با ابعاد محدود
    • الگوریتم سیمپلکس
    • اثبات و تحلیل
    • دوگانی
  6. داده‌ساختارهای پیشرفته (۳ جلسه)
    • هرم فیبوناچی
    • van Emde Boas tree
  7. الگوریتم‌های برخط (۲ جلسه)
  8. آشنایی با هندسه محاسباتی (۳ جلسه)
  9. آشنایی با الگوریتم‌های موازی (۳ جلسه)
  10. الگوریتم‌های چندریسه‌ای (۲ جلسه)
  11. آشنایی با الگوریتم‌های کوانتومی (در صورت وجود وقت)

ارزیابی

مراجع

  1. T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. 4th edition, MIT Press, 2022.
  2. J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005.
  3. V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.
  4. M. Bazaraa, J. Jarvis, and H. Sherali. Linear Programming and Network Flows. 4th edition, Wiley, 2010 (recommended).
  5. F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann. 1992.