نظریه علوم کامپیوتر - نیم‌سال دوم ۱۴۰۰

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

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

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

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

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

نحوه‌ی ارائه‌ی کلاسبه صورت برخط و هم‌زمان.

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

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

زمان‌بندی تمرین‌ها و آزمونک‌ها و میان‌ترم را می‌توانید اینجا مشاهده کنید.