جلسه اول کلاس آنلاین نظریه زبان‌ها و ماشین‌ها - ویژه کنکور ۹۹ - رایگان
زمان برگزاری:
یکشنبه ۱۰ آذر ۱۳۹۸ ساعت ۱۸:۳۰
هزینه
کلاس:
رایگان
مدت:
۴ ساعت
فیلم این کلاس ضبط می‌شود و قابل دانلود است.
فیلم این کلاس صرفا روی یک سیستم و تحت سیستم عامل ویندوز به تعداد دفعات نامتناهی قابل پخش است.
توضیحات
در علوم نظری رایانه، نظریه اتوماتا یا ماشین‌ها به بررسی ماشینهای محاسبه‌گر انتزاعی و قدرت آن‌ها در حل مسایل پرداخته خواهد شد. در این کلاس، درس نظریه زبان‌ها و ماشین‌ها در دوره کارشناسی مهندسی کامپیوتر و درس نظریه محاسبات در دوره کارشناسی علوم کامپیوتر به صورت کامل طبق مراجع اصلی این درس با رویکرد حل مسائل تدریس خواهد شد و جهت امادگی بیشتر دانشجویان در کنکور مهندسی کامپیوتر و علوم کامپیوتر، تست‌های آزمون‌های کارشناسی ارشد این دو رشته در حین درس به جزئیات حل خواهد شد.
منابع درسی:
• کتاب مرجع، معرفی زبان‌های فرمال و آتوماتا نوشته پیتر لینز
• کتاب مرجع، نظریه محاسبات نوشته مایکل سیپسر
• کتاب مرجع، معرفی زبان ها و نظریه محاسبات نوشته مارتین
• کتاب مرجع، معرفی نظریه آتوماتا، زبان‌ها و محاسبات نوشته هاپکرافت، موتوانی و اولمان
سرفصل نظریه زبان‌ها و ماشین‌ها به ترتیب زیر است:
• فصل اول: مقدمه‌ای بر نظریه محاسبات، مباحث پیشنیاز و مفاهیم اولیه
نظریه‌ی مجموعه‌ها، اصول منطق، روش‌های اثبات، رابطه و تابع، مجموعه‌های شمارا و ناشمارا، مفاهیم پایه گراف و درخت، روابط بازگشتی، نمادهای مجانبی، الفبا، رشته، زبان، عملیات روی رشته‌ها و زبان‌ها، مدل بازگشتی، مختصری بر گرامرها، آتوماتا
• فصل دوم: ماشینهای حالت متناهی
ماشین پذیرنده متناهی قطعی، ماشین پذیرنده متناهی غیرقطعی، تبدیل بین DFA وNFA ، ماشین DFA کمینه، ماشین مترجم متناهی
• فصل سوم: زبان‌های منظم
عبارت‌های منظم، گرامرهای منظم، زبان‌های منظم و ارتباط بین این مدل‌ها
• فصل چهارم: ویژگی‌های زبان‌های منظم
خصوصیات بستاری زبان‌های منظم، تصمیم پذیری و خواص الگوریتمیک زبان‌های منظم، زبان‌های نامنظم، لم تزریق زبان‌های منظم، قضیه Myhill–Nerode، دیگر روش‌های تشخیص یک زبان منظم و خانواده‌های زبان‌های زیرمجموعه زبان‌های منظم
• فصل پنجم: زبان‌های مستقل از متن
گرامرهای مستقل از متن، زبان‌های مستقل از متن، اشتقاق، اشتقاق چپ‌گرد و راست‌گرد، پارس یا تجزیه، مسئله عضویت، ابهام در گرامرهای مستقل از متن و زبان‌ها
• فصل ششم: ساده‌سازی گرامرهای مستقل از متن
تبدیلات روی گرامرهای مستقل از متن، فرم‌های نرمال چامسکی و گریباخ، الگوریتم عضویت CYK
• فصل هفتم: ماشینهای پشته‌ای PDA
ماشین پشته‌ای غیرقطعی، ارتباط بین زبان‌های مستقل از متن و ماشینهای پشته‌ای، ماشین پشته‌ای قطعی و گرامرهای معادل آن‌ها
• فصل هشتم: ویژگی‌های زبان‌های مستقل از متن
خصوصیات بستاری زبان‌های مستقل از متن، تصمیم پذیری و خواص الگوریتمیک در زبان‌های مستقل از متن، لم تزریق زبان‌های مستقل از متن قطعی و خطی و روش‌های تشخیص یک زبان مستقل از متن
• فصل نهم: ماشینهای تورینگ
ماشین تورینگ استاندارد، ماشین تورینگ پذیرنده و محاسبه‌گر، ترکیب ماشینهای تورینگ، تز تورینگ
• فصل دهم: انواع مدل‌های ماشین تورینگ
نسخه‌های مختلف از ماشین تورینگ، تورینگ قطعی و غیرقطعی، تورینگ Universal، ماشین کراندار خطی
• فصل یازدهم: دسته‌بندی زبان‌های صوری و آتوماتا
زبان‌های بازگشتیREC و بازگشتی شمارش‌پذیر RE، مسئله توقف، گرامرهای بدون محدودیت و گرامرهای حساس به متن و زبان‌های مرتبط، سلسله مراتب چامسکی، خصوصیات بستاری، تصمیم پذیری و خواص الگوریتمیک زبان‌های REC وRE و CS،
• فصل دوازدهم: محاسبه‌پذیری
محاسبه پذیری و محاسبه ناپذیری، کاهش‌پذیری، قضیه رایس، کلاس‌های پیچیدگی محاسباتی
