David Gusfield · Computer Science
Theory of Computation
UC Davis · 22 free video lectures
Free video course from David Gusfield, taught by UC Davis. Listed under Computer Science in Open Culture's directory of free online courses.
▶ Play on Open Lecture HallCourse page ↗
Lectures
- L1: Introduction to Finite-State Machines and Regular Languages
- L2: Regular Languages and Non-Deterministic FSMs
- L4: Regular Expressions
- L5: Regular Expressions, Regular Languages and Non-Regular Languages
- L6: The Pumping Lemma and Introduction to CFLs
- L7: Contex-Free Grammars and Push-Down Automata
- L8: Introduction to Turing Machines and Computations
- L9: More TM Design and Introduction to Non-Determinstic TMs
- L10: Equivalence of Non-Deterministic and Deterministic TMs
- L11: Church-Turing Thesis and Examples of Decidable Languages
- L12: Universal Turing Machines; The Halting Problem is Recognizable but Not Decidable
- L13: Diagonalization, Countability and Uncountability
- L14: More Diagonalization; Proof that Turing Machines are Countable
- L15: Proof by Diagonalization that ATM (Halting Problem) is Not Decidable
- L16: Unrecognizable Languages and Reductions
- L17: Using Reductions to Prove Language Undecidable
- L18: More Complex Reductions
- L19: Uncomputable Functions, and Introduction to Complexity
- L20: P, NP and Polynomial-Time Reductions
- L21: NP-Completeness
- L25: Minimizing Finite State Machines
- L26: Minimizing the Number of States in a DFA
From The original publisher (listed by Open Culture). More from David Gusfield.
Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights