Première édition
ISBN : 978-2-7117-2077-4
240 pages, format 17 × 24 cm
Errata
|
Première éditionISBN : 978-2-7117-2077-4240 pages, format 17 × 24 cmErrata |
|
Seconde éditionISBN : 978-2-311-01400-6256 pages, format 17 × 24 cmErrata |
Tous les commentaires, suggestions et corrections (même de la moindre typo) sont les bienvenus. Pour cela, écrire à Olivier Carton. Le premier chapitre est disponible ci-dessous avec des liens actifs (table des matières, …).
Cet ouvrage a été rédigé lors d'un cours donné à plusieurs reprises aux élèves de première année de l'École Normale Supérieure. Il couvre les grands thèmes de l'informatique fondamentale et constitue à ce titre une introduction à ce sujet riche et passionnant.
Ce livre s'adresse aux étudiants en master d'informatique ou de mathématiques. Tout master d'informatique comporte un cours sur les automates finis, la compilation et les automates à pile. La calculabilité et la complexité sont indispensables à tout étudiant désireux d'avoir une base solide en informatique fondamentale. L'approche rigoureuse conviendra parfaitement aux étudiants en mathématiques ayant une inclination vers l'informatique. Cet ouvrage couvre une grande part du programme de l'option informatique de l'agrégation de mathématiques. Il sera sans nul doute propice à de nombreux développements pour les leçons d'oral. Des exercices corrigés permettent une bonne assimilation.
Aucune connaissance préalable n'est requise. Il est seulement supposé que le lecteur maîtrise quelques éléments de mathématiques enseignés en première année universitaire. Le premier objectif de cet ouvrage est d'introduire et d'expliquer les premières notions d'informatique fondamentale. De nombreux exemples illustrent les définitions. Les différentes notions sont mises en perspective et des connexions entre des concepts en apparence éloignés sont établies. Le second objectif est de permettre d'aller plus loin. Chacun des chapitres comprend des compléments. Ceux-ci sont l'occasion de montrer quelques joyaux parmi lesquels, le théorème de Schüzenberger, le théorème de Parikh et le théorème d'Immerman et Szelepcsényi.
J'espère que ce livre saura convaincre que l'informatique fondamentale est un domaine en plein essor mais déjà foisonnant de résultats profonds et remarquables. Il essaye humblement d'en apporter la preuve par une approche des concepts essentiels ponctuée de jolis succès.