ابزار کاربر

ابزار سایت


الگوریتم_های_تقریبی:ریز_مواد

الگوریتم‌های تقریبی

کليات

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

ريز مواد

  1. مقدمات
    • مسائل ان‌پی-بهینه‌سازی
    • الگوریتم‌های تقریبی
    • درجه‌ی تقریب‌پذیری
  2. روش‌های ترکیبیاتی
    • الگوریتم‌های حریصانه
    • جست‌وجوی محلی
    • تکنیک لایه‌بندی
    • هرس پارامتری
    • برنامه‌ریزی پویا
    • گرد کردن
    • روش‌های توری
  3. روش‌های مبتنی بر برنامه‌ریزی خطی
    • گردکردن قطعی (deterministic rounding)
    • گردکردن تصادفی (randomized rounding)
    • روش بیضوی (ellipsoid method)
    • برازش دوگان (dual-fitting)
    • روش اولیه-دوگان (primal-dual method)
    • برنامه‌ریزی نیمه‌معین (semidefinite programming)
    • برنامه‌ریزی برداری (vector programming)
  4. مسائل بهینه‌سازی
    • مسائل پوششی: پوشش رأسی، پوشش مجموعه‌ای
    • مسائل شبکه‌ای: درخت‌های اشتاینر، درخت اشتاینر جمع‌کننده‌ی جایزه
    • مسائل گشت: فروشنده‌ی دوره‌گرد، فروشنده‌ی دوره‌گرد اقلیدسی
    • مسائل برش: برش بیشینه، برش چندگانه
    • مسائل عددی: کوله‌پشتی، بسته‌بندی
    • مسائل هندسی: قطر نقاط، مجموعه‌ی مستقل در مربع‌های واحد
    • مسائل صدق‌پذیری: k-صدق‌پذیری بیشینه
    • مسائل خوشه‌بندی: k-مرکز، مکان‌یابی تسهیلات
    • مسائل زمان‌بندی: زمان‌بندی کارها با پردازنده‌‌های موازی
  5. سختی تقریب
    • اثبات‌های اولیه
    • کاهش با ایجاد فاصله
    • کاهش با حفظ درجه‌ی تقریب

آزمون - تمرین – پروژه‌ی پژوهشی

  • آزمون‌های میان‌ترم و پایان‌ترم (۱۱ نمره)
  • حدود چهار تمرین‌ نظری (۵ نمره)

مراجع

  • V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.
  • D. Williamson and D. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.
الگوریتم_های_تقریبی/ریز_مواد.txt · آخرین ویرایش: 2020/12/10 05:05 توسط حمید ضرابی زاده