آموزش اتومات و محاسب‌پذیری - آخرین آپدیت

مقدمه‌ای بر نظریه اتوماتا Introduction to Automata Theory

• آشنایی با مدرس شما: پروفسور سایکیشور جانگیتی Meet Your Instructor - Prof. Saikishor Jangiti

• آشنایی با مدرس شما: پروفسور اس. پی ویمال Meet Your Instructor - Prof. S.P Vimal

• ویدیو معرفی دوره Course Introductory Video

• انواع مختلف اتوماتا Different Kinds of Automata

• مجموعه‌ها Sets

• توابع و روابط Functions and Relations

• گراف‌ها و درخت‌ها Graphs and Trees

• تکنیک‌های اثبات Proof Techniques

• زبان و رشته‌ها Language and Strings

• عملیات روی زبان Operations on a Language

• اتومات‌های متناهی Finite Automata

• پذیرنده متناهی قطعی (DFA) Deterministic Finite Accepter (DFA)

• DFA و زبان‌های منظم DFA and Regular Languages

اتومات‌های متناهی Finite Automata

• ناقطعی بودن (Non-Determinism) Non-Determinism

• انتقالات لامبدا Lambda Transitions

• تعریف Definition

• رد رشته ورودی توسط NFA Input String Rejection by an NFA

• پذیرش رشته ورودی توسط NFA Input String Acceptance by an NFA

• زبان پذیرفته شده توسط NFA Language Accepted by an NFA

• پذیرش زبان نامتناهی از طریق انتقالات لامبدا Infinite Language Acceptance Through Lambda Transitions

• حالت نهایی واحد برای NFAها Single Final State for NFAs

• هر DFA به صورت بدیهی یک NFA است Every DFA is Trivially an NFA

• قابلیت تبدیل NFA به DFA معادل NFA can be Converted to an Equivalent DFA

• اثبات هم‌ارزی Equivalence Proof

زبان‌های منظم Regular Languages

• نمایش‌های استاندارد یک زبان منظم Standard Representations of a Regular Language

• اجتماع دو زبان منظم Union of Two Regular Languages

• الحاق دو زبان منظم Concatenation of Two Regular Languages

• بسته بودن تحت عملگر ستاره Closure Under Star Operation

• معکوس یک زبان منظم Reverse of a Regular Language

• سوالات مقدماتی درباره زبان‌های منظم Elementary Questions About Regular Languages

• دستور زبان (Grammar) Grammar

• تعریف دستور زبان‌ها Definition of Grammars

• دستور زبان خطی و غیرخطی Linear Grammar and Non-Linear Grammar

• دستور زبان منظم Regular Grammar

• هر دستور زبان منظم یک زبان منظم تولید می‌کند Any Regular Grammar Generates a Regular Language

• هر زبان منظم توسط یک دستور زبان منظم تولید می‌شود Every Regular Language is Generated by Some Regular Grammar

• اصل لانه کبوتری Pigeonhole Principle

• اصل لانه کبوتری و DFAها The Pigeonhole Principle and DFAs

• لم پامپینگ (Pumping Lemma) The Pumping Lemma

• کاربردهای لم پامپینگ Applications of Pumping Lemma

• لم پامپینگ و پالیندروم The Pumping Lemma - Palindrome

• کاربرد دیگر لم پامپینگ Another Application of Pumping Lemma

• رشته‌هایی با طول فاکتوریل Factorial Length Strings

زبان‌های مستقل از متن Context Free Languages

• مقدمه‌ای بر CFL Introduction to CFL

• تعریف CFG Definition for CFG

• مثالی از CFG CFG Example

• درخت‌های اشتقاق Derivation Trees

• ابهام (Ambiguity) Ambiguity

• ابهام ذاتی Inherent Ambiguity

• تعریف NPDA NPDA Definition

• مروری بر PDA PDA Overview

• مثالی از NPDA (۱) NPDA Example - 1

• NPDA برای رشته‌های پالیندروم NPDA for Palindrome Strings

