Home » Course Layouts » Free Course Layout Udemy
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
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. (from ocw.mit.edu)
Course content
- 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
Instructor
OpenCoursa
Accessible Education for Everyone
5
5
6
24195
4637
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.
