Theory of Computation (ArsDigita University) | Computer Science

Theory of Computation

Theory of Computation (ArsDigita University). Instructor: Shai Simonson. 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)

Lecture 01 - Finite State Machines

Lecture 02 - Closure and Nondeterminism

Lecture 03 - The Pumping Lemma

Lecture 04 - Minimizing FSMs

Lecture 05 - Recitation 1

Lecture 06 - Context Free Languages

Lecture 07 - CFLs and Compilers

Lecture 08 - Recitation 2

Lecture 09 - Pushdown Machines

Lecture 10 - Recitation 3

Lecture 11 - CFGs and NPDMs

Lecture 12 - More lemmas, CYK

Lecture 13 - Undecidability and CFLs

Lecture 14 - Recitation 4

Lecture 15 - The Bullseye

Lecture 16 - Turing Machines

Lecture 17 - Recitation 5

Lecture 18 - The Halting Problem

Lecture 19 - Decidability

Lecture 20 - Complexity Theory, Quantified Boolean Formula

Lecture 21 - Savitch's Theorem, Space Hierarchy

Lecture 22 - Decidability/Complexity Relationship, Recursion Theorem

References

Theory of Computation
Instructor: Shai Simonson. Course Description. Lecture and Courseware. Student Evaluations. A theoretical treatment of what can be computed and how fast it can be done.