Cours d’introduction à l’informatique théorique pour des étudiants de master, il couvre aussi une grande partie du programme de l’option informatique de l’agrégation de mathématiques.

Voici le plan :
1) Les langages rationnels : premières définitions, opérations rationnelles, combinatoire des mots, ordres sur les mots et les arbres, automates, opérations booléennes, étoiles.
2) Les langages algébriques : grammaires algébriques, systèmes d’équations, arbres de dérivation, propriétés de clôture, automates à pile.
3) La calculabilité : notions de problème et de codage, machines de Turing, langages récursivement énumérables, langages décidables, problème de correspondance de Post, théorème de récursion, machines linéairement bornées, décidabilité de théories logiques, fonctions récursives.
4) La complexité : complexités en temps, en espace, théorèmes de hiérarchie, machines alternantes.