| Topics | Lecture Download |
| Introduction and Overview | |
| Generalized Computers, Strings, Languages. Finite Automata (FA's) | |
| Regular Languages and Regular Operations; emacs regular expressions | |
| Closure of Regular Languages Under Boolean Operations. | |
| Nondeterminstics FA's (NFA's). Regular Expressions (REG); FA = NFA = REG | |
| Minimization. Pumping Lemma | |
| Context Free Languages: Derivations, Parse-Trees, Ambiguity | |
| Pushdown Stack Automata (PDA's) | |
| Grammar and Machine Transformations | |
| Context Free Pumping Lemma | |
| Turing Machines: Motivation, Definitions, Recognizers vs. Deciders | |
| Turing Machine Variants: 3 levels of TM abstraction, Non-deterministic recognizers and deciders, König's infinity lemma, Multitape TM's | |
| Universal Models of Computation: TM = k-track TM = k-tape TM = NTM, FIFO Queue Machines | |
| Viewing algorithms as languages, Algorithmic Decision Problems: ATM, ACFG , A REX,ETM, etc. | |
| Incomputable Languages: Existence of Incomputable Languages; Cantor's Diagonalization Argument; Undecidability of ATM, E TM, EQTM; ALLTM | |
| More Undecidable Problems: Reducibility: Turing reducible, Mapping reducible, Co-mapping reducible; Beyond undecidable; General grammars; Semi-Thue systems (STP); Post's correspondence problem (PCP); Problems involving CFG's | |
| Complexity: Running time, Big-O review, the class PP and CYK algorithm | |
| The Class NP: Nondeterministic complexity: poly-time NTM's, poly-time Verifiers, poly-size proofs; Punch-Card Puzzle, SAT and variants, The class Co-NP; Polynomial time reductions | |
| NP-complete problems; P vs. NP Open Problem: Known and unknown hierarchies; Nondeterministic complexity | |
| The Cook-Levin Theorem: Showing that CSAT is NP-hard, Reducing CSAT to 3SAT | |
| Review |
Computability Lecture Notes
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment