طراحی الگوریتم‌ها
Design of Algorithms
| مقطع: کارشناسی | گرایش: نرم‌افزار |
| نوع درس: نظری | تعداد واحد: ۳ |
| پیش‌نیاز: داده‌ساختارها و الگوریتم‌ها | هم‌نیاز: – |
هدف کلی
هدف از این درس، آشنایی دانش‌جویان با روش‌های متداول در طراحی الگوریتم‌های کارا برای مسائل مختلف است. در ارائه‌ی مطالب، بر تحلیل کارایی الگوریتم‌ها و اثبات درستی آن‌ها تأکید خواهد شد. همچنین، موضوعات مهمی از نظریه‌ی الگوریتم‌ها همچون پیچیدگی محاسباتی، شبکه‌های شار و الگوریتم‌های گراف در این درس ارائه خواهند شد.
سرفصل‌ها
- مقدمات و مسائل نمونه (۲ جلسه)
- حل‌پذیری، تحلیل الگوریتم‌ها، زمان‌های اجرا
- مسائل نمونه، مثال‌هایی از بهبود کارایی با به‌کارگیری روش‌های طراحی
- الگوریتم‌های مبتنی بر استقرا (۱ جلسه)
- ارزیابی چندجمله‌ای‌ها، نگاشت یک‌به‌یک، یافتن همزمان کمینه و بیشینه
- تقسیم و حل (۲ جلسه)
- محاسبه‌ی توان، محاسبه‌ی روابط بازگشتی، نزدیک‌ترین زوج نقاط
- الگوریتم استراسن برای ضرب ماتریس‌ها، تبدیل سریع فوریه
- الگوریتم‌های حریصانه (۳ جلسه)
- مسائل زمان‌بندی، کوله‌پشتی کسری
- فشرده‌سازی، کدگذاری هافمن
- تطابق پایدار، الگوریتم گیل-شاپلی، قضایای مرتبط
- برنامه‌ریزی پویا (۴ جلسه)
- زمان‌بندی بازه‌های وزن‌دار، خرد کردن پول
- ضرب زنجیره‌ی ماتریس‌ها، کوله‌پشتی، تراز دنباله‌ها
- بزرگ‌ترین زیردنباله‌ی مشترک، بزرگ‌ترین زیردنباله‌ی افزایشی
- محاسبه‌ی مجموعه‌ی مستقل روی درخت، درخت دودویی جست‌وجوی بهینه
- جست‌وجوی فضای حالت (۲ جلسه)
- روش پس‌گرد، مسئله‌ی هشت وزیر، مجموع زیرمجموعه‌ها
- انشعاب و حد، فروشنده‌ی دوره‌گرد، درخت بازی، هرس آلفا-بتا
- الگوریتم‌های گراف (۳ جلسه)
- درخت فراگیر کمینه: الگوریتم‌های کروسکال و پریم
- هرم فیبوناچی، تحلیل سرشکن برای کاهش کلید
- کوتاه‌ترین مسیر بین تمام رأس‌ها: الگوریتم‌های فلوید-وارشال و جانسون
- تطابق رشته‌ها (۲ جلسه)
- روش مبتنی بر اثر انگشت، الگوریتم رابین-کارپ
- تطابق رشته به وسیله‌ی اتوماتا: الگوریتم کنوث-موریس-پرت
- شبکه‌های شار (۳ جلسه)
- شار بیشینه و برش کمینه: الگوریتم فورد-فالکرسن
- بهبود الگوریتم فورد-فالکرسن، بهبودهای ادموندز و کارپ
- گونه‌ها و کاربردها: تطابق در گراف دوبخشی، مسیرهای مجزا، گرد کردن ماتریس
- برنامه‌ریزی خطی (۲ جلسه)
- فرم استاندارد، مدل‌سازی مسائل با برنامه‌ریزی خطی
- الگوریتم سیمپلکس برای حل برنامه‌ریزی خطی
- پیچیدگی محاسبات (۳ جلسه)
- کاهش چندجمله‌ای، مسائل صدق‌پذیری
- رده‌ی ان‌پی، اثبات ان‌پی-تمام بودن یک مسئله، قضیه‌ی کوک
- دور همیلتنی، رنگ‌آمیزی گراف، مجموع زیرمجموعه‌ها
- الگوریتم‌های تقریبی (۲ جلسه)
- روش‌های ترکیبیاتی، پوشش راسی، فروشنده‌ی دوره‌گرد
- سختی تقریب، طرح‌های تقریب چندجمله‌ای (اختیاری)
ارزیابی پیشنهادی
- سه تمرین نظری (۳ نمره)
- سه تمرین برنامه‌نویسی (۳ نمره)
- آزمون میان‌ترم (۷ نمره)
- آزمون پایانی (۷ نمره)
- مسابقه برنامه‌سازی (۱+ نمره)
منابع پیشنهادی
- T. Cormen, C. Leiserson, R. Riverst, and C. Stein. Introduction to Algorithms. 4th Edition, MIT Press, 2022.
- J. Kleinberg and E. Tardos. Algorithm Design. 2nd Edition, Pearson, 2022.
- U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
- G. Brassard and P. Bratley. Algorithmics: Theory and Practice. Prentice-Hall, 1988.