Theory of Computation - Fall 2011
By Dan Gusfield
To listen to an audio podcast, mouse over the title and click Play. Open iTunes to download and subscribe to podcasts.
Description
This is a rigorous undergraduate course on the Theory of Computation, using the classic text "Introduction to the Theory of Computation" by Michael Sipser. The course covers machine models and languages defined by Finite State Machines, Context-Free Languages, and Turing Machines. There are four major theorems (and their uses) that we will study during this course, providing complete proofs: the pumping Lemma for regular languages, used to show that there are languages that are not regular; the existence of a Universal Turing Machine; undecidability of the Halting problem; and Cook's theorem that NP-complete problems exist. In addition to these major results, and other results, a central goal of the course is to increase student's skill level in understanding and writing rigorous mathematical proofs.
| Name | Description | Released | Price | ||
|---|---|---|---|---|---|
| 1 | VideoSecond Lecture on Godel's Incompleteness Theorem | Second Lecture on Godel's Incompleteness Theorem | 5/2/2014 | Free | View in iTunes |
| 2 | VideoGodel for Goldilocks: Godel's First Incompleteness Theorem | Godel for Goldilocks: Godel's First Incompleteness Theorem | 5/1/2014 | Free | View in iTunes |
| 3 | VideoL26: Minimizing the number of states in a DFA | L26: Minimizing the number of states in a DFA | 2/10/2012 | Free | View in iTunes |
| 4 | VideoL25: Minimizing Finite State Machines | L25: Minimizing Finite State Machines | 1/27/2012 | Free | View in iTunes |
| 5 | VideoL24: NP Completeness, Supplemental lecture 3 | L24: NP Completeness, Supplemental lecture 3 | 12/13/2011 | Free | View in iTunes |
| 6 | VideoL23: NP Completeness, Supplemental lecture 2 | L23: NP Completeness, Supplemental lecture 2 | 12/9/2011 | Free | View in iTunes |
| 7 | VideoL22: A more informal introduction to NP-completeness, Supplemental Lecture 1 | L22: A more informal introduction to NP-completeness, Supplemental Lecture 1 | 12/3/2011 | Free | View in iTunes |
| 8 | VideoL21: NP-completeness | L21: NP-completeness | 12/1/2011 | Free | View in iTunes |
| 9 | VideoL20: P, NP and polynomial-time reductions | L20: P, NP and polynomial-time reductions | 11/29/2011 | Free | View in iTunes |
| 10 | VideoL19: Uncomputable functions, and introduction to complexity | L19: Uncomputable functions, and introduction to complexity | 11/22/2011 | Free | View in iTunes |
| 11 | VideoL18: More complex reductions | L18: More complex reductions | 11/17/2011 | Free | View in iTunes |
| 12 | VideoL17: Using reductions to prove language undecidable | L17: Using reductions to prove language undecidable | 11/15/2011 | Free | View in iTunes |
| 13 | VideoL16: Unrecognizable languages, and reductions | L16: Unrecognizable languages, and reductions | 11/12/2011 | Free | View in iTunes |
| 14 | VideoL15: Proof by diagonalization that ATM (Halting problem) is not decidable | L15: Proof by diagonalization that ATM (Halting problem) is not decidable | 11/11/2011 | Free | View in iTunes |
| 15 | VideoL14: More Diagonalization; Proof that Turing machines are countable | L14: More Diagonalization; Proof that Turing machines are countable | 11/10/2011 | Free | View in iTunes |
| 16 | VideoL13: Diagonalization, countability and uncountability | L13: Diagonalization, countability and uncountability | 11/8/2011 | Free | View in iTunes |
| 17 | VideoL12: Universal Turing Machines; The Halting Problem is Recognizable but not Decidable | L12: Universal Turing Machines; The Halting Problem is Recognizable but not Decidable | 11/3/2011 | Free | View in iTunes |
| 18 | VideoL11: Church-Turing thesis and examples of decidable languages | L11: Church-Turing thesis and examples of decidable languages | 11/1/2011 | Free | View in iTunes |
| 19 | VideoL10: Equivalence of non-deterministic and deterministic TMs | L10: Equivalence of non-deterministic and deterministic TMs | 10/25/2011 | Free | View in iTunes |
| 20 | VideoL9: More TM design and introduction to non-determinstic TMs | L9: More TM design and introduction to non-determinstic TMs | 10/20/2011 | Free | View in iTunes |
| 21 | VideoL8: Introduction to Turing Machines and Computations | L8: Introduction to Turing Machines and Computations | 10/18/2011 | Free | View in iTunes |
| 22 | VideoL7: Contex-Free Grammars and Push-Down Automata | L7: Contex-Free Grammars and Push-Down Automata | 10/13/2011 | Free | View in iTunes |
| 23 | VideoL6: The Pumping Lemma, and introduction to CFLs | L6: The Pumping Lemma, and introduction to CFLs | 10/11/2011 | Free | View in iTunes |
| 24 | VideoL5: Regular expressions, regular languages, and non-regular languages | L5: Regular expressions, regular languages, and non-regular languages | 10/6/2011 | Free | View in iTunes |
| 25 | VideoL4: Regular Expressions | L4: Regular Expressions | 10/4/2011 | Free | View in iTunes |
| 26 | VideoL2: Regular Languages and non-deterministic FSMs | L2: Regular Languages and non-deterministic FSMs | 9/27/2011 | Free | View in iTunes |
| 27 | VideoL1: Introduction to Finite-state Machines, Regular Languages | L1: Introduction to Finite-state Machines, Regular Languages | 9/22/2011 | Free | View in iTunes |
| 27 Items |
- Free
- Category: Technology
- Language: English
- © Copyright The Regents of the University of California, Davis campus, 2015. All Rights Reserved.