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.