MIT 18.404J Theory of Computation, Fall 2020
4.0
(2)
18 learners
What you'll learn
This course includes
- 32.3 hours of video
- Certificate of completion
- Access on mobile and TV
Course content
1 modules • 25 lessons • 32.3 hours of video
MIT 18.404J Theory of Computation, Fall 2020
25 lessons
• 32.3 hours
MIT 18.404J Theory of Computation, Fall 2020
25 lessons
• 32.3 hours
- 1. Introduction, Finite Automata, Regular Expressions 01:00:34
- 2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA 01:03:27
- 3. Regular Pumping Lemma, Conversion of FA to Regular Expressions 01:10:02
- 4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion 01:09:23
- 5. CF Pumping Lemma, Turing Machines 01:13:59
- 6. TM Variants, Church-Turing Thesis 01:14:49
- 7. Decision Problems for Automata and Grammars 01:16:51
- 8. Undecidability 01:17:02
- 9. Reducibility 01:16:37
- 10. Computation History Method 01:21:41
- 11. Recursion Theorem and Logic 01:17:32
- 12. Time Complexity 01:25:37
- 14. P and NP, SAT, Poly-Time Reducibility 01:19:23
- 15. NP-Completeness 01:25:53
- 16. Cook-Levin Theorem 01:18:27
- 17. Space Complexity, PSPACE, Savitch's Theorem 01:20:10
- 18. PSPACE-Completeness 01:17:36
- 19. Games, Generalized Geography 01:19:38
- 20. L and NL, NL = coNL 01:20:06
- 21. Hierarchy Theorems 01:21:57
- 22. Provably Intractable Problems, Oracles 01:22:50
- 23. Probabilistic Computation, BPP 01:23:41
- 24. Probabilistic Computation (cont.) 01:23:16
- 25. Interactive Proof Systems, IP 01:14:30
- 26. coNP is a subset of IP 01:23:30
Take this course with you
Download the app to continue lessons from your phone anytime.
