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

منابع و مراجع درس:

کتاب طراحی الگوریتمها نویسنده ریچارد نیپولیتن
کتاب طراحی الگوریتمها نویسنده دکتر محمود نقیب زاده
کتاب طراحی الگوریتمها نویسنده کرمن

سرفصل درس و جزوه:

فصل اول: مفاهیم اولیه، مرتبه زمانی و تحلیل الگوریتمها - تمرین ها
فصل دوم: روش تقسیم و غلبه (Divide and Conquer) - تمرین ها
فصل سوم: روش حریصانه (Greedy Approach) - تمرین ها
فصل چهارم: روش برنامه نویسی پویا (Dynamic Programming)-تمرین ها
فصل پنجم: روشهای جستجو (Backtracking-Branch & Bound)-تمرین ها

طرح درس بر اساس آخرین سرفصل وزارت علوم:

طرح درس قدیمی مورخ 1389/11/10
طرح درس جدید مورخ 1400/02/09

نحوه ارزشیابی:

کوئیز 1 نمره (نمره مازاد 20)
تمرین های کلاسی 2 نمره
پروژه برنامه نویسی 4 نمره (1 نمره مازاد 20)
امتحان میانترم 5 نمره
امتحان پایان ترم 10 نمره

پروژه برنامه نویسی:

پروژه ترم دوم سال تحصیلی 98-97

الف) الگوریتم دایجسترا: تعیین کوتاهترین مسیرها از مبداء واحد
ب) الگوریتم پردازش رشته: می خواهیم رشته X = x₁x₂x₃... x_n را به رشته Y = y₁y₂y₃... y_mتبدیل کنیم به طوری که هزینه مجموع اعمال ویرایشی انجام شده مینیمم باشد. اعمال ویرایشی عبارتند از:

D = Delete -------> D(x_i) g

I = Insert -------> I(y_j) g

C = Change -------> C(x_i,y_j) g

برای تحویل پروژه یک فایل pdf با محتویات زیر ایجاد نمایید و در روز تحویل پروژه پرینت کامل آن را به همراه کد مربوطه برای اجراء بیاورید. محتویات فایل pdf عبارتند از:

- نام و نام خانوادگی و شماره دانشجویی
- عنوان مسئله
- ایده حل مسئله (روش حل مسئله)
- تشریح جزئیات حل مسئله
- ارائه کد حل مسئله (با توضیحات)
- تست یک نمونه ورودی و خروجی از برنامه نهایی

نمونه سوالات امتحانی:

امتحان میانترم 1393/09/08

امتحان پایان ترم 1394/03/24

سایت ها و مطالب مفید :

فایل فلش الگوریتم های مختلف: در این فایل بسیاری از الگوریتم های مختلف بصورت تجسمی و تعاملی توضیح داده شده اند. این فایل توسط گروه کامپیوتر دانشگاه سان فرانسیسکو تولید شده است.
سایت انواع سوالات طراحی الگوریتم ها: در این سایت انواع مختلف سوالات طراحی الگوریتم ها و مسابقات ACM با دسته بندی های مناسبی به همراه پاسخ آنها ارائه شده است.
سایت تجسمی برای الگوریتمها: در این سایت، اکثر الگوریتم های مورد بحث در علوم کامپیوتر بصورت تصویری و تعاملی شرح داده شده است. می توان آن را یکی از هزارن صفحه تجسم سازی اطلاعات و الگوریتم ها در وب دانست که روز به روز بر تعداد آنها افزوده می شود
سایت ارائه الگوریتمها از سایت های دیگر: این سایت سعی کرده لینک تمامی جاهایی که الگوریتمی را پیاده سازی کرده یا به صورت انیمیشن (فلش/ جاوا اپلت/HTML5/ ...) در اختیار سایرین قرار داده اند را جمع آوری کند.