YoVDO

Theory of Computation, Fall 2020

Offered By: Massachusetts Institute of Technology via YouTube

Tags

Computer Science Courses Regular Expressions Courses Finite Automata Courses Turing Machines Courses Computability Courses Computational Complexity Theory Courses Time Complexity Courses

Course Description

Overview

Dive into the world of theoretical computer science with this comprehensive lecture series on the Theory of Computation, taught by Professor Michael Sipser at MIT. Explore fundamental concepts such as finite automata, regular expressions, pushdown automata, Turing machines, and computational complexity theory. Learn about key theorems like Cook-Levin, Savitch's, and Immerman-Szelepcsenyi, while developing a deep understanding of computability and complexity. Progress through 26 lectures covering topics from basic automata to advanced concepts like interactive proof systems, probabilistic computation, and NP-completeness. Gain insights into decision problems, undecidability, reducibility, and space complexity. Engage with this rigorous course to build a strong foundation in theoretical computer science and its applications.

Syllabus

1. Introduction, Finite Automata, Regular Expressions.
2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA.
3. Regular Pumping Lemma, Conversion of FA to Regular Expressions.
4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion.
5. CF Pumping Lemma, Turing Machines.
6. TM Variants, Church-Turing Thesis.
7. Decision Problems for Automata and Grammars.
8. Undecidability.
9. Reducibility.
10. Computation History Method.
11. Recursion Theorem and Logic.
12. Time Complexity.
14. P and NP, SAT, Poly-Time Reducibility.
15. NP-Completeness.
16. Cook-Levin Theorem.
17. Space Complexity, PSPACE, Savitch's Theorem.
18. PSPACE-Completeness.
19. Games, Generalized Geography.
20. L and NL, NL = coNL.
21. Hierarchy Theorems.
22. Provably Intractable Problems, Oracles.
23. Probabilistic Computation, BPP.
24. Probabilistic Computation (cont.).
25. Interactive Proof Systems, IP.
26. coNP is a subset of IP.


Taught by

MIT open courseware

Tags

Related Courses

Introduction to Computer Science and Programming
Tokyo Institute of Technology via edX
Paradox and Infinity
Massachusetts Institute of Technology via edX
Mathematical Logic and Algorithms Theory
Tomsk State University of Control Systems and Radioelectronics via iversity
Preparing for Further Study in Mathematics
Manchester Grammar School via FutureLearn
Basics of Computational Complexity
Indian Institute of Technology Kanpur via Swayam