نظریه محاسبات
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.