CIS 511, 2010

Some Course Notes and Slides

Notes

• Discrete math. basics, induction, inductive definitions
  (Chapter from ``Logic for Computer Science'', by J. Gallier)   (ps)   |  (pdf)
• Discrete mathematics. Some Notes
  (Book in progress, by J. Gallier)   (html)  
• Notes on the closure definition of the regular languages (notes)   (pdf)
• The Myhill-Nerode Theorem. State Equivalence, and minimization of DFA's (notes)   (pdf)
• Context-free grammars, context-free languages, parse trees, and Ogden's Lemma (notes)   (pdf)
• A survey of LR-parsing methods. The graph methods for computing
  FIRST, FOLLOW, and LALR(1) Lookahead sets (notes)   (pdf)
• Computability, Undecidability, and Basic Recursive Function Theory (notes) (pdf)
• Chapter 5 of " Discrete Mathematics. Some Notes".
  Especially Sections 5.1, 5.3, 5.4, 5.9, 5.10, 5.11 and 5.12
  Notes on Public Key Cryptography and RSA   (pdf)
• Book Manuscript, by Gallier and Hicks (pdf)
• Definitions of terms such as "Theorem, Lemma, Proposition, etc.",
  from Legendre's "Elements de Geometrie" (first publication, 1794)   (pdf)  
• Preface by Martin Davis of "Hilbert's Tenth Problem",
  by Yuri Matiyasevich   (pdf)
• Theory of Computation in German! (slides)

Slides

• Generalities, Motivations, Basics of language theory, DFA's, the cross-product construction,
  morphisms and maps of DFA's, NFA's, the subset construction   (pdf)
• Transducers, labeled directed graphs, regular expressions (slides)   (pdf)
• The Myhill-Nerode Theorem. State Equivalence, and minimization of DFA's (slides)   (pdf)
• Context-free grammars and context-free languages (slides)   (pdf)
• BNF convbnf
• BNF metabnf
• BNF pasbnf
• BNF toybnf
• Context-free languages as fixed points, Greibach normal form (slides)   (pdf)
• Parse Trees, and Ogden's Lemma (slides)   (pdf)
• Pushdown Automata and context-free languages (slides)   (pdf)
• LR-parsing and shift/reduce algorithm (slides)   (pdf)
• RAM programs (Post machines), Turing Machines, Primitive recursive functions, partial recursive functions (slides, pdf)
• Coding of RAM programs, Unsolvability of the Halting Problem, A universal RAM program,
  The Enumeration Theorem, Kleene's T-predicate, Kleene Normal Form Theorem (slides, pdf)
• Elementary Recursive Function Theory, Acceptable indexings, the s-m-n Theorem, Undecidable Problems,
  K and TOTAL are not recursive, Rice's Theorem (slides, pdf)
• Recursively Enumerable Sets, Many-One Reducibility, Complete Sets, TOTAL, FINITE, and their complements, are not r.e. (slides, pdf)
• The Recursion Theorem, the Extended Rice Theorem, Productive and Creative Sets (slides, pdf)
• The Post Correspondence Problem (PCP), Undecidable properties of languages, Greibach's theorem (slides, pdf)
• Computational Complexity, the class P, satisfiability, the class NP, NP-completeness, Cook's theorem (slides, pdf)
• Eulerian and Hamiltonian cycles (slides, pdf)
• Prove that P = NP, and get a one million dollar reward! (Clay Institute)
• Notes on Public Key Cryptography and RSA (slides)   (pdf)
• What is a proof? (Talk given on November 6, 2008)
  slides (pdf)   slides (keynote)
• A Turing Machine in the classic style (html)

Slides, Printed Version

• RAM programs (Post machines), Turing Machines (printed slides, pdf)
• Primitive recursive functions, partial recursive functions (printed slides, pdf)
• Coding of RAM programs, Unsolvability of the Halting Problem, A universal RAM program,
  The Enumeration Theorem, Kleene's T-predicate, Kleene Normal Form Theorem (printed slides, pdf)
• Elementary Recursive Function Theory, Acceptable indexings, the s-m-n Theorem, Undecidable Problems,
  K and TOTAL are not recursive, Rice's Theorem (printed slides, pdf)
• Recursively Enumerable Sets, Many-One Reducibility, Complete Sets, TOTAL, FINITE, and their complements, are not r.e. (printed slides, pdf)
• The Recursion Theorem, the Extended Rice Theorem, Productive and Creative Sets (printed slides, pdf)
• The Post Correspondence Problem (PCP), Undecidable properties of languages, Greibach's theorem (printed slides, pdf)
• Computational Complexity, the class P, satisfiability, the class NP, NP-completeness, Cook's theorem (printed slides, pdf)
• Phrase structure grammars, context-sensitive grammars (printed slides, pdf)

Back to Gallier Homepage

published by:

Jean Gallier