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

Design of Algorithms

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

اهداف درس

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

ریز مواد

  • مقدمات و مسائل نمونه (۲ جلسه)
    • حل‌پذیری، تحلیل الگوریتم‌ها، زمان‌های اجرا
    • بزرگ‌ترین زیردنباله‌ی متوالی، مسئله‌ی ۳-مجموع
  • الگوریتم‌های مبتنی بر استقرا (۱ جلسه)
    • ارزیابی چندجمله‌ای‌ها، نگاشت یک‌به‌یک، ستاره‌ی مشهور
  • تقسیم و حل (۲ جلسه)
    • محاسبه‌ی توان، محاسبه‌ی روابط بازگشتی، نزدیک‌ترین زوج نقاط
    • الگوریتم استراسن برای ضرب ماتریس‌ها، تبدیل سریع فوریه
  • الگوریتم‌های حریصانه (۳ جلسه)
    • خرد کردن پول، مسائل زمان‌بندی، کوله‌پشتی کسری
    • فشرده‌سازی: کدگذاری هافمن
    • تطابق پایدار، الگوریتم گیل-شاپلی، قضایای مرتبط
  • برنامه‌ریزی پویا (۴ جلسه)
    • اعداد فیبوناچی، زمان‌بندی بازه‌های وزن‌دار، خرد کردن پول
    • ضرب زنجیره‌ی ماتریس‌ها، کوله‌پشتی، تراز دنباله‌ها
    • بزرگ‌ترین زیردنباله‌ی مشترک، بزرگ‌ترین زیردنباله‌ی افزایشی
    • محاسبه‌ی مجموعه‌ی مستقل روی درخت، درخت دودویی جست‌وجوی بهینه
  • جست‌وجوی فضای حالت (۲ جلسه)
    • روش پس‌گرد، مسئله‌ی هشت وزیر، مجموع زیرمجموعه‌ها
    • انشعاب و حد، فروشنده‌ی دوره‌گرد، درخت بازی، هرس آلفا-بتا
  • الگوریتم‌های گراف (۳ جلسه)
    • درخت فراگیر کمینه: الگوریتم‌های کروسکال و پریم
    • هرم فیبوناچی، تحلیل سرشکن برای کاهش کلید
    • کوتاه‌ترین مسیر بین تمام رأس‌ها: الگوریتم‌های فلوید-وارشال و جانسون
  • تطابق رشته‌ها (۲ جلسه)
    • روش مبتنی بر اثر انگشت، الگوریتم رابین-کارپ
    • تطابق رشته به وسیله‌ی اتوماتا: الگوریتم کنوث-موریس-پرت
  • شبکه‌های شار (۳ جلسه)
    • شار بیشینه و برش کمینه: الگوریتم فورد-فالکرسن
    • بهبود الگوریتم فورد-فالکرسن، بهبودهای ادموندز و کارپ
    • گونه‌ها و کاربردها: تطابق در گراف دوبخشی، مسیرهای مجزا، گرد کردن ماتریس
  • برنامه‌ریزی خطی (۲ جلسه)
    • فرم استاندارد، مدل‌سازی مسائل با برنامه‌ریزی خطی
    • الگوریتم سیمپلکس برای حل برنامه‌ریزی خطی
  • پیچیدگی محاسبات (۳ جلسه)
    • کاهش چندجمله‌ای، مسائل صدق‌پذیری
    • رده‌ی ان‌پی، اثبات ان‌پی‌-تمام بودن یک مسئله، قضیه‌ی کوک
    • دور همیلتنی، رنگ‌آمیزی گراف، مجموع زیرمجموعه‌‌ها
  • الگوریتم‌های تقریبی (۲ جلسه)
    • پوشش راسی، فروشنده‌ی دوره‌گرد، سختی تقریب
    • طرح‌های تقریبی چندجمله‌ای، مسئله‌ی کوله‌پشتی

ارزیابی

  • سه تمرین نظری (۳ نمره)
  • سه تمرین برنامه‌نویسی (۳ نمره)
  • آزمون‌ میان‌ترم (۷ نمره)
  • آزمون پایانی (۷ نمره)
  • یک مسابقه به سبک ای‌سی‌ام (۱‌+ نمره)

مراجع

  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.