0
(
ratings
)
2
students
Created by:
Last updated:
September 21, 2023
Duration:
Unlimited Duration
FREE
This course includes:
Unlimited Duration
Badge on Completion
Certificate of completion
Unlimited Duration
Description
18.404J/6.840J The Theory of Computation(Fall 2020, MIT OCW). Instructor: Prof. Michael Sipser. This course emphasizes computability and computational complexity theory.
Topics include regular and context-free languages, decidable and undecidable problems, reducibility, recursive function theory, time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems. (from ocw.mit.edu)
Course Curriculum
- Lecture 01 – Introduction: Finite Automata, Regular Expressions Unlimited
- Lecture 02 – Nondeterminism, Closure Properties, Regular Expressions to Finite Automata Unlimited
- Lecture 03 – Regular Pumping Lemma, Finite Automata to Regular Expressions Unlimited
- Lecture 04 – Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion Unlimited
- Lecture 05 – CF Pumping Lemma, Turing Machines Unlimited
- Lecture 06 – TM Variants, Church-Turing Thesis Unlimited
- Lecture 07 – Decision Problems for Automata and Grammars Unlimited
- Lecture 08 – Undecidability Unlimited
- Lecture 09 – Reducibility Unlimited
- Lecture 10 – Computation History Method Unlimited
- Lecture 11 – Recursion Theorem and Logic Unlimited
- Lecture 12 – Time Complexity Unlimited
- Lecture 14 – P and NP, SAT, Poly-Time Reducibility Unlimited
- Lecture 15 – NP-Completeness Unlimited
- Lecture 16 – Cook-Levin Theorem Unlimited
- Lecture 17 – Space Complexity, PSPACE, Savitch’s Theorem Unlimited
- Lecture 18 – PSPACE-Completeness Unlimited
- Lecture 19 – Games, Generalized Geography Unlimited
- Lecture 20 – L and NL, NL = coNL Unlimited
- Lecture 21 – Hierarchy Theorems Unlimited
- Lecture 22 – Provably Intractable Problems, Oracles Unlimited
- Lecture 23 – Probabilistic Computation, BPP Unlimited
- Lecture 24 – Probabilistic Computation (cont.) Unlimited
- Lecture 25 – Interactive Proof Systems, IP Unlimited
- Lecture 26 – coNP is a subset of IP Unlimited
About the instructor
5
5
Instructor Rating
6
Reviews
4637
Courses
24154
Students
OpenCoursa
We are an educational and skills marketplace to accommodate the needs of skills enhancement and free equal education across the globe to the millions. We are bringing courses and trainings every single day for our users. We welcome everyone woth all ages, all background to learn. There is so much available to learn and deliver to the people.
