نظریه پیچیدگی

Complexity Theory

مقطع: تحصیلات تکمیلی گرایش: الگوریتم‌ها و محاسبات
نوع درس: نظری تعداد واحد: ۳
پیش‌نیاز: – هم‌نیاز: –

هدف کلی

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

سرفصل‌ها

  1. مروری بر نظریه ماشین‌های تورینگ
  2. زبان‌های بازگشتی و به‌طور بازگشتی شمارا
  3. مروری بر مسائل تصمیم‌ناپذیر
  4. مروری بر منطق گزاره‌ها و منطق مرتبه‌اول
  5. تعریف کلاس‌های پیچیدگی زمانی و فضایی
  6. تعریف کاهش و قضیه کوک-لوین و مسائل NP-Complete
  7. رده‌های coNP و PSPACE-Complete و مسائل مهم آن‌ها
  8. رده‌های پیچیدگی الگوریتم‌های تصادفی
  9. الگوریتم‌های موازی، ساختار درونی کلاس P
  10. رده‌های پیچیدگی الگوریتم‌های تقریبی و کران‌های تقریب‌ناپذیری
  11. ارتباط نظریه‌های پیچیدگی و رمزنگاری، اثبات تعاملی
  12. نظریه پیچیدگی محاسبات کوانتومی

ارزیابی پیشنهادی

منابع پیشنهادی

  1. C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
  2. S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
  3. D.Z. Du and K.I. Ko. Theory of Computational Complexity. Wiley, 2000.
  4. I. Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms. Springer, 2005.