دانشکده مهندسی کامپیوتر

دانشگاه صنعتی شریف

ابزار کاربر

ابزار سایت

محل شما: فهرست » سرفصل دروس » نظریه پیچیدگی

نوار کناری

فهرست مطالب


گروه‌های آموزشی

درس:۴۰۷۷۵

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

Theory of Complexity

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

اهداف درس

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

ریز مواد

  • مروری بر نظریه ماشین‌های تورینگ، ماشین‌های تورینگ چند نواری و غیرقطعی (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. (۲ جلسه)
  • کلاس‌های پیچیدگی الگوریتم‌های تقریبی، حدود تقریب پذیری و تقریب ناپذیری. (۲ جلسه)
  • رابطه نظریه‌های پیچیدگی و رمزنگاری. اثبات تعاملی (Iinteractive 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.
درس/۴۰۷۷۵.txt · آخرین ویرایش: 2019/12/26 01:59 (ویرایش خارجی)

کلیه‌ی حقوق این سایت متعلق به دانشکده‌ی مهندسی کامپیوتر است.