Cours : Guillaume Hanrot
TD : Marc De Visme & Pierre Pradic
Chapters :
First computation models:
- Finite automata / regular languages : deterministic vs non deterministic, equivalence between automata / regular expressions, minisation, limits of regular languages, pumping lemma.
- Grammars : Chomski’s hierarchy, equivalence context-free / stack, limits of context-free with pumping.
Church-Turing thesis:
- Turing machines.
- Equivalence with : recursive functions, lambda-calculus.
Decidable / Undecidable:
- Undecidable, stopping problem.
- Theorems: Rice, Kleene.
An introduction to complexity theory:
- Time-complexity classes, Space-complexity classes, deterministic and non-deterministic classes.
- Elementary inclusion and separation results.
- Classes P and NP: certificate-based characterization of NP; Cook’s theorem.