Cet ouvrage, qui reprend un enseignement dispensé aux élèves ingénieurs de l’INSA de Lyon, se compose de trois parties.
La première est consacrée aux fondements de logique et de théorie des ensembles. Les relations binaires et leurs diverses propriétés sont précisées et illustrées d’exemples. Cette partie aborde également les notions de calculabilité et de complexité.
Les machines de Turing sont présentées de façon claire, ainsi que les thèses de Church sur lesquelles repose la théorie de l’informatique. Les notions de calculabilité, de récursivité, etc. sont présentées de manière abordable et, là encore, illustrées par des exemples. Enfin l’essentiel de la complexité est abordé sous un angle pratique.
La deuxième partie, plus classique, est consacrée à la théorie des graphes. Les définitions sont précises, les exemples nombreux, sans que l’on soit noyé sous les algorithmes de résolution.
La dernière partie de l’ouvrage, plus théorique, reprend et développe les notions d’algèbre utiles en mathématiques discrètes, en particulier l’algèbre de Boole et les automates à états finis.

L’intérêt de cet ouvrage est de présenter la théorie en vue des applications informatiques des mathématiques finies, en restant très pédagogique, sans ostentation, tout en s’appuyant sur de nombreux exemples et exercices. Si les démonstrations sont claires, certes, le logicien ne trouvera pas toujours les définitions irréprochables, mais, grâce aux choix faits par l’auteur, l’informaticien se les appropriera et pourra les utiliser sans difficulté. C’est cette simplicité de présentation de notions abstraites et difficiles d’accès qui rend cet ouvrage intéressant, et ce d’autant plus que les traités couvrant ce domaine ne pullulent pas.

Sommaire :

* Fondements
– Mémento de logique
– Ensembles
– Relations binaires
– Fonctions
– Relations binaires internes
– Calculabilité et récursivité
– Notion de complexité

* Graphes
– Des points et des flèches
– Chemins et circuits
– Fermetures transitives
– Arbres et connexités
– Graphes multipartis

* Algèbre
– Opérateurs et algèbres
– Monoïdes et langages
– Dioïdes et algèbres de chemin
– Algèbre de Boole
– Algèbre de Kleene et automates à états finis