1
Theory of Computation (ArsDigita University). Instructor: Shai Simonson.
FREE
This course includes
Hours of videos
611 years
Units & Quizzes
22
Unlimited Lifetime access
Access on mobile app
Certificate of Completion
A theoretical treatment of what can be computed and how fast it can be done. Applications to compilers, string searching, and control circuit design will be discussed. The hierarchy of finite state machines, pushdown machines, context free grammars and Turing machines will be analyzed, along with their variations. The notions of decidability, complexity theory and a complete discussion of NP-Complete problems round out the course. (from ADUni.org)
Course Currilcum
- Lecture 01 – Finite State Machines Unlimited
- Lecture 02 – Closure and Nondeterminism Unlimited
- Lecture 03 – The Pumping Lemma Unlimited
- Lecture 04 – Minimizing FSMs Unlimited
- Lecture 05 – Recitation 1 Unlimited
- Lecture 06 – Context Free Languages Unlimited
- Lecture 07 – CFLs and Compilers Unlimited
- Lecture 08 – Recitation 2 Unlimited
- Lecture 09 – Pushdown Machines Unlimited
- Lecture 10 – Recitation 3 Unlimited
- Lecture 11 – CFGs and NPDMs Unlimited
- Lecture 12 – More lemmas, CYK Unlimited
- Lecture 13 – Undecidability and CFLs Unlimited
- Lecture 14 – Recitation 4 Unlimited
- Lecture 15 – The Bullseye Unlimited
- Lecture 16 – Turing Machines Unlimited
- Lecture 17 – Recitation 5 Unlimited
- Lecture 18 – The Halting Problem Unlimited
- Lecture 19 – Decidability Unlimited
- Lecture 20 – Complexity Theory, Quantified Boolean Formula Unlimited
- Lecture 21 – Savitch’s Theorem, Space Hierarchy Unlimited
- Lecture 22 – Decidability/Complexity Relationship, Recursion Theorem Unlimited
