Bulletin Vert n°491
novembre — décembre 2010

Langages formels calculabilité et complexité

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.

 

Les Journées Nationales
L’APMEP

Publications
Ressources

Actualités et Informations
Base de ressources bibliographiques

 

Les Régionales de l’APMEP