C e polycopié est le support écrit du cours ``Informatique Fondamentale `` de deuxième année. Il porte sur les
notions plus avancées de la programmation telles que les
algorithmes sur les graphes, la modularité, la programmation par
objets, la vérification de programmes, l'analyse syntaxique,
l'exploration exhaustive et la concurrence. Bien sûr, chacune de ces
notions ne sera vue que partiellement, mais l'ensemble de ces
chapitres se veut représenter un bagage informatique minimal pour tout
ingénieur moderne. Ce cours suppose connues des notions élémentaires
comme la programmation impérative et itérative, ou récursive,
manipulant des structures de données scalaires ou composites telles
que les tableaux, les enregistrements, les listes ou les arbres.
Le langage de programmation choisi est Java. Nous essaierons de donner
des programmes équivalents en Ocaml, et parfois en C. Le choix du
langage est secondaire, car l'ensemble du cours est quasiment
indépendant du langage. Au début, un style très pascalien de
programmation impérative sera suivi. La programmation par objets ne
sera développée qu'après quelques chapitres. Ce qui importe dans le
choix du langage est d'abord d'avoir un langage fortement typé, et
ensuite de disposer d'un système automatique de gestion de la mémoire,
permettant de garder les notions développées à un bon niveau
d'abstraction, sans ignorer les problèmes de complexité. Mais nous
garderons à l'esprit quelques inconvénients dus au choix de Java:
lourdeur, inefficacité, par exemple.
Les participants à ce cours ont donc grandement contribué à
l'établissement de ce polycopié. Merci donc à François Anceau, Patrice
Bertin, Gilles Dowek, Georges Gonthier, Daniel Krob, Philippe
Chassignet, Frédéric Chyzak, Ian Mackie, Guillaume Poupard, Laurent
Viennot, Dominique Rossin, Didier le Botlan, James Leifer, Alan
Schmitt et Simon Patarin. Pour une partie, ce cours s'inspire de
l'ancien cours de première année ``Algorithmes et Programmation ``
effectué de 1992 à 2001 avec Robert Cori.
Cette première version du polycopié a bénéficié de la relecture et des
nombreuses remarques de Philippe Chassignet, Robert Cori,
Jean-Christophe Filliâtre, Georges Gonthier, Luc Maranget, Catuscia
Palamidessi et Didier Rémy. Les assertions du
chapitre 5 ont été mises au point grâce au
programme Why de Jean-Christophe Filliâtre.
Enfin, si ce cours est entièrement disponible sur le Web, cela est dû
à Luc Maranget et à son très efficace traducteur Hevea de format TeX
en format Html. Le polycopié se trouve en
http://www.enseignement.polytechnique.fr/informatique/
sous la rubrique ``Informatique Fondamentale ``.
Polycopié, version 1.0