طراحی و تحلیل الگوریتم

نام درس طراحی و تحلیل الگوریتم
کد درس 8101424
تعداد واحد 3
نوع درس
مقطع درس کارشناسی
دروس هم نیاز ساختمان داده ها و الگوریتم
دروس پیش نیاز
مطالب پیش نیاز
کتاب (کتب) مرجع
  1. T. Cormen, C. Leiserson, R. Riverst, C. Stein (CLRS) Introduction to Algorithms, MIT Press, Sept. 3rd Edition, 2009.
  2. Levitin, Introduction to the Design and Analysis of Algorithms, Addiso Wesley, 2007
  3. J. Kleinberg, E. Tardos, Algorithm Design, Addison Wesley, 2005.
 
مدرس مسعود اسدپور
اهداف درس

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

دانشجویانی که این درس را با موفقیت پشت سر بگذارند قادر خواهند بود

  • یک درک کلی از روشهای حل مسائل الگوریتمی داشته باشند.
  • با مسائل NP-complete اشنا شده و NP-complete بودن یک مساله را ثابت کنند.
  • پیچیدگی زمانی یک الگوریتم را محاسبه کنند.
  • درکی از الگوریتمهای رایج و مهم داشته و راه حلهای مختلف آنها را از نظر پیچیدگی مقایسه کنند و بدانند هر الگوریتم را در کجا استفاده نمایند.
  • از توابع کتابخانه ای موجود برای الگوریتمهای رایج استفاده نمایند.
 

 

نتایج درس
مباحث

در این درس روش‌های مختلف طراحی و تحلیل الگوریتم‌های سریع و کارا برای حل مسایل مختلف گفته می‌شوند. در ارائه‌ی مطالب بر استفاده از داده‌ساختارهای مناسب و اثبات درستی و تحلیل الگوریتم‌ها تاکید می‌شود

استفاده از کامپیوتر
تکالیف

12 تکلیف (6 تکلیف برنامه نویسی، 6 تکلیف دستی)

پروژه ها
نمره دهی

30%

تکالیف

10%

کوییز

25%

امتحان میان ترم

35%

امتحان پایان ترم

سایر مراجع
  1. U. Manber, Introduction to Algorithms: A Creative Approach, Addison Wesley, 1989.
  2. محمد قدسی و محمد مهدیان، مسئله ­های الگوریتمی، انتشارات فاطمی، 1387
تنظیم کننده مسعود اسدپور
تاریخ تنظیم 1392/11/9