بهینه‌سازی ترکیبیاتی
Combinatorial Optimization
| مقطع: تحصیلات تکمیلی | گرایش: الگوریتم‌ها و محاسبات |
| نوع درس: نظری | تعداد واحد: ۳ |
| پیش‌نیاز: – | هم‌نیاز: – |
هدف کلی
هدف این درس آشنایی دانشجویان با بهینه‌سازی ترکیبیاتی از طریق بررسی مسائل بهینه‌سازی و الگوریتم‌های خاص این حوزه از جمله الگوریتم‌های سیمپلکس، الگوریتم‌های اولیه-دوگان، دوگانی و برنامه‌ریزی خطی صحیح است.
سرفصل‌ها
- مسائل بهینه‌سازی
- مجموعه‌ها و توابع محدب
- هندسه‌ی برنامه‌ریزی خطی
- دوگان برنامه‌ریزی خطی
- الگوریتم سیمپلکس
- دوگان الگوریتم سیمپلکس
- الگوریتم‌های اولیه-دوگان
- الگوریتم‌های شبکه‌های شار
- مسائل تطابق و کوتاه‌ترین مسیر
- برنامه‌ریزی خطی صحیح
- کاربرد در الگوریتم‌های تقریبی
ارزیابی پیشنهادی
- تمرین‌های نظری: ۳ نمره
- آزمون‌های میان‌ترم و پایانی: ۱۵ نمره
- گزارش پژوهشی: ۲ نمره
منابع پیشنهادی
- C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 1998.