نظریه پیچیدگی
Complexity Theory
| مقطع: تحصیلات تکمیلی | گرایش: الگوریتم‌ها و محاسبات |
| نوع درس: نظری | تعداد واحد: ۳ |
| پیش‌نیاز: – | هم‌نیاز: – |
هدف کلی
هدف از این درس ارائه مدل‌های پایه برای پیچیدگی محاسبه، مروری بر دستاوردهای اصلی نظریه محاسبه، آشنایی با قضایای اساسی این حوزه، شناخت کلاس‌های پیچیدگی زمانی و فضایی اصلی و همچنین مروری بر به‌کارگیری این نظریه در شاخه‌های جدیدتر نظریه محاسبات مانند محاسبات موازی، محاسبات تصادفی، محاسبات کوانتومی و روش‌های رمزنگاری است.
سرفصل‌ها
- مروری بر نظریه ماشین‌های تورینگ
- زبان‌های بازگشتی و به‌طور بازگشتی شمارا
- مروری بر مسائل تصمیم‌ناپذیر
- مروری بر منطق گزاره‌ها و منطق مرتبه‌اول
- تعریف کلاس‌های پیچیدگی زمانی و فضایی
- تعریف کاهش و قضیه کوک-لوین و مسائل NP-Complete
- رده‌های coNP و PSPACE-Complete و مسائل مهم آن‌ها
- رده‌های پیچیدگی الگوریتم‌های تصادفی
- الگوریتم‌های موازی، ساختار درونی کلاس P
- رده‌های پیچیدگی الگوریتم‌های تقریبی و کران‌های تقریب‌ناپذیری
- ارتباط نظریه‌های پیچیدگی و رمزنگاری، اثبات تعاملی
- نظریه پیچیدگی محاسبات کوانتومی
ارزیابی پیشنهادی
- آزمون: آزمون‌های میان‌ترم (۲۵ درصد نمره) و پایان‌ترم (۴۰ درصد نمره)
- تمرین: چند سری تمرین بر اساس متون معرفی شده (۲۰ درصد نمره)
- گزارش پژوهشی: ارائه مقاله‌ای در موضوعات مرتبط که مستلزم مطالعه چند مقاله به‌روز باشد. (۱۵ درصد نمره)
منابع پیشنهادی
- C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
- S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
- D.Z. Du and K.I. Ko. Theory of Computational Complexity. Wiley, 2000.
- I. Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms. Springer, 2005.