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

Complexity Theory

شماره درس: ۴۰۷۷۵ تعداد واحد: ۳
مقطع: کارشناسی ارشد نوع درس: نظری
پیش‌نیاز: – هم‌نیاز: –

اهداف درس

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

ریز مواد

  • مروری بر نظریه ماشین‌های تورینگ، ماشین‌های تورینگ چند نواری و غیرقطعی (nondeterministic)، تز تورینگ-چرچ، مسائل و زبان‌های بازگشتی و به طور بازگشتی شمارا، تعریف مفاهیم زمان اجرا و فضای مصرفی یک الگوریتم (۲ جلسه)
  • مروری بر مسائل تصمیم ناپذیر، مساله توقف و انواع آن، قضیه رایس، روش قطری‌سازی (Diagonalization) (۲ جلسه)
  • مروری بر منطق گزاره‌ها و منطق مرتبه‌اول، مدل‌های حساب، قضایای صحت و تمامیت نظام استنتاجی منطق مرتبه‌اول، قضیه تصمیم‌ناپذیری منطق مرتبه‌اول، قضایای ناتمامیت گودل (۴ جلسه)
  • تعریف کلاس‌های پیچیدگی زمانی و فضایی در حالت کلی و قضایای اساسی ارتباط آن‌ها. قضیه سلسله مراتبی بودن (Hierarchy) و قضیه Gap در حوزه پیچیدگی زمانی و فضایی، مروری بر کلاس‌های زمانی P، NP، EXP و NEXP و کلاس‌های مکمل آن‌ها. مروری بر کلاس‌های فضایی L، NL، PSPACE، NPSPACE و کلاس‌های مکمل آن‌ها و ارتباط آن‌ها با کلاس‌های زمانی (۳ جلسه)
  • تعریف تقلیل (Reduction) و مسائلی که برای یک کلاس C-تمام (C-Complete) هستند. بررسی کلاس‌های مسایل P-Complete و NP-Complete. قضیه کوک-لوین و مباحث مرتبط با رابطه کلاس P و NP (۲ جلسه)
  • مروری بر برخی مسایل معروف NP-Complete (۲ جلسه)
  • کلاس coNP و مسائل توابع. کلاس PSPACE-Complete و مسایل مهم در آن (۱ جلسه)
  • کلاس‌های پیچیدگی الگوریتم‌های تصادفی، کلاس‌های RP، CoRP، ZPP، و BPP، پیچیدگی مداری (Circuit Complexity) (۳ جلسه)
  • الگوریتم‌های موازی، ساختار درونی کلاس P (۲ جلسه)
  • کلاس‌های پیچیدگی الگوریتم‌های تقریبی، حدود تقریب پذیری و تقریب ناپذیری (۲ جلسه)
  • رابطه نظریه‌های پیچیدگی و رمزنگاری. اثبات تعاملی (Interactive Proof) (۲ جلسه)
  • مباحث ویژه مانند نظریه پیچیدگی در حضور ماشین‌های تورینگ پیشگو (Oracle TM)، ماشین تورینگ تناوبی (Alternating TM)، نظریه پیچیدگی محاسبات کوانتومی (۳ جلسه)

ارزیابی

  • آزمون: آزمون‌های میان‌نیم‌سال (۲۵ درصد نمره) و پایان‌نیم‌سال (۴۰ درصد نمره)
  • تمرین: چند سری تمرین بر اساس متون معرفی شده (۲۰ درصد نمره)
  • گزارش پژوهشی: ارائه مقاله‌ای در موضوعات مرتبط که حداقل مستلزم مطالعه پنج مقاله به‌روز باشد. (۱۵ درصد نمره)
  • ارائه: ارائه یک موضوع منتخب در کلاس (±۱۰ درصد نمره)

مراجع

  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.