طراحي الگوريتم
طرح كلي درس
نام درس: طراحي الگوريتم ميزان واحد نظري: 3 ميزان واحد عملي:0
شماره درس: روز و ساعت: يكشنبه 2-4 و سهشنبه 9-10 + سه شنبه 10-12 و يكشنبه 4-5
نام استاد: بهروز شاهقلي ساعت و نحوه ارتباط با استاد: شنبه 16-18- دفتر كار
تكاليف دانشجو: تمرين هاي كتاب مرجع - پروژه هاي برنامه نويسي
نمره نهايي: (پروژه: 4 نمره ميان نيمسال: 8 نمره پايان نيمسال: 8)
تاريخ امتحان ميان نيمسال: 5/2/95 تاريخ و ساعت امتحان پايان نيمسال:
تذكرات مهم: پروژه هاي اين درس به صورت حضوري در سايت كامپيوتر توسط دانشجويان انجام مي شود.
| هدف يا اهداف درس: آشنايي با تكنيكها و روشهاي طراحي الگوريتمهاي بهينه |
| بودجه بندي درس: |
| هفته | تاريخ | مبحث | توضيحات |
| اول | | اهميت طراحي الگوريتم با مقايسه چند مثال ساده- يادآوري مفاهيم پيچيدگي زماني و حافظه در مقايسه روشهاي حل يك مسأله | رجوع به مفاهيم مذكور در درس ساختمان داده |
| دوم | | تحليل الگوريتمها- مرتبه پيچيدگي و قضاياي مربوطه | |
| سوم | | معرفي تكنيك تقسيم و غلبه- نمونه هايي از الگوريتمهاي مرتب سازي و جستجوي مبتني بر اين روش | |
| چهارم | | روش ضرب ماتريس اشتراسن، ارائه الگوريتمي براي عمليات حسابي روي اعداد بزرگ- نقايص روش تقسيم و غلبه و مسائلي كه نبايد به اين روش حل كرد. | |
| پنجم | | معرفي روش برنامه نويسي پويا با يك مثال ساده- روش كوتاهترين مسير floyd | |
| ششم | | معرفي مسائل بهينه سازي و نحوه كاربرد برنامه نويسي پويا در حل آن- الگوريتم ساخت درخت جستجوي باينري بهينه، الگوريتم زمانبندي خط توليد | زمانبندي خط توليد از مرجع دوم مطالعه شود |
| هفتم | | الگوريتم پويا براي ضرب زنجيري ماتريسها، معرفي مسأله TSP و روش حل پوياي آن، مفهوم NP، | پروژه اول |
| هشتم | | مواردي كه استفاده از روش پويا توصيه نمي شود- معرفي روش memorization- استفاده از تخمين زننده توابع در مسائل بهينه سازي | memorization در مرجع دوم مطالعه شود |
| نهم | | معرفي روش حل مسأله حريصانه با يك مثال ساده- كدهاي هافمن- مسائل زمانبندي و امكانسنجي حل آنها با روش حريصانه | |
| دهم | | درخت پوشاي بهينه- مسيريابي Dijkstra | |
| يازدهم | | مقايسه روش حريصانه با روش پويا در مسأله Knapsak- نكاتي در رابطه با كارايي روش حريصانه در مسائل بهينه سازي | پروژه دوم |
| دوازدهم | | حل مسأله به روش backtracking، مسأله n وزير | |
| سيزدهم | | مسأله sum-of-subset، رنگ آميزي گراف | |
| چهاردهم | | مسأله دور هميلتوني- مسأله 0-1knapsak | |
| پانزدهم | | بهينه سازي درخت فضاي حالت در روش backtracking و معرفي روش branch and bound- حل مسأله 0-1knapsak به روش مذكور | پروژه سوم |
| شانزدهم | | مسأله TSP و حل آن به روش branch and bound- معرفي اجمالي روشهاي ديگر حل مسأله | |
| منابع: 1. R. E. Neapolitan and K. Naimipour, “Foundations of Algorithms”, 4th Edition, Jones and Barlett publishers, 2009. 2. Cormen, Leisersen, Rivest, and Stein, “Introduction to Algorithms”, 3rd Edition, MIT Press, 2009. |