وبلاگ رسمی دکتر ماریا افشاری راد
درباره
این وبلاگ صرفا جهت اطلاع رسانی، ثبت تمرینات تحویلی، طرح درس ها و پرسش و پاسخ دانشجویان طراحی شده است. 
اطلاعات تماس
موضوعات
۱۳۹۶ شهریور
طرح درس بهینه سازی ترکیبیاتی
۱۳۹۶/۰۶/۳۱
۲۲:۴۵
ماریا افشاری راد
۱۸۸
۰

مراجع:

[1] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, INC, 1982.

[2] B. Korte and  J. Vygen, Combinatorial Optimization Theory and Algorithms, Springer, Fourth Edition, 2008.

[3] A. Schrijver, A Course in Combinatorial Optimization, lecturer note, Department of Mathematics, Amsterdam, Netherlands, 2008.

[4] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, MIT Press, Third Edition, 2009.

 

ارزیابی درس:

 

 

نمره

تاریخ و توضیح

تمرین + پروژه‌ (پیاده‌سازی و پژوهشی)

5

در طول نیم‌سال

میان ترم

5

 

پایان ترم

10

12/10/96

 

محتوای درس:

 

نام فصل

محتوای فصل

تعداد جلسات

(تقریبی)

فصل اول:  مقدمات گراف و بهینه‌سازی ترکیبیاتی

 

·         تعریف مساله بهینه‌سازی ترکیبیاتی

·         آشنایی با جند مساله ترکیبیاتی: فروشنده دوره‌گرد، برنامهریزی صحیح، خوشه و ...

·         مساله تصمیم‌گیری

·         مقدمات گراف (به عهده دانشجو)

جلسات 1-4

فصل دوم: تحلیل الگوریتمها:

·         تعریف نمادهای O،  و ..

·         مفهوم اندازه مساله

·         تحلیل چند الگوریتم: دایکسترا، فلوید-وارشال و ...

·         پیچیدگی الکوریتمها

·         سیمپلکس چندجملهای نیست.

جلسات 5-9

فصل سوم: جورسازی

·         گراف دوافرازه

·         ماتریس یکهنگه

·         قضیه هال

·         الگوریتم جورسازی برای گراف دوافرازه

·         چندوجهی جورسازی برای گراف  دوافرازه

·         مسائل بزرگترین خوشه و پوشش راسی

جلسات 10-14

فصل چهارم: پیچیدگی الگوریتمها

 

·         رده مسائل P  و NP.

·         چند مثال از مسائل P

·         چند مثال از مسائل NP

·         تعریف کاهش چندجملهای

·         چند مثال از کاهش چند جملهای : فروشنده دورهگرد، خوشه، پوشش راسی و ...

·         رده مسائل NP-Complete و NP-Hard

·         الگوریتم شبه چندجملهای

·         مسائل قویا NP-Hard و ذکر چند مثال

·         بررسی مسائل Subset Sum، Bin Packing، 0-1 Knapsack.

جلسات 15-21

فصل پنجم: الگوریتمهای تقریبی

 

·         تعریف الگوریتم تقریبی

·         مساله پوشش مجموعه

·         الگوریتم حریصانه

·         دو الگوریتم برای مساله پوشش راسی

·         الگوریتمهای α- تقریب

·         پیچیدگی مساله فروشنده دورهگرد متقارن

·         دو الگوریتم برای مساله فروشنده دورهگرد متقارن و اثبات α- تقریب بودن آنها

جلسات22- 27

فصل ششم: الگوریتمهای فراابتکاری

 

الگوریتمهای جستجوی همسایگی، جستجوی ممنوع، تبرید شبیهسازی شده، ژنتیک و ... (به فراخور زمان کلاس)

جلسات 28-30

ارائه سمینار دانشجویان

جلسات 31 و 32

 

پروژه‌ :

دانشجو باید یک پرو‌ژه در این درس انجام دهد. پروژه نخست به صورت پژوهشی بوده و گزارش آن به زبان فارسی و مانند یک مقاله علمی تدوین شود. متن گزارش باید شامل حداقل بخش‌های زیر باشد.

·         عنوان پروژه

·         چکیده پروژه

·         معرفی مساله، کاربردهای آن، درجه سختی مساله، زیر مساله‌های مربوط و ...

·         بررسی روش‌ها

·         الگوریتم‌های بررسی شده (شبه کد یا الگوریتم به زبان فارسی) و مقایسه آنها

·         فهرست مراجع و منابع مورد استفاده همراه با ارجاع به آنها در متن گزارش

گزارش‌ها در اواخر ترم در یک زمان 30 دقیقه‌ای در کلاس ارایه شوند. گزارش نهایی، حداکثر در روز آزمون پایانی به صورت تایپ شده (تنها با زی‌پرشین پذیرفته می‌شود)، تحویل داده شود. 

در این پرو‌ژه بر اساس الگوریتم‌های ارایه شده در کلاس، پیاده‌سازی به روی یک مساله خاص انجام می‌شود. زبان برنامه‌نویسی با انتخاب دانشجو خواهد بود. جزئیات بیشتر در آینده ارایه خواهد شد. در این پروژه دانشجوها می‌توانند به صورت گروه‌های 2 نفری پروژه را انجام دهند.

Useful links:

1.      http://en.wikipedia.org/wiki/Combinatorial_optimization

2.      http://ocw.mit.edu/courses/mathematics/18-433-combinatorial-optimization-fall-2003/

3.      http://ocw.mit.edu/courses/sloan-school-of-management/15-083j-integer-programming-and-combinatorial-optimization-fall-2009/

4.      http://www.or.uni-bonn.de/~vygen/indexeng.html


 
تمامی حقوق این سامانه برای دانشگاه علم و فناوری مازندران محفوظ است
سامانه وبلاگ ویهان
محصول مشترک گروه شرکت های نرم افزاری ویهان و دانشگاه علم و فناوری مازندران
نسخه ۱.۰