طراحی الگوریتم‌ها
| مدرس: | گواهی: رسمی دوزبانه |
| ترم: | پیش‌نیاز: داده‌ساختارها و الگوریتم‌ها |
| زمان ارائه: | محل برگزاری: کلاس مجازی |
هدف کلی
هدف از این درس، آشنایی دانش‌جویان با روش‌های متداول در طراحی الگوریتم‌های کارا برای مسائل مختلف است. در ارائه‌ی مطالب، بر تحلیل کارایی الگوریتم‌ها و اثبات درستی آن‌ها تأکید خواهد شد. همچنین، برخی داده‌ساختارهای پیشرفته که در طراحی الگوریتم‌های کارا استفاده می‌شوند ارائه خواهد شد.
سرفصل‌ها
- مقدمات و مسائل نمونه (۱ جلسه)
- مسئله‌ی ۳-مجموع، معرفی نمادهای 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.