par Olivier Carton

Vuibert, octobre 2008
238 p. en 16,5 × 24, ISBN : 978-2-7117-2077-4

Cet ouvrage correspond à un 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.

Solidement structuré en chapitres, paragraphes et sous-paragraphes, il donne les définitions, puis les démonstrations des lemmes, propositions et théorèmes en les agrémentant, au fil du texte, de nombreux exemples et exercices corrigés.

Divisé en deux parties, Langages formels et Calculabilité et complexité, il aborde successivement :

• 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.

La bibliographie se limite à l’essentiel pour non spécialistes, l’index renvoie aux définitions, aux énoncés et aux concepts rencontrés.

Ce livre comble une lacune : alors que de nombreux livres en anglais couvrent ces sujets, il n’y avait jusqu’à maintenant que quelques références en français.

Il intéressera tous ceux qui souhaitent faire à l’informatique au lycée la place qui lui revient désormais.