توصیف درس

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

سرفصل‌های تقریبی

• اتوماتا، لم پمپ کردن، عبارت‌های منظم
• ماشین تورینگ
• محاسبه‌پذیری، تصمیم‌پذیری، تشخیص‌پذیری
• قضیه بازگشت
• پیچیدگی محاسبات (P و NP و بقیه خانواده)
• پیچیدگی حافظه (PSPACE و L و NL)
• محاسبات تصادفی
• برخی مباحث پیشرفته‌تر در پیچیدگی محاسبات
• (احتمالا) کمی محاسبات نامتداول

پیش‌نیازها

درس الگوریتم و ساختمان داده پیش‌نیاز این درس هستند. آشنایی با اتوماتا و درس زبان‌ها و ماشین‌ها که با این درس اشتراک زیادی دارند خیلی به فهم این درس کمک می‌کنند.

منابع درس

درس مشابه با درس نظریه محاسبه آقای سیپسر خواهد بود.

Sipser, Michael. Introduction to the Theory of Computation. 3rd ed. Cengage Learning, 2012. ISBN: 9781133187790.

نحوه‌ی ارائه‌ی کلاس

به صورت برخط و هم‌زمان.

نحوه ارزش‌یابی

• تمرین: ۵ نمره
• آزمونک: ۳ نمره
• میان‌ترم: ۵ نمره
• پایان‌ترم: ۷ نمره

در مجموع برای تحویل تمرین‌ها می‌توانید ۱۰ روز تاخیر بدون کسر نمره داشته باشید که ساعتی محاسبه می‌شود.

جدول زمانی و توضیحات تمرین‌ها

دستیاران آموزشی درس (به ترتیب الفبا)