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

• مباحث مقدماتی: داده ساختارهای پایه ای شامل لیست، صف، پشته، درخت، هرم و گراف، روشهای تحلیل کارایی و اثبات صحت الگوریتم
• الگوریتم های بدیهی: طراحی الگوریتم ها به روش کورکورانه (Force-Brute) و جستجوی کامل فضای حالت (Search Exhaustive).
• استقرا: طراحی الگوریتم های بازگشتی مبتنی بر استقرا و کاهش و غلبه (Conquer and Decrease).
• تقسیم و حل: تکنیک طراحی الگوریتم مبتنی بر تقسیم و حل (Conquer and Divide) و تبدیل و حل (Conquer and Transform).
• حریصانه: روش حریصانه (Greedy) در طراحی الگوریتم
• برنامه ریزی پویا: حل مسائل با استفاده از روش برنامه ریزی پویا (ِProgramming Dynamic).
• بهبود تدریجی: طراحی الگوریتم به روش بهبود تدریجی (Improvement Iterative)
• الگوریتم های گراف: درخت پوشای کمینه و کوتاه ترین مسیرها.
• طبقه بندی مسائل و کلاسهای پیچیدگی: کلاس P و NP ،کاهش مسائل، مسائل NP⁃تمام.
• روش های مواجهه با مسائل سخت: روش های مبتنی بر Backtrack و bound-and-Branch ،الگوریتم های تقریبی.

این درس در ادامه درس ساختمان داده ها ارائه خواهد شد که در آن علاوه بر نیاز به تسلط بر داده ساختارها و الگوریتم های پایه ای و آشنایی با روش های تحلیل کارایی الگوریتم ها نیز ضروری است. همچنین، برای پیاده سازی پروژهای عملی، تسلط بر یک زبان برنامه نویسی مورد نیاز است.

Anany Levitin. “Design and Analysis of Algorithms”. 3rd Edition, Pearson, 2012

J. Kleinberg and E. Tardos. “Algorithm Design”. Addison Wesley, 2005

T. Cormen, C. Leiserson, R. Riverst, and C. Stein. “Introduction to Algorithms”. 3rd edition, MIT Press,2009

کلاس درس در روزهای یکشنبه و سه شنبه از ساعت 9:0 الی 10:30 در کلاس مجازی دکتر زارعی برگزار خواهد شد.

• تمرین: 4 نمره (شامل 4 سری تمرین )
• آزمون کوتاه و فعالیت کلاسی: 2 نمره ( آزمون کوتاه بدون اطلاع قبلی گرفته می شود.)
• تمرین برنامه نویسی: 4 نمره ( شامل ۳ تمرین برنامه نویسی خواهد بود.)
• میان‌ترم: 4 نمره
• پایان‌ترم: 6 نمره

کلاس حل تمرین در روز چهارشنبه از ساعت 10:00 الی 12:00 در کلاس مجازی برگزار خواهد شد.