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

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

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

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