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

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.