پیچیدگی محاسبه - نیم‌سال دوم سال 1400

یادآوری مفاهیم اصلی مربوط به نظریه محاسبه و مدل‌های محاسباتی بالاخص ماشین تورینگ، تعاریف مختلف ماشین تورینگ و تأثیر آنها بر زمان محاسبه و حافظه مصرفی، تعیین مدل‌های استاندارد ماشین تورینگ مربوط به پیچیدگی زمانی و حافظه، تعریف کلاس‌های اصلی پیچیدگی زمانی بالاخص P‌، NP‌،EXP ، تعریف کلاس‌های اصلی پیچیدگی حافظه بالاخص L‌، NL‌، PSpace، NP-Completeness و قضیه Cook-Levin، روش‌های مختلف تحویل (Reduction) بالاخص تحویل‌های Karp و Turing ، تکنیک قطری سازی و اثبات قضیه Ladner، قضایای سلسله مراتبی زمانی و حافظه، تعریف NL-Completeness، قضیه Savitch، قضیه Immerman - Szelepcsenyi، سلسله مراتب چند جمله‌ای و ماشین‌های تورینگ Alternating، ماشین‌های تورینگ مجهز به Oracle، پیچیدگی غیر‌ یکنواخت، پیچیدگی مداری و کلاس P/Poly، نسبی سازی (relativization) و قضیه‌های اصلی مربوطه، (مباحث تکمیلی با نظر استاد).

Review of basic concepts as computational models, different types of Turing machines, time and space in Turing machines, standard Turing machines, basic time complexity classes as P, NP, EXP, and NEXP as well as basic space complexity classes as L, NL, and PSPACE, reductions and NP-completeness, diagonalization and Ladner’s theorem, time hierarchy theorems and polynomial hierarchy, Savitch and Immerman – Szelepcsenyi theorems, alternating Turing machines, oracle Turing machines, nonuniform and circuit complexity, relativization, sparse and tally sets and P/Poly, selected topics.

آشنایی با مدل ماشین تورینگ و زبان های فرمال

[1] Arora, Sanjeev, Barak, Boaz, Computational Complexity: A Modern Approach, Cambridge University Press, Cambridge, 2009. 1

[2] Du, Ding-Zhu, Ko, Ker-I, Theory of Computational Complexity, Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. 2

[3] Papadimitriou, Christos H, Computational Complexity, Addison-Wesley Publishing Company, Reading, MA, 1993. 3

[4] Goldreich, Oded, Computational Complexity: A Conceptual Perspective, Cambridge University Press, Cambridge, 2008. 4

این کلاس به صورت آنلاین در اتاق مجازی https://vc.sharif.edu/ch/daneshgar تشکیل می شود.

• حضور و مشارکت فعال در کلاس درس
• در طول نیمسال تحصیلی تمرین هایی برای حل مشخص می شوند که تحویل گرفته خواهند شد
• یک پروژه نهایی برای هر دانشجو تعیین می شود که در پایان نیمسال تحویل گرفته خواهد شد
• آزمون میان ترم (تاثیر: حدود 40 درصد)
• آزمون پایان ترم (تاثیر: حدود 60 درصد)
• اصولا همه آزمون های اصلی درس تجمعی هستند و محتوی آزمون از کل مطالبی که از ابتدای ترم تدریس شده باشند تا جایی که در اطلاعیه آزمون ذکر می شود، خواهد بود.
• نمره نهایی دانشجو در این درس بر اساس تمامی فعالیت های فوق الذکر تعیین می شود و همه میزان تاثیرهای اعلامی تخمینی و صرفا جهت اطلاع از کلیات روش ارزیابی است. به دانشجویان عزیز توصیه می شود که از ابتدای شروع کلاس در فراگیری مطالب جدی باشند و تا انتهای نیمسال و آزمون نهایی از هر نوع تلاش برای جبران عقب افتادگی احتمالی فروگذاری نکنند.