18.404J/6.840J The Theory of Computation(Fall 2020, MIT OCW). Instructor: Prof. Michael Sipser. This course emphasizes computability and computational complexity theory.
0
2
September 21, 2023
English
English [CC]
Description
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
24183
Students
OpenCoursa
Accessible Education for Everyone
OpenCoursa is a free online learning platform dedicated to providing high-quality education to learners worldwide. With courses across a wide range of subjects, we empower individuals to gain new skills and knowledge at no cost. Our mission is to make education accessible to everyone, offering flexible learning opportunities for personal and professional growth.
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.
FREE
Hours of videos
694 years, 4 months
Units & Quizzes
Unlimited Lifetime access
Access on mobile app
Certificate of Completion
- For teams of 2 or more users
- 27,000+ fresh & in-demand courses
- Learning Engagement tools
- SSO and LMS Integrations