• رد رشته توسط NPDA NPDA Rejection

• مثالی از NPDA (۲) NPDA Example - 2

• فشار رشته در NPDA Push String in NPDA

• پذیرش رشته‌های با تعداد مساوی A و B توسط NPDA NPDA Accepting Strings with Equal Number of A’s and B’s

• پذیرش زبان‌های مستقل از متن توسط NPDAها NPDAs Accept Context-Free Languages

• تبدیل دستور زبان‌های مستقل از متن به NPDA Converting Context-Free Grammars to NPDAs

• تبدیل NPDA به دستور زبان‌های مستقل از متن Converting NPDAs to Context-Free Grammars

• تعریف Definition

• مثالی از DPDA DPDA Example

• مقایسه NPDA و DPDA NPDA vs DPDA

ساده‌سازی، فرم‌های نرمال و ویژگی‌های CFL Simplification, Normal Forms and Properties of CFL

• دستور زبان S S-Grammar

• ساده‌سازی دستور زبان‌های مستقل از متن Simplification of Context Free Grammars

• ویژگی‌های تصمیم‌پذیر CFL Decidable Properties of CFL

• ویژگی‌های مثبت Positive Properties

• ویژگی‌های منفی Negative Properties

• اشتراک زبان‌های مستقل از متن و زبان‌های منظم Intersection of Context-Free Languages and Regular Languages

• کاربردهای بستگی منظم Applications of Regular Closure

• مقدمه‌ای بر لم پامپینگ برای CFL Introduction to Pumping Lemma for CFL

• لم پامپینگ برای CFL The Pumping Lemma for CFL

• کاربرد لم پامپینگ برای CFL Application of the Pumping Lemma for CFL

• زبان WW مستقل از متن نیست The Language WW is not Context Free

• فرم نرمال چامسکی Chomsky Normal Form

• الگوریتم عضویت CYK CYK Membership Algorithm

• فرم نرمال گرایبک Greibach Normal Form

• سلسله‌مراتب چامسکی Chomsky Hierarchy

مقدمه‌ای بر ماشین تورینگ Introduction to Turing Machine

• طرح کلی ماژول Outline of the Module

• تعریف ماشین تورینگ Definition of a Turing Machine

• یک TM ساده A Simple TM

• گراف‌های انتقال برای نمایش TM Transition Graphs to Represent TM

• توصیف لحظه‌ای Instantaneous Description

• حلقه‌های بی‌نهایت Infinite Loops

• تعریف زبان پذیرفته شده توسط TM Definition of Language Accepted by TM

• ماشین تورینگی که زبان {0^n 1^n : n >= 1} را می‌پذیرد TM that Accepts L = {0ⁿ1ⁿ: n ≥ 1}

• محاسبه 0011 برای زبان {0^n 1^n : n >= 1} L = {0ⁿ1ⁿ : n ≥ 1} - Computation of 0011

• ماشین تورینگی که زبان {0^n 1^n 2^n : n >= 1} را می‌پذیرد TM that Accepts L = {0ⁿ 1ⁿ 2ⁿ : n ≥ 1}

• تابع محاسب‌پذیر تورینگ Turing Computable Function

• جمع Addition

• ماشین تورینگ برای کپی کردن یک رشته Turing Machine for Copying a String

• ماشین تورینگ برای مقایسه Turing Machine for Comparison

• چگونه یک ماشین تورینگ برای یک کار ساده طراحی کنیم؟ How to Design a Turing Machine for a Simple Task?

• طراحی یک ماشین تورینگ Design a Turing Machine

• خلاصه ماژول Summary of the Module

انواع ماشین تورینگ Variations of Turing Machine

• طرح کلی ماژول Outline of the Module

• مثالی از طراحی ماشین تورینگ Turing Machine Design Example

• دستورالعمل ماکرو در ماشین تورینگ Macro-Instruction in Turing Machine

• زیربرنامه در ماشین تورینگ Subprogram in Turing Machine

