الگوریتم‌های تقریبی
Approximation Algorithms
| مقطع: تحصیلات تکمیلی | گرایش: الگوریتم‌ها و محاسبات |
| نوع درس: نظری | تعداد واحد: ۳ |
| پیش‌نیاز: – | هم‌نیاز: – |
هدف کلی
بسیاری از مسائل بهینه‌سازی در ریاضیات، علوم کامپیوتر و مهندسی ان‌پی-سخت هستند و بنابراین به دست آوردن جواب‌های بهینه برای این دسته از مسائل در زمان چندجمله‌ای با فرض P ≠ NP امکان‌پذیر نیست. الگوریتم‌های تقریبی امکان دست‌یابی به جواب‌هایی نزدیک به جواب بهینه با ضریب تقریب قابل اثبات را برای این دسته از مسائل فراهم می‌آورند. هدف از این درس، آشنایی با مفاهیم و روش‌های متداول برای طراحی الگوریتم‌های تقریبی حول محور مسائل بنیادی در بهینه‌سازی ترکیبیاتی، و نیز آشنایی با روش‌های اثبات سختی تقریب برای برخی از این مسائل است.
سرفصل‌ها
- نمونه مسائل بهینه‌سازی
- روش‌های ترکیبیاتی
- الگوریتم‌های حریصانه
- جستجوی محلی
- طرح‌های تقریبی با زمان چندجمله‌ای (PTAS)
- برنامه‌ریزی پویا روی مقادیر گردشده
- گرد کردن قطعی برنامه‌ریزی خطی
- گرد کردن تصادفی برنامه‌ریزی خطی
- روش اولیه-دوگان
- برنامه‌ریزی نیمه‌معین
- روش‌های اثبات سختی تقریب
ارزیابی پیشنهادی
- تمرین‌ها (دو تا سه تمرین نظری): ۲۵ درصد نمره
- آزمون‌های میان‌ترم و پایانی: ۵۵ درصد نمره
- پروژه پژوهشی: ۲۰ درصد نمره
منابع پیشنهادی
- D. Williamson and D. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.
- V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.
- B. Gartner and J. Matousek. Approximation Algorithms and Semidefinite Programming. Springer, 2012.
- J. Hromkovic. Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. 2nd Edition, Springer, 2010.