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