• تز تورینگ Turing’s Thesis

• هم‌ارزی کلاس‌های اتوماتا Equivalence of Classes of Automata

• ماشین‌های تورینگ با گزینه توقف (Stay) Turing Machines with Stay-Option

• مثالی از ماشین‌های تورینگ با گزینه توقف Turing Machines with Stay-Option Example

• ماشین‌های تورینگ با نوار نیمه‌بی‌نهایت Turing Machines with Semi-Infinite Tape

• ماشین‌های تورینگ چند نوار Multitape Turing Machines

• مثالی از ماشین تورینگ چند نوار Multitape Turing Machine Example

• ماشین تورینگ آفلاین Offline Turing Machine

• ماشین تورینگ چند بعدی Multi-Dimensional Turing Machine

• ماشین تورینگ غیرقطعی Non-Deterministic Turing Machine

• ماشین‌های تورینگ جهانی (Universal) Universal Turing Machines

• توابع محاسب‌پذیر تورینگ Turing-Computable Functions

• خلاصه ماژول Summary of the Module

سلسله‌مراتب زبان‌های صوری و اتوماتا Hierarchy of Formal Languages and Automata

• طرح کلی ماژول Outline of the Module

• زبان‌های بازگشتی Recursive Languages

• مثال‌هایی از زبان‌های بازگشتی Recursive Languages Examples

• زبان‌های شمارش‌پذیر بازگشتی Recursively Enumerable Language

• مثال‌هایی از زبان‌های شمارش‌پذیر بازگشتی Recursively Enumerable Language Examples

• زبان‌های غیرشمارش‌پذیر بازگشتی Non-Recursively Enumerable Language

• مثال‌هایی از زبان‌های غیرشمارش‌پذیر بازگشتی Non-Recursively Enumerable Language Examples

• زبان‌هایی که شمارش‌پذیر بازگشتی هستند اما بازگشتی نیستند Languages that is Recursively Enumerable but not Recursive

• دستور زبان‌های بدون محدودیت Unrestricted Grammars

• یک مثال از دستور زبان‌های بدون محدودیت Unrestricted Grammars - An Example

• دستور زبان‌های بدون محدودیت و زبان‌های RE Unrestricted Grammars & RE Languages

• دستور زبان‌های حساس به متن Context Sensitive Grammars

• زبان‌های حساس به متن Context Sensitive Languages

• سلسله‌مراتب چامسکی Chomsky Hierarchy

• خلاصه ماژول Summary of the Module

محاسب‌پذیری و تصمیم‌پذیری Computability and Decidability

• تصمیم‌پذیری Decidability

• مسئله عضویت Membership Problem

• مسئله توقف (Halting Problem) Halting Problem

• کاهش‌پذیری و مسئله توقف Reducibility and the Halting Problem

• مسئله توقف نوار خالی Blank Tape Halting Problem

• ویژگی‌های تصمیم‌پذیری زبان‌های شمارش‌پذیر بازگشتی Decidability Properties of Recursively Enumerable Languages

• مسئله تطابق پست (Post Correspondence Problem) The Post Correspondence Problem

• مسئله تطابق پست تغییریافته Modified Post Correspondence Problem

• تصمیم‌پذیری مسئله PC Decidability of PC Problem

• توابع غیرمحاسب‌پذیر Uncomputable Functions

• قضیه رایس Rice’s Theorem

مروری بر پیچیدگی محاسباتی Overview of Computational Complexity

• کارایی محاسبات Efficiency of Computation

• پیچیدگی زمانی چندجمله‌ای Polynomial Time Complexity

• کلاس P The Class P

• پیچیدگی زمانی نمایی Exponential Time Complexity

• مسئله ارضای‌پذیری (Satisfiability) Satisfiability Problem

• زمان چندجمله‌ای غیرقطعی Non-Deterministic Polynomial Time

• آیا P = NP است؟ Is P = NP?

• مسائل NP-Complete NP-Complete Problems