Home » Course Layouts » Free Course Layout Udemy
This course emphasizes computability and computational complexity theory.
0
1
English
English [CC]
FREE
- Learn basic syntax that can apply to any language.
- Learn what is a programming language and the basic concepts for beginners.
- Understand what is Javascript in it's truest form.
- Know the basic syntax of Javascript.
- Know some hidden quirks in Javascript.
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.
Course content
- Introduction, Finite Automata, Regular Expressions Unlimited
- Nondeterminism, Closure Properties, Regular Expressions → Finite Automata Unlimited
- The Regular Pumping Lemma, Finite Automata → Regular Expressions, CFGs Unlimited
- Pushdown Automata, CFG ↔ PDA Unlimited
- The CF Pumping Lemma, Turing Machines Unlimited
- TM Variants, the Church-Turing Thesis Unlimited
- Decision Problems for Automata and Grammars Unlimited
- Undecidability Unlimited
- Reducibility Unlimited
- The Computation History Method Unlimited
- The Recursion Theorem and Logic Unlimited
- Time Complexity Unlimited
- P and NP, SAT, Poly-time Reducibility Unlimited
- NP-Completeness Unlimited
- Cook-Levin Theorem Unlimited
- Space Complexity, PSPACE, Savitch’s Theorem Unlimited
- PSPACE-Completeness Unlimited
- Games, Generalized Geography Unlimited
- L and NL, NL = coNL Unlimited
- Hierarchy Theorems Unlimited
- Provably Intractable Problems, Oracles Unlimited
- Probabilistic Computation, BPP Unlimited
- Probabilistic Computation (cont.) Unlimited
- Interactive Proof Systems, IP Unlimited
- coNP ⊆ IP Unlimited
Instructor
Massachusetts Institute of Technology
5
5
1
1916
1520
