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

مدرس:	گواهی: رسمی دوزبانه
ترم:	پیش‌نیاز: داده‌ساختارها و الگوریتم‌ها
زمان ارائه:	محل برگزاری: کلاس مجازی

هدف کلی

هدف از این درس، آشنایی دانش‌جویان با روش‌های متداول در طراحی الگوریتم‌های کارا برای مسائل مختلف است. در ارائه‌ی مطالب، بر تحلیل کارایی الگوریتم‌ها و اثبات درستی آن‌ها تأکید خواهد شد. همچنین، برخی داده‌ساختارهای پیشرفته که در طراحی الگوریتم‌های کارا استفاده می‌شوند ارائه خواهد شد.

سرفصل‌ها

مقدمات و مسائل نمونه (۱ جلسه)
- مسئله‌ی ۳-مجموع، معرفی نمادهای o و ω
الگوریتم‌های مبتنی بر استقرا (۱ جلسه)
- ارزیابی چندجمله‌ای‌ها، نگاشت یک‌به‌یک، ستاره‌ی مشهور
تقسیم و حل (۱ جلسه)
- نزدیک‌ترین زوج نقاط، ضرب ماتریس‌ها
الگوریتم‌های حریصانه (۲ جلسه)
- کدگذاری هافمن
- تطابق پایدار
برنامه‌ریزی پویا (۲ جلسه)
- کوله‌پشتی، تراز دنباله‌ها
- د.د.ج بهینه، بزرگ‌ترین زیردنباله‌ی افزایشی، محاسبه‌ی مجموعه‌ی مستقل روی درخت
جست‌وجوی فضای حالت (۱ جلسه)
- روش پس‌گرد، انشعاب و حد
داده‌ساختارهای پیشرفته (۳ جلسه)
- تحلیل سرشکن
- د.د.ج. متوازن: درخت قرمز-سیاه، درخت AVL
- مجموعه‌های مجزا
- درخت ترای
الگوریتم‌های گراف (۳ جلسه)
- ترتیب توپولوژیکی، مؤلفه‌های قویاً همبند
- کوتاه‌ترین مسیر در گراف‌ها: الگوریتم‌های بلمن-فورد
- کوتاه‌ترین مسیر بین تمام رأس‌ها: الگوریتم‌های فلوید-وارشال و جانسون
- درخت فراگیر کمینه: الگوریتم‌های کروسکال و پریم
تطابق رشته‌ها (۲ جلسه)
- روش مبتنی بر اثر انگشت، الگوریتم رابین-کارپ
- تطابق رشته به وسیله‌ی اتوماتا: الگوریتم کنوث-موریس-پرت
شبکه‌های شار (۲ جلسه)
- شار بیشینه و برش کمینه: الگوریتم فورد-فالکرسن
- گونه‌ها و کاربردها: تطابق در گراف دوبخشی، مسیرهای مجزا، گرد کردن ماتریس

ارزیابی

تمرین‌های عملی: ۳ نمره
آزمونک‌ها: ۳ نمره
آزمون‌ پایان‌دوره: ۱۴ نمره

منابع

T. Cormen, C. Leiserson, R. Riverst, and C. Stein. Introduction to Algorithms. 4th Edition, MIT Press, 2022.
J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley, 2005.
U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
G. Brassard, P. Bratley. Algorithmics: Theory and Practice. Prentice-Hall, 1988.