نظریه محاسبات

Theory of Computation

شماره درس: ۲۰۲۰	تعداد واحد: ۳
نوع درس: نظری	پیش‌نیاز: داده‌ساختارها و الگوریتم‌ها

اهداف درس

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

ریز مواد

مقدمات (۲ جلسه)
- آشنایی با مفاهیم اصلی و تاریخچه نظریه محاسبات، نظریه پیچیدگی و نظریه زبان‌ها و ماشین‌ها
- مباحث تکمیلی منطق و جبرمجموعه‌ها، مجموعه‌های شمارا، زبان‌ها و گرامرها
ماشین‌های حالت متناهی و زبان‌های منظم (۴ جلسه)
- پذیرنده‌های متناهی قطعی و غیرقطعی، زبان‌های منظّم و عبارات منظّم
- گرامرهای راستگرد و چپ‌گرد خطّی، گرامرهای منظّم، لِم پُمپینگ برای زبان‌های منظّم
زبان‌های مستقل از متن و ماشین‌های پوش دان (۴ جلسه)
- گرامرهای مستقل از متن، زبان‌های مستقل از متن
- اشتقاق چپگرد و راستگرد، درخت اشتقاق، گرامرهای مبهم و نامبهم، زبان‌های ذاتاً مبهم و نامبهم
- ساده‌سازی گرامرهای مستقل از متن و شکل نرمال چامسکی و گریباخ برای آن‌ها
- ماشین‌های پوش‌دان، هم ارزی ماشین‌های پوش‌دان و گرامرهای مستقل از متن، ماشین های پوش دان قطعی
- زبان‌های مستقل از متن قطعی، زبان‌های غیر مستقل از متن، لِم پُمپینگ برای زبان‌های مستقل از متن
محاسبه‌پذیری (۴ جلسه)
- ماشین تورینگ، تِز چِرچ - تورینگ
- تصمیم‌پذیری و تصمیم‌ناپذیری، تشخیص‌پذیری و تشخیص‌ناپذیری زبان‌ها و مسایل
- مسئله توقّف، مسئله تخصیص پُست و نمونه های دیگر مسایل از منظر تصمیم یا تشخیص ناپذیری
- روش تبدیل (کاهش) مسایل برای اثبات تصمیم یا تشخیص‌ناپذیری
نظریه پیچیدگی محاسبات (۴ جلسه)
- پیچیدگی زمانی الگوریتم ها، روش کاهش چندجمله‌ای
- کلاسهای پیچیدگی زمانی شامل کلاس پی، ان‌پی و کو-ان‌پی، تعریف کامل بودن یک مساله در یک کلاس با تاکید بر کلاس مسایل ان‌پی کامل
- روشهای اثبات اثبات ان‌پی‌-کامل بودن یک مسئله، قضیه‌ی کوک-لوین
- نمونه‌هایی از مسایل ان‌پی-کامل مانند مسئله دور همیلتنی، پوشش راسی، مجموع زیرمجموعه‌‌ها و ….
- پیچیدگی حافظه‌ای مسائل و کلاس‌های آن (کلاس حافظه لگاریتمی، چند جمله‌ای و مکمل آن‌ها)
- رابطه کلاس‌های پیچیدگی حافظه‌ای با یکدیگر
- رابطه کلاس‌های پیچیدگی زمانی و حافظه‌ای با یکدیگر

ارزیابی

آزمون تمرین‌ها: ۶ نمره
آزمون پایان دوره: ۱۴ نمره

مراجع

M. Sipser. Introduction to the Theory of Computation. 3rd Edition, Cengage Learning, 2013.
J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to automata theory, languages, and computation. 2nd Edition, Addison-Wesley, 2001.
J. E. Hopcroft and J. D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley, 1979.