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

Design of Algorithms

شماره درس: ۲۰۱۶ تعداد واحد: ۳
نوع درس: نظری پیش‌نیاز: داده‌ساختارها و الگوریتم‌ها

اهداف درس

هدف از این درس، آشنایی دانش‌جویان با روش‌های متداول در طراحی الگوریتم‌های کارا برای مسائل مختلف است. در ارائه‌ی مطالب، بر تحلیل کارایی الگوریتم‌ها و اثبات درستی آن‌ها تأکید خواهد شد. همچنین، برخی داده‌ساختارهای پیشرفته که در طراحی الگوریتم‌های کارا استفاده می‌شوند ارائه خواهد شد.

ریز مواد

  • مقدمات و مسائل نمونه (۱ جلسه)
    • مسئله‌ی ۳-مجموع، معرفی نمادهای $o, \omega$
  • الگوریتم‌های مبتنی بر استقرا (۱ جلسه)
    • ارزیابی چندجمله‌ای‌ها، نگاشت یک‌به‌یک، ستاره‌ی مشهور
  • تقسیم و حل (۱ جلسه)
    • نزدیک‌ترین زوج نقاط، ضرب ماتریس‌ها
  • الگوریتم‌های حریصانه (۲ جلسه)
    • کدگذاری هافمن
    • تطابق پایدار
  • برنامه‌ریزی پویا (۲ جلسه)
    • کوله‌پشتی، تراز دنباله‌ها
    • د.د.ج بهینه، بزرگ‌ترین زیردنباله‌ی افزایشی، محاسبه‌ی مجموعه‌ی مستقل روی درخت
  • جست‌وجوی فضای حالت (۱ جلسه)
    • روش پس‌گرد، انشعاب و حد
  • داده‌ساختارهای پیشرفته (۳ جلسه)
    • تحلیل سرشکن
    • د.د.ج. متوازن: درخت قرمز-سیاه، درخت AVL
    • مجموعه‌های مجزا
    • درخت ترای
  • الگوریتم‌های گراف (۳ جلسه)
    • ترتیب توپولوژیکی، مؤلفه‌های قویاً همبند
    • کوتاه‌ترین مسیر در گراف‌ها: الگوریتم‌های بلمن-فورد
    • کوتاه‌ترین مسیر بین تمام رأس‌ها: الگوریتم‌های فلوید-وارشال و جانسون
    • درخت فراگیر کمینه: الگوریتم‌های کروسکال و پریم
  • تطابق رشته‌ها (۲ جلسه)
    • روش مبتنی بر اثر انگشت، الگوریتم رابین-کارپ
    • تطابق رشته به وسیله‌ی اتوماتا: الگوریتم کنوث-موریس-پرت
  • شبکه‌های شار (۲ جلسه)
    • شار بیشینه و برش کمینه: الگوریتم فورد-فالکرسن
    • گونه‌ها و کاربردها: تطابق در گراف دوبخشی، مسیرهای مجزا، گرد کردن ماتریس

ارزیابی

  • تمرین‌های عملی: ۳ نمره
  • آزمونک‌ها: ۳ نمره
  • آزمون‌ پایان‌دوره: ۱۴ نمره

مراجع

  1. J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley, 2005.
  2. T. Cormen, C. Leiserson, R. Riverst, and C. Stein. Introduction to Algorithms. 3rd Edition, MIT Press, 2009.
  3. U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
  4. G. Brassard, P. Bratley. Algorithmics: Theory and Practice. Prentice-Hall, 1988.