Introduction
En 30 ans, l'informatique est devenue une industrie importante: 10%
des investissements hors bâtiments des sociétés françaises. Au
recensement de 1982, 50000 cadres techniciens se déclaraient
informaticiens, 150000 en 1991. Une certaine manière de pensée et de
communication a découlé de cette rapide évolution. L'informatique
apparaît comme une discipline scientifique introduisant des
problèmes nouveaux ou faisant revivre d'autres. Certains pensent que
l'informatique est la partie constructive des mathématiques,
puisqu'on ne s'y contente pas de théorèmes d'existence, mais du
calcul des objets. D'autres y voient les mathématiques concrètes,
puisque le domaine a l'exactitude et la rigueur des mathématiques, et
que la confrontation des idées abstraites à la réalisation de
programmes interdit le raisonnement approximatif. Une autre
communauté est intéressée surtout par la partie physique du domaine,
car une bonne part des progrès de l'informatique est due au
développement foudroyant de la micro-électronique.
La jeunesse de l'informatique permet à certains de nier son aspect
scientifique: ``les ordinateurs ne sont que des outils pour faire des
calculs ou des machines traitement de texte''. Malheureusement,
beaucoup de ``fous de la programmation'' étayent l'argument
précédent en ignorant toute considération théorique qui puisse les aider
dans leurs constructions souvent très habiles. Regardons la
définition du mot hacker fournie dans The New Hacker's
Dictionary [40], dictionnaire relu et corrigé
électroniquement par une bonne partie de la communauté informatique.
hacker [originally, someone who makes furniture with an axe] n.
1. A person who enjoys exploring the details of programmable systems
and how to stretch their capabilities, as opposed to most users, who
prefer to learn only the minimum necessary. 2. One who programs
enthusiastically (even obsessively) or who enjoys programming rather
than just theorizing about programming. 3. A person capable of
appreciating hack value. 4. A person who is good at programming
quickly. 5. An expert at a particular program, or one who frequently
does work using it or on it; as in ``a Unix hacker''. 6. An expert or
enthusiast of any kind. One might be an astronomy hacker, for example.
7. One who enjoys the intellectual challenge of creatively overcoming
or circumventing limitations. 8. [deprecated] A malicious meddler who
tries to discover sensitive information by poking around. Hence password hacker, network hacker. See cracker.
Hacker est un mot courant pour désigner un
programmeur passionné. On peut constater toutes les connotations
contradictoires recouvertes par ce mot. La définition la plus
infamante est ``2. One who ... enjoys programming rather than
just theorizing about programming.''. Le point de vue que nous
défendrons dans ce cours sera quelque peu différent. Il existe une
théorie informatique (ce que ne contredit pas la définition
précédente) et nous essaierons de démontrer qu'elle peut aussi se
révéler utile. De manière assez extraordinaire, peu de disciplines
offrent la possibilité de passer des connaissances théoriques à
l'application pratique aussi rapidement. Avec les systèmes
informatiques modernes, toute personne qui a l'idée d'un algorithme
peut s'asseoir derrière un terminal, et sans passer par une
lourde expérimentation peut mettre en pratique son idée. Bien sûr,
l'apprentissage d'une certaine gymnastique est nécessaire au début,
et la construction de gros systèmes informatiques est bien plus
longue, mais il s'agit alors d'installer un nouveau service, et non
pas d'expérimenter une idée. En informatique, théorie et
pratique sont très proches.
D'abord, il n'existe pas une seule théorie de l'informatique, mais
plusieurs théories imbriquées: logique et calculabilité,
algorithmique et analyse d'algorithmes, conception et sémantique des
langages de programmation, bases de données, principes des systèmes
d'exploitation, architectures des ordinateurs et évaluation de leurs
performances, réseaux et protocoles, langages formels et compilation,
codes et cryptographie, apprentissage et zero-knowledge
algorithms, calcul formel, démonstration automatique, conception et
vérification de circuits, vérification et validation de programmes,
temps réel et logiques temporelles, traitement d'images et vision,
synthèse d'image, robotique, ...
Chacune des approches précédentes a ses problèmes ouverts, certains
sont très célèbres. Un des plus connus est de savoir si P = NP,
c'est-à-dire si tous les algorithmes déterministes en temps
polynomial sont équivalents aux algorithmes non déterministes
polynomiaux. Plus concrètement, peut-on trouver une solution
polynomiale au problème du voyageur de commerce. (Celui-ci a un
ensemble de villes à visiter et il doit organiser sa tournée pour
qu'elle ait un trajet minimal en kilomètres). Un autre est de trouver
une sémantique aux langages pour la programmation objet. Cette
technique de programmation incrémentale est particulièrement utile
dans les gros programmes graphiques. A ce jour, on cherche encore un
langage de programmation objet dont la sémantique soit bien claire et
qui permette de programmer proprement. Pour résumer, en
informatique, il y a des problèmes ouverts.
Quelques principes généraux peuvent néanmoins se dégager. D'abord,
en informatique, il est très rare qu'il y ait une solution unique à
un problème donné. Tout le monde a sa version d'un programme,
contrairement aux mathématiques où une solution s'impose
relativement facilement. Un programme ou un algorithme se trouve très
souvent par raffinements successifs. On démarre d'un algorithme
abstrait et on évolue lentement par optimisations successives vers
une solution détaillée et pouvant s'exécuter sur une machine. C'est
cette diversité qui donne par exemple la complexité de la correction
d'une composition ou d'un projet en informatique (à l'Ecole
Polytechnique par exemple). C'est aussi cette particularité qui fait
qu'il y a une grande diversité entre les programmeurs. En
informatique, la solution unique à un problème n'existe pas.
Ensuite, les systèmes informatiques représentent une incroyable
construction, une cathédrale des temps modernes. Jamais une
discipline n'a si rapidement fait un tel empilement de travaux. Si on
essaie de réaliser toutes les opérations nécessaires pour déplacer
un curseur sur un écran avec une souris, ou afficher l'écho de ce
qu'on frappe sur un clavier, on ne peut qu'être surpris par les
différentes constructions intellectuelles que cela a demandées. On
peut dire sans se tromper que l'informatique sait utiliser la
transitivité. Par exemple, ce polycopié a été frappé à l'aide
du traitement de texte LATEX [31]
de L. Lamport (jeu de macros TeX de D. Knuth [26]),
les caractères ont été
calculés en METAFONT de D. Knuth [27],
les dessins en gpic version Gnu (R. Stallman)
de pic de B. Kernighan [23].
On ne comptera ni le système Macintosh (qui dérive fortement de
l'Alto et du Dorado faits à Xerox PARC [51, 32]),
ni OzTeX (TeX sur Macintosh), ni les éditeurs QED, Emacs, Alpha,
ni le système Unix fait à Bell laboratories
[44],
les machines Dec Stations 3100, 5000, Sun Sparc2, ni leurs composants
MIPS 2000/3000 [21] ou Sparc, ni le réseau Ethernet
(Xerox-PARC [36]) qui permet d'atteindre les serveurs
fichiers, ni les réseaux Transpac qui permettent de travailler à la
maison, ni les imprimantes Laser et leur langage PostScript,
successeur d'InterPress (J. Warnock à Xerox-PARC, puis Adobe Systems)
[2], qui permettent l'impression du document. On peut
évaluer facilement l'ensemble à quelques millions de lignes de
programme et également à quelques millions de transistors. Rien de
tout cela n'existait en 1960. Tout n'est que gigantesque mécano, qui
s'est assemblé difficilement, mais dont on commence à comprendre les
critères nécessaires pour en composer les différents éléments.
En informatique, on doit composer beaucoup d'objets.
Une autre remarque est la rapidité de l'évolution de l'informatique.
Une loi due à B. Joy dit que les micro-ordinateurs doublent de
vitesse tous les deux ans, et à prix constant. Cette loi n'a pas
été invalidée depuis 1978! (cf. le livre de Hennessy et Patterson
[19]). Si on
regarde les densités des mémoires ou des disques, on constate que
des machines de taille mémoire honorable de 256 kilo-Octets en 1978
ont au minimum 32 Méga-Octets aujourd'hui. De même, on est passé de
disques de 256 MO de 14 pouces de diamètre et de 20 cm de hauteur à
des disques 3,5 pouces de 4 GO (Giga-Octets) de capacité et de 5cm
de hauteur. Une machine portable de 3,1 kg peut avoir un disque de 500
MO. Il faut donc penser tout projet informatique en termes évolutifs.
Il est inutile d'écrire un programme pour une machine spécifique,
puisque dans deux ans le matériel ne sera plus le même. Tout
programme doit être pensé en termes de portabilité, il doit pouvoir
fonctionner sur toute machine. C'est pourquoi les informaticiens sont
maintenant attachés aux standards. Il est frustrant de ne pouvoir
faire que des tâches fugitives. Les standards (comme par exemple le
système Unix ou le système de fenêtres X-Window qui sont des
standards de facto) assurent la pérennité des programmes. En informatique, on doit programmer en utilisant des standards.
Une autre caractéristique de l'informatique est le côté instable
des programmes. Ils ne sont souvent que gigantesques constructions,
qui s'écroulent si on enlève une petite pierre. Le 15 janvier 1990,
une panne téléphonique a bloqué tous les appels longue distance aux
Etats-Unis pendant une après-midi. Une instruction break
qui arrêtait le contrôle d'un for dans un programme C s'est
retrouvée dans une instruction switch qui avait été
insérée dans le for lors d'une nouvelle version du programme
de gestion des centraux d'AT&T. Le logiciel de test n'avait pas
exploré ce recoin du programme, qui n'intervenait
qu'accidentellement en cas d'arrêt d'urgence d'un central. Le
résultat de l'erreur fut que le programme marcha très bien jusqu'à
ce qu'intervienne l'arrêt accidentel d'un central. Celui-ci, à
cause de l'erreur, se mit à avertir aussitôt tous ses centraux
voisins, pour leur dire d'appliquer aussi la procédure d'arrêt
d'urgence. Comme ces autres centraux avaient tous aussi la nouvelle
version du programme, ils se mirent également à parler à leurs
proches. Et tout le système s'écroula en quelques minutes. Personne
ne s'était rendu compte de cette erreur, puisqu'on n'utilisait jamais
la procédure d'urgence et, typiquement, ce programme s'est effondré
brutalement. Il est très rare en informatique d'avoir des
phénomènes continus. Une panne n'est en général pas le résultat
d'une dégradation perceptible. Elle arrive simplement brutalement.
C'est ce côté exact de l'informatique qui est très attrayant. En
informatique, il y a peu de solutions approchées. En
informatique, il y a une certaine notion de l'exactitude.
Notre cours doit être compris comme une initiation à l'informatique,
et plus exactement à l'algorithmique et à la programmation. Il
s'adresse à des personnes dont nous tenons pour acquises les connaissances
mathématiques: nulle part on n'expliquera ce qu'est une récurrence,
une relation d'équivalence ou une congruence. Il est orienté vers
l'algorithmique, c'est-à-dire la conception d'algorithmes (et non
leur analyse de performance), et la programmation, c'est-à-dire leur
implantation pratique sur ordinateur (et non l'étude d'un --- ou de
plusieurs --- langage(s) de programmations). Les cours d'algorithmique
sont maintenant bien catalogués, et la référence principale sur
laquelle nous nous appuierons est le livre de Sedgewick
[47].
Une autre référence intéressante par sa
complétude et sa présentation est le livre de Cormen, Leiserson et
Rivest [10]. Il existe bien d'autres ouvrages: Gonnet et
Baeza-Yates [15], Berstel-Pin-Pocchiola [8],
Manber [35], Graham-Knuth-Patashnik [17]....
Il faut aussi bien sûr signaler les
livres de Knuth [28, 29, 30]. Les cours de
programmation sont moins clairement définis. Ils dépendent souvent
du langage de programmation ou du type de langage de programmation
choisi. Nous nous appuierons sur le polycopié de P. Cousot
[11], sur le livre de Kernighan et Ritchie pour C [22],
sur le livre de Wirth pour Pascal [20],
sur le livre de Nelson [39]
ou Harbison pour Modula-3[18].
Le cours est organisé selon les structures de données et les méthodes
de programmation, utilisées dans différents algorithmes. Ainsi seront
considérés successivement les tableaux, les listes, les piles, les
arbres, les files de priorité, les graphes. En parallèle, on
regardera différentes méthodes de programmation telles que la
récursivité, les interfaces ou modules, la compilation séparée, le
backtracking, la programmation dynamique. Enfin, nous essaierons
d'enchaîner sur différents thèmes. Le premier d'entre eux sera la
programmation symbolique. Un autre sera la validation des programmes,
notamment en présence de phénomènes asynchrones. Enfin, on essaiera de
mentionner les différentes facettes des langages de programmation
(garbage collection, exceptions, modules, polymorphisme,
programmation incrémentale, surcharge). Nous fournirons pour chaque
algorithme deux versions du programme (quand nous en montrerons son
implémentation): une dans le langage Java et une autre en Caml
(langage enseigné en classes préparatoires). Une introduction à Java
figurera en annexe, ainsi qu'un rappel de Caml. La lecture des
chapitres et des annexes peut se mener en parallèle. Le lecteur qui
connaît les langages de programmation n'aura pas besoin de consulter
les annexes. Celui qui démarre en Java ou en Caml devra plutôt
commencer par les appendices.
Le choix de considérer les langages Java et Caml est dicté par deux
considérations. Ce sont d'abord des langages fortement typés. Il est
impossible de finir un programme par une violation de la mémoire ou
une erreur système irrémissible. Les deux langages vérifient la
validité des index dans les accès aux tableaux ou des références dans
les accès aux structures de données dynamiques. Par ailleurs, les deux
langages ont une gestion automatique de la mémoire, car ils disposent
d'un glaneur de cellules (garbage collector en anglais)
permettant de récupérer automatiquement l'espace mémoire perdu. Cela
simplifie notablement l'écriture des programmes et permet de se
concentrer sur leur essence. L'allocation mémoire, elle, reste
toujours explicite et on pourra toujours comprendre l'espace mémoire
exigé par un programme. Autrefois, le cours étais fait en Pascal et en
C; il sera possible de disposer d'appendices donnant les programmes de
ce cours dans ces deux langages.
Historiquement, Java est un langage orienté-objet, quoique nous
utiliserons peu cette particularité dans notre cours qui doit garder
un aspect élémentaire. Il provient de Simula-67, Smalltalk,
Modula-3[39] et C++[49]. Caml est un
langage plutôt fonctionnel, dialecte de ML, dont il existe plusieurs
implémentations: Caml et SML/NJ développés à l'INRIA et à Bell
laboratories. Il provient de Lisp et de
Scheme[1]. Depuis peu de temps, Caml dispose
d'une très efficace extention orientée objet, Objective Caml (Ocaml).
Les deux langages n'ont pas l'efficacité de C ou C++, quoique ceci
reste à démontrer dans la manipulation des structures de données
dynamiques. Mais à l'ère des machines RISC, il vaut mieux
essayer d'écrire des programmes simples et compréhensibles. C'est le
style que nous voulons adopter ici. La structure de nos programmes
sera très souvent indépendante du langage de programmation, comme en
attesteront les quatre versions de chacun de nos programmes en Pascal,
C, Caml ou Java.
Pour être bien clair, prenons l'exemple du calcul de p. Un
programme C esthétiquement correct, qui utilise la formule p/4=
arctan(1)= Sn=0n=¥ (-1)n/(2n+1), est
#include <stdio.h>
#define N 10000
main()
{
float pi = 0;
int sign = 1;
int n = 1;
int m = 1;
while (n < N) {
pi = pi + (float)sign / m;
m = m + 2;
sign = -sign;
++n;
}
pi = 4 * pi;
printf ("%.6f\n", pi);
}
Mais le programme C suivant [40] est
interdit dans notre cours.
#define _ -F<00 || --F-OO--;
int F=00,OO=00;
main(){F_OO();printf("%1.3f\n", 4.*-F/OO/OO);}F_OO()
{
_-_-_-_
_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_
_-_-_-_
}
Ce programme fait un nombre inconsidéré d'appels au
préprocesseur et beaucoup trop d'effets de bord (cf. page
X). Il est illisible. Il faut avoir une
conception simple et donc esthétique des programmes. On n'est plus à
l'époque où tout se joue à l'instruction machine près. La puissance
des ordinateurs a rendu très viable la programmation sans
optimisations excessives. Tout l'art du programmeur est de comprendre
les quelques endroits critiques d'un programme, en général très peu
nombreux, où les optimisations sont nécessaires. Donc le programme
cryptique précédent, ou tout autre bourré d'optimisations inutiles
sera mauvais et donc interdit.
Dans cet exemple, typiquement, la convergence du calcul de p est
mauvaise. Inutile donc de chercher à optimiser ce programme. Il faut
changer de formule pour le calcul. La formule de John Machin (1680-1752)
fait converger plus vite en calculant p/4 = 4 arctan(1/5) -
arctan(1/239). Une autre technique consiste à taper sur la commande
suivante sur une machine de l'Ecole Polytechnique
% maple
|\^/| MAPLE V
._|\| |/|_. Copyright (c) 1981-1990 by the University of Waterloo.
\ MAPLE / All rights reserved. MAPLE is a registered trademark of
<____ ____> Waterloo Maple Software.
| Type ? for help.
> evalf(Pi,1000);
3.14159265358979323846264338327950288419716939937510582097494459230781\
6406286208998628034825342117067982148086513282306647093844609550582231\
7253594081284811174502841027019385211055596446229489549303819644288109\
7566593344612847564823378678316527120190914564856692346034861045432664\
8213393607260249141273724587006606315588174881520920962829254091715364\
3678925903600113305305488204665213841469519415116094330572703657595919\
5309218611738193261179310511854807446237996274956735188575272489122793\
8183011949129833673362440656643086021394946395224737190702179860943702\
7705392171762931767523846748184676694051320005681271452635608277857713\
4275778960917363717872146844090122495343014654958537105079227968925892\
3542019956112129021960864034418159813629774771309960518707211349999998\
3729780499510597317328160963185950244594553469083026425223082533446850\
3526193118817101000313783875288658753320838142061717766914730359825349\
0428755468731159562863882353787593751957781857780532171226806613001927\
876611195909216420199
> quit;
%