مباحث پیشرفته در الگوریتم‌ها - نیم‌سال اول 1401

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

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

1. مباحث مقدماتی:
   • معرفی مدل های محاسباتی شامل حافظه اصلی، حافظه خارجی و جویباری
   • معرفی مدل های الگوریتمی شامل قطعی، تقریبی، تصادفی، موازی و برخط
   • معرفی معیارهای ارزیابی کارایی شامل حافظه و زمان اجرا
   • معرفی مدل‌های تحلیل شامل بهترین حالت، بدترین حالت، حالت متوسط، تحلیل سرشکنی و تحلیل رقابتی
2. داده ساختارهای پیشرفته:
   • انواع هرم‌ها (دودویی، دوجمله‌ای، فیبوناچی و چاق)
   • درخت Splay
   • درخت و آرایه پیشوندی و کاربرد آن‌ها
3. الگوریتم های پیشرفته:
   • الگوریتم‌های تطابق رشته ها شامل Suffix Tree and Suffix Array, Moore-Boyer, KMP, Automata Finite, Karp-Rabin
   • الگوریتم‌های شبکه شاره شامل
     1. Ford-Fulkerson, Max-flow min-cut theorem, Augmenting path, Capacity-scaling, Shortest augmenting path
     2. Preflow-push, FIFO preflow-push
     3. Dynamic trees
     4. کاربردها شامل Disjoint paths and network connectivity, Bipartite matchings, Unit capacity simple networks
4. پیچیدگی محاسبه:
   • کلاس‌های پیچیدگی P و NP
   • اثبات NP⁃تمام بودن مساله ارضاپذیری
   • اثبات مسائل دیگری از کلاس NP⁃تمام در حوزه‌های مختلف شامل ترکیبیات و گراف، مسائل عددی، مسائل منطقی، مجموعه‌ها و افراز
   • عدم تقارن و کلاس co-NP
   • مسائل کلاس PSPACE
5. الگوریتم‌های تقریبی:
   • معرفی الگوریتم های تقریبی با ضریب تقریب ثابت
   • معرفی نتایج سختی (Hardness-Result) و عدم وجود الگوریتم با ضریب ثابت
   • نمونه الگوریتم‌های با ضریب تقریب لگاریتمی
   • حل نمونه مسائل پوشش راسی
   • فروشنده دوره گرد و حالت متریک آن و درخت اشتاینر
   • معرفی الگوریتم های تقریبی PTAS و FPTAS و حل نمونه مسائل مانند کوله پشتی
   • استفاده از برنامه ریزی خطی برای حل تقریبی مسائل و معرفی تکنیک گردکردن تصادفی، گردکردن تدریجی و integrality gap
   • معرفی روش semi-definite programming برای حل تقریبی مسائل
6. الگوریتم‌های تصادفی:
   • معرفی دلایل و کاربردهای الگوریتم‌ها و روش‌های تصادفی برای افزایش سرعت، سادگی و امکانپذیری الگوریتم‌ها
   • اثبات ویژگی‌ها به روش احتمالاتی (Method Probabilistic)
   • حل برخی مسائل بصورت تصادفی از جمله برش کمینه، پوشش مجموعه‌ای، ضرب ماتریس‌ها و تطابق رشته‌ها و چندجمله‌ای‌ها

• تمرین: 6 نمره
• میان‌ترم: 5 نمره
• پایان‌ترم: 6 نمره
• تحقیق و کار پژوهشی: 3 نمره

برای دانشجویان مقطع کارشناسی ثبت نامی در درس، نمره بخش تحقیق و کار پژوهشی روی باقی بخش‌های درس پخش خواهد شد.

1. T. Cormen, C. Leiserson, R. Riverst, and C. Stein. “Introduction to Algorithms”. 3rd edition, MIT Press, 2009.
2. V.J. Vazirani. “Approximation Algorithms”. Springer, 2003.