جلسه اول کلاس آنلاین نظریه زبان‌ها و ماشین‌ها - ویژه کنکور ۹۹ - رایگان

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

منابع درسی:
• کتاب مرجع، معرفی زبان‌های فرمال و آتوماتا نوشته پیتر لینز
• کتاب مرجع، نظریه محاسبات نوشته مایکل سیپسر
• کتاب مرجع، معرفی زبان ها و نظریه محاسبات نوشته مارتین
• کتاب مرجع، معرفی نظریه آتوماتا، زبان‌ها و محاسبات نوشته هاپکرافت، موتوانی و اولمان

سرفصل نظریه زبان‌ها و ماشین‌ها به ترتیب زیر است:

• فصل اول: مقدمه‌ای بر نظریه محاسبات، مباحث پیشنیاز و مفاهیم اولیه
نظریه‌ی مجموعه‌ها، اصول منطق، روش‌های اثبات، رابطه و تابع، مجموعه‌های شمارا و ناشمارا، مفاهیم پایه گراف و درخت، روابط بازگشتی، نمادهای مجانبی، الفبا، رشته، زبان‌، عملیات روی رشته‌ها و زبان‌ها، مدل بازگشتی، مختصری بر گرامرها، آتوماتا

• فصل دوم: ماشین‌های حالت متناهی
ماشین پذیرنده متناهی قطعی، ماشین پذیرنده متناهی غیرقطعی، تبدیل بین DFA وNFA ، ماشین DFA کمینه، ماشین‌ مترجم متناهی

• فصل سوم: زبان‌های منظم
عبارت‌های منظم، گرامرهای منظم، زبان‌های منظم و ارتباط بین این مدل‌ها

• فصل چهارم: ویژگی‌های زبان‌های منظم
خصوصیات بستاری زبان‌های منظم، تصمیم پذیری و خواص الگوریتمیک زبان‌های منظم، زبان‌های نامنظم، لم تزریق زبان‌های منظم، قضیه Myhill–Nerode، دیگر روش‌های تشخیص یک زبان منظم و خانواده‌های زبان‌های زیرمجموعه زبان‌های منظم

• فصل پنجم: زبان‌های مستقل از متن
گرامرهای مستقل از متن، زبان‌های مستقل از متن، اشتقاق، اشتقاق چپ‌گرد و راست‌گرد، پارس یا تجزیه، مسئله عضویت، ابهام در گرامرهای مستقل از متن و زبان‌ها

• فصل ششم: ساده‌سازی گرامرهای مستقل از متن
تبدیلات روی گرامرهای مستقل از متن، فرم‌های نرمال چامسکی و گریباخ، الگوریتم عضویت CYK

• فصل هفتم: ماشین‌های پشته‌ای PDA
ماشین پشته‌ای غیرقطعی، ارتباط بین زبان‌های مستقل از متن و ماشین‌های پشته‌ای، ماشین پشته‌ای قطعی و گرامرهای معادل آن‌ها

• فصل هشتم: ویژگی‌های زبان‌های مستقل از متن
خصوصیات بستاری زبان‌های مستقل از متن، تصمیم پذیری و خواص الگوریتمیک در زبان‌های مستقل از متن، لم تزریق زبان‌های مستقل از متن قطعی و خطی و روش‌های تشخیص یک زبان مستقل از متن

• فصل نهم: ماشین‌های تورینگ
ماشین تورینگ استاندارد، ماشین تورینگ پذیرنده و محاسبه‌گر، ترکیب ما‌شین‌های تورینگ، تز تورینگ

• فصل دهم: انواع مدل‌های ماشین تورینگ
نسخه‌های مختلف از ماشین تورینگ، تورینگ قطعی و غیرقطعی، تورینگ Universal، ماشین کراندار خطی

• فصل یازدهم: دسته‌بندی زبان‌های صوری و آتوماتا
زبان‌های بازگشتیREC و بازگشتی شمارش‌پذیر RE، مسئله توقف، گرامرهای بدون محدودیت و گرامرهای حساس به متن و زبان‌های مرتبط، سلسله مراتب چامسکی، خصوصیات بستاری، تصمیم پذیری و خواص الگوریتمیک زبان‌های REC وRE و CS،

• فصل دوازدهم: محاسبه‌پذیری
محاسبه پذیری و محاسبه ناپذیری، کاهش‌پذیری، قضیه رایس، کلاس‌های پیچیدگی محاسباتی