سرفصل درس طراحی الگوریتم ها

طراحی الگوریتم ها (شماره درس: ۴٠٣۵۴)

Design of Algorithms

اهداف درس طراحی الگوریتم ها

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

سرفصل های درس طراحی الگوریتم ها

1. مقدمات و مسائل نمونه (٢ جلسه)
   • حل پذیری، تحلیل الگوریتم ها، زمان های اجرا
   • بزرگ ترین زیردنباله ی متوالی، مسئله ی ٣‐مجموع
2. الگوریتم های مبتنی بر استقرا (١ جلسه)
   • ارزیابی چندجمله ای ها، نگاشت يک به يک ،ستاره ی مشهور
3. تقسیم و حل (٢ جلسه)
   • محاسبه ی توان، محاسبه ی روابط بازگشتی، نزدیک ترین زوج نقاط
   • الگوریتم استراسن برای ضرب ماتریس ها، تبدیل سریع فوریه
4. الگوریتم های حریصانه (٣ جلسه)
   • خرد کردن پول، مسائل زمان بندی، کوله پشتی کسری
   • فشرده سازی: کدگذاری هافمن
   • تطابق پایدار، الگوریتم گیل‐شاپلی، قضایای مرتبط
5. برنامه ریزی پویا (۴ جلسه)
   • اعداد فیبوناچی، زمان بندی بازه های وزن دار، خرد کردن پول
   • ضرب زنجیره ی ماتریس ها، کوله پشتی، تراز دنباله ها
   • بزرگ ترین زیردنباله ی مشترک، بزرگ ترین زیردنباله ی افزایشی
   • محاسبه ی مجموعه ی مستقل روی درخت، درخت دودویی جست وجوی بهینه
6. جست وجوی فضای حالت (٢ جلسه)
   • روش پس گرد، مسئله ی هشت وزیر، مجموع زیرمجموعه ها
   • انشعاب و حد، فروشنده ی دوره گرد، درخت بازی، هرس آلفا‐بتا
7. الگوریتم های گراف (٣ جلسه)
   • درخت فراگیر کمینه: الگوریتم های کروسکال و پریم
   • هرم فیبوناچی، تحلیل سرشکن برای کاهش کلید
   • کوتاه ترین مسیر بین تمام رأس ها: الگوریتم های فلوید‐وارشال و جانسون
8. تطابق رشته ها (٢ جلسه)
   • روش مبتنی بر اثر انگشت، الگوریتم رابین‐کارپ
   • تطابق رشته به وسیله ی اتوماتا: الگوریتم کنوث‐موریس‐پرت
9. شبکه های شار (٣ جلسه)
   • شار بیشینه و برش کمینه: الگوریتم فورد‐فالکرسن
   • بهبود الگوریتم فورد‐فالکرسن، بهبودهای ادموندز و کارپ
   • گونه ها و کاربردها: تطابق در گراف دوبخشی، مسیرهای مجزا، گرد کردن ماتریس
10. برنامه ریزی خطی (٢ جلسه)
    • فرم استاندارد، مدل سازی مسائل با برنامه ریزی خطی
    • الگوریتم سیمپلکس برای حل برنامه ریزی خطی
11. پیچیدگی محاسبات (٣ جلسه)
    • کاهش چندجمله ای، مسائل صدق پذیری
    • رده ی ان پی، اثبات ان پی ‐تمام بودن یک مسئله، قضیه ی کوک
    • دور همیلتنی، رنگ آمیزی گراف، مجموع زیرمجموعه ها
12. الگوریتم های تقریبی (٢ جلسه)
    • پوشش راسی، فروشنده ی دوره گرد، سختی تقریب
    • طرح های تقریبی چندجمله ای، مسئله ی کوله پشتی

ارزیابی درس طراحی الگوریتم ها

• سه تمرین نظری (٣ نمره)
• سه تمرین برنامه نویسی (٣ نمره)
• آزمون میان ترم (٧ نمره)
• آزمون پایانی (٧ نمره)
• یک مسابقه به سبک ای سی ام (١ + نمره)

مراجع درس طراحی الگوریتم ها

[1] J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley, 2005.
[2] T. Cormen, C. Leiserson, R. Riverst, and C. Stein. Introduction to Algorithms. 3rd edition, MIT Press, 2009.
[3] U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
[4] G. Brassard, P. Bratley. Algorithmics: Theory and Practice. Prentice-Hall, 1988.