Sign up to save your podcasts
Or
Share Theory of Computation - Fall 2011
Share to email
Share to Facebook
Share to X
Share to email
Share to Facebook
Share to X
Or
Theory of Computation - Fall 2011
By Dan Gusfield
Theory of Computation - Fall 2011 episodes
- Second Lecture on Godel's Incompleteness TheoremCompletion of the lecture on Godel's first incompleteness theorem.16 min
- Godel for Goldilocks: Godel's First Incompleteness TheoremGodel's first incompleteness theorem, requiring minimal background. You only need to know what an integer is, what a function is and that a computer program is a finite series of statements written in some finite alphabet.1 hr 11 min
- L26: Minimizing the number of states in a DFACompletion of the method to minimize the number of states in a DFA for any regular language. A by-product is a proof that the minimizing DFA is unique for any given regular language.1 hr 26 min
- L25: Minimizing Finite State MachinesIn this supplemental lecture we define what is meant by a minimized DFA, and introduce an efficient algorithm to minimize the number of states in a DFA for any regular language.1 hr 14 min
- L24: NP Completeness, Supplemental lecture 3Supplemental lecture 3 on less formal treatment of NP-completeness.51 min
- L23: NP Completeness, Supplemental lecture 2A second supplemental lecture on a more informal treatment of NP-completeness.46 min
- L22: A more informal introduction to NP-completeness, Supplemental Lecture 1This is a supplemental lecture Introducing the concept of NP through reductions. It was given in another course, but since the treatment of NP completeness was so compressed in Fall 2011, I think this lecture, and two more, will be quite valuable.49 min
- L21: NP-completenessFormal definition of NP-completeness and polynomial-time reductions to prove additional languages are NP-complete once one NP-complete language has been established.1 hr 13 min
- 33 min
- L19: Uncomputable functions, and introduction to complexityProof by diagonalization that there are uncomputable functions; introduction to complexity theory, big-Oh notation, definition of worst-case for a non-deterministic. Turing machine; definition of the classes P and NP.1 hr 22 min
About Theory of Computation - Fall 2011
From the publisher's feed
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.