طراحی الگوریتم‌ها
Design of Algorithms
| شماره درس: ۴۰۳۵۴ | تعداد واحد: ۳ |
| مقطع: کارشناسی | نوع درس: نظری |
| پیش‌نیاز: ساختمان داده‌ها و الگوریتم‌ها | هم‌نیاز: – |
اهداف درس
هدف از این درس، آشنایی دانش‌جویان با روش‌های متداول در طراحی الگوریتم‌های کارا برای مسائل مختلف است. در ارائه‌ی مطالب، بر تحلیل کارایی الگوریتم‌ها و اثبات درستی آن‌ها تأکید خواهد شد. همچنین، موضوعات مهمی از نظریه‌ی الگوریتم‌ها همچون پیچیدگی محاسباتی، شبکه‌های شار و الگوریتم‌های گراف در این درس ارائه خواهند شد.
ریز مواد
- مقدمات و مسائل نمونه (۲ جلسه)
- حل‌پذیری، تحلیل الگوریتم‌ها، زمان‌های اجرا
- بزرگ‌ترین زیردنباله‌ی متوالی، مسئله‌ی ۳-مجموع
- الگوریتم‌های مبتنی بر استقرا (۱ جلسه)
- ارزیابی چندجمله‌ای‌ها، نگاشت یک‌به‌یک، ستاره‌ی مشهور
- تقسیم و حل (۲ جلسه)
- محاسبه‌ی توان، محاسبه‌ی روابط بازگشتی، نزدیک‌ترین زوج نقاط
- الگوریتم استراسن برای ضرب ماتریس‌ها، تبدیل سریع فوریه
- الگوریتم‌های حریصانه (۳ جلسه)
- خرد کردن پول، مسائل زمان‌بندی، کوله‌پشتی کسری
- فشرده‌سازی: کدگذاری هافمن
- تطابق پایدار، الگوریتم گیل-شاپلی، قضایای مرتبط
- برنامه‌ریزی پویا (۴ جلسه)
- اعداد فیبوناچی، زمان‌بندی بازه‌های وزن‌دار، خرد کردن پول
- ضرب زنجیره‌ی ماتریس‌ها، کوله‌پشتی، تراز دنباله‌ها
- بزرگ‌ترین زیردنباله‌ی مشترک، بزرگ‌ترین زیردنباله‌ی افزایشی
- محاسبه‌ی مجموعه‌ی مستقل روی درخت، درخت دودویی جست‌وجوی بهینه
- جست‌وجوی فضای حالت (۲ جلسه)
- روش پس‌گرد، مسئله‌ی هشت وزیر، مجموع زیرمجموعهها
- انشعاب و حد، فروشنده‌ی دوره‌گرد، درخت بازی، هرس آلفا-بتا
- الگوریتم‌های گراف (۳ جلسه)
- درخت فراگیر کمینه: الگوریتم‌های کروسکال و پریم
- هرم فیبوناچی، تحلیل سرشکن برای کاهش کلید
- کوتاه‌ترین مسیر بین تمام رأس‌ها: الگوریتم‌های فلوید-وارشال و جانسون
- تطابق رشته‌ها (۲ جلسه)
- روش مبتنی بر اثر انگشت، الگوریتم رابین-کارپ
- تطابق رشته به وسیله‌ی اتوماتا: الگوریتم کنوث-موریس-پرت
- شبکه‌های شار (۳ جلسه)
- شار بیشینه و برش کمینه: الگوریتم فورد-فالکرسن
- بهبود الگوریتم فورد-فالکرسن، بهبودهای ادموندز و کارپ
- گونه‌ها و کاربردها: تطابق در گراف دوبخشی، مسیرهای مجزا، گرد کردن ماتریس
- برنامه‌ریزی خطی (۲ جلسه)
- فرم استاندارد، مدل‌سازی مسائل با برنامه‌ریزی خطی
- الگوریتم سیمپلکس برای حل برنامه‌ریزی خطی
- پیچیدگی محاسبات (۳ جلسه)
- کاهش چندجمله‌ای، مسائل صدق‌پذیری
- رده‌ی ان‌پی، اثبات ان‌پی-تمام بودن یک مسئله، قضیه‌ی کوک
- دور همیلتنی، رنگ‌آمیزی گراف، مجموع زیرمجموعهها
- الگوریتم‌های تقریبی (۲ جلسه)
- پوشش راسی، فروشنده‌ی دوره‌گرد، سختی تقریب
- طرح‌های تقریبی چندجمله‌ای، مسئله‌ی کوله‌پشتی
ارزیابی
- سه تمرین نظری (۳ نمره)
- سه تمرین برنامه‌نویسی (۳ نمره)
- آزمون میان‌ترم (۷ نمره)
- آزمون پایانی (۷ نمره)
- یک مسابقه به سبک ای‌سی‌ام (۱+ نمره)
مراجع
- 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.
- U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
- G. Brassard, P. Bratley. Algorithmics: Theory and Practice. Prentice-Hall, 1988.