ابزار کاربر

ابزار سایت


درس:۴۰۷۶۵

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

Advanced Algorithms

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

اهداف درس

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

ریز مواد

  1. 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. آشنایی با الگوریتم‌های کوانتومی (در صورت وجود وقت)

ارزیابی

  • تمرین: ‎6 یا 7‎ تمرين (30 درصد نمره)
  • آزمون: آزمون‌های ميان‌نیمسال (20 درصد نمره)، و پایان‌نیمسال (25 درصد نمره)
  • ارائه: ارائه‌ در کلاس (5 درصد نمره)‎‎
  • مطالعه: فهم يک مقاله پژوهشی، تهیه خلاصه و ارائه (20 درصد نمره)

مراجع

  • T‎. ‎Cormen‎, ‎C‎. ‎Leiserson‎, ‎R‎. ‎Rivest‎, and C‎. ‎Stein. Introduction to Algorithms. 3rd ed. MIT Press‎, ‎‎2009‎.
  • J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005 (recommended).
  • V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.
  • M. Bazaraa, J. Jarvis, and H. Sherali. Linear Programming and Network Flows. 4th ed. Wiley, 2010 (recommended).
  • F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann. 1992.
درس/۴۰۷۶۵.txt · آخرین ویرایش: 2020/09/26 10:16 توسط محمد علی آبام