Résumé
Ce document se propose de donner quelques rudiments d'algorithmique à un public
littéraire. Pour relever ce dé, on commence par une longue introduction dénissant la
notion d'algorithme et présentant les diérents outils dont nous auront besoin pour la suite.
Après quelques notes sur la récursivité, on présente les structures de données fondamentales
et quelques algorithmes incontournables pour le public visé. Des annexes complètent ce
polycopié et pourront être réservées à une seconde lecture.
Fig. 1 Alan M. Turing (1912-1954), l'un des pères de l'Informatique.
1
2 TABLE DES MATIÈRES
Table des matières
1 Du problème au programme : l'algorithme 3
1.1 Dénition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Machines de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Intérêt de cette dénition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Apparté mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Retour sur les algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Informatique : rappels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6.2 Programme, système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6.3 Mémoire et processeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Récursivité 13
2.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Contre exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Ranements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Structuration des données 16
3.1 Tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3 Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3.1 Parcours d'un arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3.2 Arbres de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3.3 Des arbres particuliers : les tas . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 Hachages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.4.1 Où l'on retrouve les listes chaînées . . . . . . . . . . . . . . . . . . . . . 21
3.4.2 Tables de hachages à adressage ouvert . . . . . . . . . . . . . . . . . . . 22
3.5 Piles & les . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Divers algorithmes de tri 22
4.1 Tri par insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2 Tri bulle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3 Tri par tas ou heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.4 Tri par fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.5 Tri rapide ou quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.6 Tris linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.6.1 Tri par comptage ou par dénombrement . . . . . . . . . . . . . . . . . . 26
4.6.2 Tri par base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5 Recherche de motifs 27
5.1 Première approche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2 Utilisation d'un hachage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3
6 Conclusion 30
6.1 Pour nir. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6.2 Conseils bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
A Manipulations numériques 31
A.1 Génération de nombres aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . 31
A.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Bibliographie 33
Index 34
1 Du problème au programme : l'algorithme
Le mot algorithme vient du nom du mathématicien persan Al Khwarizmi (environ
820 après J.C.) dont le traité d'arithmétique permis la diusion en Occident de règles de calcul
sur la représentation décimale des nombres (découvertes par les Indiens)1.
Les premiers algorithmes connus remontent pourtant à l'Antiquité : l'algorithme d'Euclide
(IIIème siècle avant J.C) permettant de déterminer le PGCD de deux nombres, celui d'Archim
ède (IIIème siècle avant J.C) d'approximer ¼, ceux de Diophante d'Alexandrie (IIIème siècle
après J.C) de résoudre des équations en nombres entiers, sans oublier les diérents algorithmes
des grecs et des égyptiens permettant de calculer des surfaces.
On le voit, l'algorithmique est la lle des Mathématiques. Elle a beaucoup évolué ces cinquante
dernières années du fait de l'émergence de sa petite s÷ur l'Informatique et du boom de
la recherche, tant en Mathématiques qu'en Informatique.
Dans toute la suite, la formalisation mathématique ne dépasse pas le niveau de Mathématiques
éxigé au Baccalauréat dans les sections littéraires mais la formalisation et l'abstraction
pourront choquer au premier abord.
1.1 Dénition
Dans la préface de l'édition française de [CLR94], la bible de Cormen et al., on peut lire2 :
[L'algorithmique] est le c÷ur de l'informatique. Pour tous ceux qui doivent [. . .]
faire travailler un ordinateur, il est essentiel de comprendre ses principes fondamentaux
et de connaître ses éléments de base. Une formule 1 ne se conduit pas comme
une voiture à pédales. De même un ordinateur ne s'utilise pas comme un boulier.
L'algorithmique est le permis de conduire de l'informatique. Sans elle, il n'est pas
1Ainsi parle-t-on à tort des nombres arabes tandis que l'on devrait dire nombres sanscrits.
2[CLR94], page xiii.
4 1. Du problème au programme : l'algorithme
concevable d'exploiter sans risque un ordinateur.
Un algorithme représente ce que doit faire un morceau de programme informatique dans les
grandes lignes. Il y a beaucoup de manières de représenter un algorithme, la meilleure étant
probablement l'utilisation d'un pseudo-langage de programmation, ce que nous ferons.
Le grand problème de l'algorithmique est de mettre au point des algorithmes ecaces en
terme de temps de calcul (mesuré en opérations élémentaires) et d'espace mémoire requis, ces
deux contraintes étant incompressibles et fortement liées ; si l'espace requis diminue, c'est au
détriment du temps de calcul et réciproquement. En eet, si un programme est trop lourd en
terme de temps de calcul et/ou d'espace mémoire requis, son utilisation nécessitera un supercalculateur3
et non un simple poste de travail.
La mesure du temps de calcul et de l'espace mémoire mobilisé sont donc fondamentaux pour
évaluer et comparer des algorithmes. Pour cela, l'unité de mesure est la taille des données du
problème. Ainsi, la bonne question à se poser est : que se passe-t-il si je double la taille des
données ?
Nous voilà à même de donner une dénition d'un algorithme :
Dénition 1.1.1 Un algorithme est une suite nie d'instructions élémentaires qui, étant donné
des paramètres typés, renvoie la solution d'un problème donné.
Il nous faut donc dénir les termes instruction élémentaire, paramètres typés, problème et
préciser suite nie.
Commençons par suite nie : il faut non seulement que la suite d'instructions soit
nie mais aussi et surtout qu'elle s'execute un nombre ni de fois (on dit que l'algorithme
termine ). Il faut toujours s'assurer qu'un algorithme termine.
Par problème , on entend toute question dont la réponse est true ou false ou le résultat
d'un calcul (numérique ou non).
Par paramètre typé , on entend cette donnée est un entier, cette autre une chaîne de
caractères ; autrement dit, une donnée d'une nature particulière : entier, ottant, caractère,
chaîne de caractères, etc. Le type inue évidemment sur le traitement.
Imaginons que l'on dispose d'une calculatrice programmable proposant les opérations +, ¡,
¤, ¥ et p. Ce sera donc le nombre d'appels de ces opérations élémentaires que l'on comptera
pour évaluer la complexité d'un algorithme implémenté sur cette calculatrice. Un problème est
par exemple résoudre ax + b = 0 . L'algorithme est le suivant :
Algorithme 1.1.2
Equation(a, b)
Si b = 0, alors :
Si a 6= 0, alors :
3Les super-calculateurs actuels coûtent plusieurs milliards d'euro, leur(s) processeur(s) tien(nen)t dicilement
sur un terrain de tennis et se refroidi(ssen)t à l'air liquide (-270±C). . .
1.2 - Machines de Turing 5
x = 0.
Si a = 0, alors :
il y a une innité de solutions.
sinon :
Si a = 0, alors :
il y n'a pas de solution.
sinon x = ¡b=a.
La terminaison est triviale. Ici, outre des tests, on note une multiplication ¡1 et une division.
Ainsi, le matériel à son importance. En eet, quand bien même on manipule des algorithmes
et des données abstraites, il n'en demeure pas moins que ce n'est pas (que) pour la gloire mais
bien en vue d'une utilisation dans la vraie vie. Il faudra donc toujours garder à l'esprit que
l'implémentation d'un algorithme dépend étroitement de la machine sur laquelle le programme
en résultant sera exécuté : il sera dicile d'utiliser une calculette à 2 francs 6 sous pour trier
un gros tableau de données.
Il existe plusieurs modéles théoriques pour aborder la suite, en particulier celui des machines
de Turing, que nous suivrons, et celui des machines RAM4 (Random Access Machines, très
proches de nos machines actuelles, issus des travaux de von Neumann). On peut démontrer
que, quelque soit le modèle retenu, les caractéristiques des algorithmes sont les mêmes, ce qui
est moral.
1.2 Machines de Turing
Dénition 1.2.1 On appelle alphabet un ensemble § ni non vide. Ses éléments ¾ 2 § sont
appelés lettres ou caractères. On note ² le mot vide (qui ne contient aucune lettre). On note
j¾j la longueur de ¾, c'est le nombre de lettres de ¾. On note §¤ l'ensemble des mots composé
à partir de §.
Une machine de Turing est un ordinateur imaginaire qui nous servira à dénir la notion
de complexité d'un algorithme : ce sera le nombre d'opérations élémentaires d'une machine de
Turing.
Dénition 1.2.2 On appelle machine de Turing, la donnée de
M= hQ;§; q0; ±; Fi
où
Q est l'ensemble (ni) des états de la machine,
§ est l'alphabet de la machine (avec lequel elle code ses données),
q0 2 Q est l'état initial,
± est la fonction de transition de M dénie par ± : Q £ § 7! Q £ § £ f¡1; 0; 1g,
F l'ensemble des états naux, F µ Q.
4Cf. 1.6.1, page 10.
6 1. Du problème au programme : l'algorithme
Une machine de Turing dispose d'un ruban de longueur nie à gauche, innie à droite,
divisé en cases. Chaque case ne comporte qu'un unique symbole. La première case contient
l'état initial q0 et la machine dispose d'un symbole qF ou (yF ; nF ) de n, selon que le problème
envisagé est un calcul ou un problème de décision. Outre cette bande (gurant la mémoire), la
machine dispose d'une tête de lecture/écriture actionnée par un mécanisme (gurant le processeur).
Ce mécanisme est entièrement déterminé par la fonction ± (les circuits imprimés dans le
silicium). On rappelle que Q£§ est l'ensemble formé des couples (q; ¾) avec q 2 Q et ¾ 2 §. De
même, Q£§£f¡1; 0; 1g est-il l'ensemble des triplets (q; ¾; ²) où q 2 Q, ¾ 2 § et ² 2 f¡1; 0; 1g.
Ainsi ± associe-t-elle à un couple (q; ¾) un triplet (q0; ¾0; ²).
Sur la bande, immédiatement à la droite de q0, un certain nombre de cases sont occupées
par des symboles (un par case), ces symboles représentant les données du problème. 0 2 § gure
le blanc. À chaque instant, l'état de la machine est entièrement déterminé par ± et les données
initiales. Ainsi, ±(q; ¾) = (q0; ¾0; ²) signie que quand on est dans l'état q et que l'on lit ¾ 2 §,
on doit se déplacer de ² (¡1 vers la gauche, 0 ne pas bouger, 1 vers la droite), passer dans l'état
q0, remplacer ¾ par ¾0.
On prend les conventions :
q0 ne peut être eacé,
on ne peut pas aller plus à gauche quand on lit q0,
à l'instant initial, il n'y a qu'un nombre ni de symboles diérents de 0 2 §,
la machine s'arrête quand l'un des états de F est atteint,
le contenu nal de la bande correspond alors au résultat du calcul quand la machine est
dans l'état qF , l'état yF correspond à une réponse positive au problème de décision, l'état
nF correspond à une réponse négative.
Avant le lancement de la machine, les données ont été écrites sur la bande immédiatement à
droite de q0 et la tête de lecture positionnée sur q0. C'est l'état initial. Il y a un ou artistique
(dans la pratique seulement) sur l'état nal. En eet, ce peut être un symbole de l'alphabet que
l'on écrira donc sur la bande (typiquement pour un problème de décision qF ou qN) ou quelque
chose de plus abstrait déni par ± (typiquement dans le cadre d'un calcul).
Exemple 1.2.3 Soit l'alphabet § = f0; 1; #; q0g. On va dénir une machine de Turing additionnant
deux entiers. Outres les conventions précédentes, on décide de coder un entier par son
écriture en binaire suivi de #. Je vous rappelle qu'un entier a s'écrit en binaire :
a = §n
i=0ai:2i
où ai 2 f0; 1g et n = blog2 ac (n est le plus grand entier tel que a ¸ 2n) soit :
a = a0 + a121 + : : : + an2n
Ainsi, 5 s'écrit-il 101 (1:22+1:20), 8 1000 (1:23), etc. Si vous regardez bien, en remplaçant 2 par
10, vous devriez vous rappeler les paroles de votre instituteur lorsque vous appreniez l'addition
entière.
Exercice 1.2.4 Écrire l'algorithme d'addition.
1.3 - Intérêt de cette dénition 7
Pour simplier, plutôt qu'une unique bande, on va utiliser une machine à trois bandes : une
pour chaque entrée, une autre pour le résultat. Pour initialiser la machine, on copie les entiers
a et b sur les deux premières en commençant par la droite. Après chaque entier, on inscrit un #.
Pour additionner a et b, la formule (attention aux retenues, 1 + 1 = 10 et 1 + 1 + 1 = 11 !)
est :
s = §n
i=0si:2i = §n
i=0ai:2i + §n
i=0bi:2i
où m = bmax(log2 a; log2 b)c (m est donc le plus grand entier5 vériant 2m · max(a; b)) et
si ´ ai + bi + ri mod 2 avec r dénit par : r0 = 0 et ri+1 = 0 si (ai + bi + ri) · 1, 1 sinon.
On suppose que les trois têtes de lecture sont solidaires et que les deux premières bandes
sont accessibles en lecture seule, la dernière en lecture écriture. En listant les cas possibles,
on voit vite qu'il nous faut deux états principaux q0 et qr. En détails, on a une fonction ± :
Q £ § £ § £ § ! Q £ § £ f0; 1g dont voici les principaux états :
±(q0; q0; q0; q0) = (q0; 1; q0)
±(q0; 1; #; 0) = (q0; 1; 1)
±(q0; #; 1; 0) = (q0; 1; 1)
±(q0; 0; #; 0) = (q0; 1; 0)
±(q0; #; 0; 0) = (q0; 1; 0)
±(q0; 0; 0; 0) = (q0; 1; 0)
±(q0; 1; 1; 0) = (qr; 1; 0)
±(qr; 1; 0; 0) = (qr; 1; 0)
±(qr; 0; 1; 0) = (qr; 1; 0)
±(qr; 1; #; 0) = (qr; 1; 0)
±(qr; #; 1; 0) = (qr; 1; 0)
±(qr; 1; 1; 0) = (qr; 1; 1)
±(qr; 0; 0; 0) = (q0; 1; 1)
±(qr; #; 0; 0) = (q0; 1; 1)
±(qr; 0; #; 0) = (q0; 1; 1)
Exercice 1.2.5 Compléter cette table pour faire apparaître qF et s'assurer ainsi de la terminaison.
Remarque 1.2.6 Il faudra me croire (si ça n'est pas déjà trivial) quand je dis qu'utiliser une
bande ou en utiliser trois comme ici revient au même.
1.3 Intérêt de cette dénition
De telles machines de Turing permettent de décrire de manière élémentaire tout problème
de calcul ou de décision. Ces machines ont une mémoire centrale, une unité de calcul, lisent
des données et les traitent en conséquence. En fait, les ordinateurs actuels répondent à cette
dénition.
On note que si l'on avait écrit les nombres de gauche à droite, le nombre de déplacements
de la tête de lecture/écriture auraient été beaucoup plus nombreux. De même, si l'on n'avait
5On note bxc le plus grand entier n tel que n = bxc · x.
8 1. Du problème au programme : l'algorithme
utilisé qu'une unique bande. On retiendra que la structure des données est fondamentale et fortement
liée à l'algorithme (comprendre si l'on choisit une mauvaise représentation, l'algorithme
de traitement ne pourra pas être ecace).
Si l'on rééchit plus de cinq secondes, on note que le calcul a demandé m+3 déplacements
de la tête (un pour quitter l'état initial, m+1 pour remplir les cases de la somme, une dernière
pour marquer la n du calcul) et 3m + 1 cases mémoires (m pour chacune des deux données,
m+1 pour le résultat). On remarque donc que le nombre d'étapes de calcul est lié à l'occupation
mémoire (par un facteur 3). Ici, les opérations élémentaires sont les déplacements de la tête. En
fait, c'est ± qui dénit ces opérations élémentaires. La complexité d'un algorithme est mesurée
par le nombre d'opérations élémentaires nécéssaires au calcul de la solution sur une machine.
On retiendra de tout cela que :
pour un même problème, il y a plusieurs machines de Turing dont certaines sont plus
ecaces que d'autres,
pour un même problème, si l'on fait baisser l'occupation de la mémoire, on augmente le
nombre d'opérations élémentaires,
une machine implémente un algorithme et donc, il existe plusieurs algorithmes pour un
même problème, certains étant moins coûteux que d'autres (du point de vue de l'occupation
de la mémoire ou du point de vue du nombre d'opérations élémentaires).
1.4 Apparté : la notation O(x), polynômes, exponentielles, logarithmes, partie
entière et congruences
Un polynôme est une expression anxn + : : : + a2x2 + a1x + a0. Le terme intéressant est
anxn ; an étant une constante, on la néglige aussi. Finalement, dans l'expression précédente,
seule nous intéresse xn car c'est le terme qui croît le plus vite : on dit que l'expression est de
l'ordre de xn, ce que l'on note :
anxn + : : : + a2x2 + a1x + a0 = O(xn)
Pour s'en convaincre, regardons la contribution de chacun des termes : soit le polynôme
n2 + n + 1. Si n = 10,
n2
n2 + n + 1
=
102
102 + 10 + 1
= 0:90
n
n2 + n + 1
=
10
102 + 10 + 1
= 0:09
Je ne pense pas avoir besoin de poursuivre l'expérience avec le malheureux texte constant. Si
maintenant on prend n = 100, la contribution du terme quadratique est encore bien supérieure :
n2
n2 + n + 1
=
1002
1002 + 100 + 1
= 0:99
1.5 - Retour sur les algorithmes 9
Une fonction exponentielle est de la forme kx (k une constante donnée). On a toujours, pour
x susamment grand et n un entier donné, que kx est beaucoup plus grand que xn d'où :
·xn + ¸kx = O(kx)
Ici, pour reprendre l'exemple précédent, voyons la contribution des diérents termes : soit
l'expression n2 + 2n. On a :
n2
n2 + 2n =
102
100 + 1024
= 0:08
2n
n2 + 2n =
1024
100 + 1024
= 0:91
Dans tout les cas, seul nous intéresse le terme dont la croissance est la plus rapide. Attention
toutefois, l'arithmétique des O n'est pas conforme à l'arithmétique usuelle et O(n)¡O(n) n'est
pas nul.
Pour ceux que la notation log2 » laisse rêveur, on peut dénir très grossièrement la fonction
logarithme comme étant celle telle que pour » 2 R+ n f0g, si º = log2 » alors 2º = ». Autrement
dit, log2 2» = ».
On a déjà rencontré la notation b»c. Elle représente l'entier immédiatement inférieur à » :
b2:1c = 2 et évidemment b3c = 3.
Complexité Type
O(1) accéder au premier élément d'un ensemble de données
O(log n) couper un ensemble en deux puis chacun en deux, etc.
O(n) parcourir un ensemble de n données
O(n log n) couper répétitivement un ensemble en deux et parcourir chacune des parties
O(n2) parcourir un ensemble de données une fois par élément d'un autre ensemble de
même taille
O(2n) générer tous les sous-ensembles possibles d'un ensemble de données
O(n!) générer toutes les permutations possibles d'un ensemble de données
1.5 Retour sur les algorithmes
On vient de voir qu'il existe diérents type d'algorithmes. On a aussi largement évoqué le
temps de calcul de ces algorithmes. Enn, on a vu que si l'entrée est un entier n, on mesure la
complexité par rapport à log2 n. Ainsi, un algorithme qui s'eectue en O(n) instructions est-il
exponentiel.
Dans la pratique, il est des instructions plus rapides que d'autres : l'aectation, l'addition et
la soustraction sont parmi les plus rapides ; la multiplication est assez lente, la division et l'exponentiation
encore plus ; l'appel de fonction bat tous les records du fait des lectures/écritures
en mémoire centrale. Le test dépend des données.
10 1. Du problème au programme : l'algorithme
Aussi, la bonne question à poser est que se passe-t-il lorsque la taille des données
est multipliée par 2 ? Si n est la taille des données (de taille équivalente) du problème6,
disons qu'un algorithme qui s'exécute en :
O(log n) est quasi-instantané (algorithme sub-linéaire),
O(n) ou O(n log n) est très rapide (algorithme linéaire),
O(n2) ou O(n3) commence à être lent,
O(nk) pour k > 3 devient très lent et souvent impraticable.
La qualité d'un algorithme se mesure à sa complexité mais aussi à sa clarté et sa simplicit
é. Un algorithme complexe sera sources d'erreurs de programmation (dures à déceler et qui
prennent donc plus de temps au programmeur). De plus, on mesure la complexité en négligeant
les constantes multiplicatives aussi un algorithme en O(n
p
n) pourra être meilleur qu'un
concurrent en O(n
p
2) (par exemple si ce dernier est alambiqué et si sa constante multiplicative
est très grande).
1.6 Informatique : rappels
1.6.1 Architecture
Lorsque Johann von Neumann (1903-1957) se lança dans l'Informatique, il comprit assez
vite que les machines de l'époque n'étaient que des calculateurs et non pas des machines autonomes.
Leur autonomie vient de ce que von Neumann comprit que données et algorithmes
doivent tout deux résider en mémoire et non pas être entrés à la main par un opérateur. Pour
cela, il fallait représenter un algorithme sous forme numérisée (Proposition de von Neumann).
De plus, les premiers calculateurs travaillaient tous en système décimal, nécessitant ainsi un
grand nombre de composants et donc d'opérations. Il conçut donc (1946, l'EDSAC) la première
machine calculant en binaire et à programme enregistré, base de presque toutes les machines
actuelles. Elle était composé de cinq éléments :
la mémoire,
l'unité arithmétique et logique,
l'unité de contrôle,
l'entrée,
la sortie.
La mémoire était découpée en mots de n bits (en l'occurence 40), chaque mot disposant d'une
adresse. Un mot pouvait contenir un entier ou deux instructions ; chaque instruction contenait
un type et une adresse mémoire. Enn, l'UAL contenait un registre (l'accumulateur). Une
instruction permettait ainsi par exemple d'ajouter le contenu d'un mot à celui du registre, d'enregistrer
le registre dans la mémoire, de charger un mot dans le registre, etc (via leur adresses).
L'unité de contrôle se chargeait de lire dans la mémoire les instructions et les données pour les
transmettre à l'UAL qui les traitait. Tant l'unité de contrôle que l'UAL sont désormais partie
intégrante du processeur.
6Ce qui revient au même ou presque que de considérer le logarithme en base 2 de la longueur des données
exprimées en binaire. . .
1.6 - Informatique : rappels 11
Fig. 2 Johann von Neumann (1903 - 1957) devant le premier ordinateur de l'Institute of
Advanced Studies de Princeton.
L'innovation de von Neumann tient en cette numérisation de l'algorithme. Dès lors, donn
ées et algorithmes résident en mémoire, côte à côte et l'UAL est capable de beaucoup plus que
de simple calculs : elle interprête l'algorithme sous sa forme numérisée.
1.6.2 Programme, système
Depuis que les ordinateurs sont construits sur le modèle de von Neumann, ce sont des
machines autonomes. À ce titre, elles sont capables de se gérer sans intervention humaine pour
beaucoup de tâches. On a vu apparaître assez vite les premiers langages de programmation. Ces
derniers permettent de traduire un code source compréhensible par un humain en une suite de
mots machine exécutables par la machine (je vous rappelle qu'il s'agit de suites de bits). C'est
à la même époque que la notion de système d'exploitation est apparue. Il s'agit d'un ensemble
de programmes permettant une (plus) grande autonomie à la machine.
Dans ce cadre, l'informatique s'est stratiée : on n'écrit plus de programme directement
en binaire mais on utilise le langage assembleur qui est plus compréhensible. Comme c'est encore
12 1. Du problème au programme : l'algorithme
assez barbare, on programme dans des langages plus évolués (plus proches du langage humain),
dits langages de haut niveau qui sont ensuite traduits en assembleur puis le résultat est traduit
en langage machine.
Une autre forme de cette stratication se retrouve dans la notion de fonction et dans celle
de bibliothèque. Plutôt que de réécrire à chaque fois les mêmes séquences de code pour faire
telle ou telle tâche usuelle (enregistrer un chier sur le disque, le monter en mémoire, etc.), des
bibliothèques de fonctions ont été mises au point. Une fonction est un morceau de programme
que l'on peut appeler par un nom en fournissant éventuellement des paramètres, à la manière
d'une fonction mathématique.
Une autre forme encore de stratication se retrouve dans l'architecture des systèmes d'exploitations
; les systèmes bien conçus fonctionnent comme suit :
le noyau est l'interface entre le matériel et le reste du monde,
les programmes sont des processus à part, qui font appel au noyau pour les tâches fondamentales
(accès au matériel par exemple).
Les programmes orent en particulier l'interface utilisateur (interface graphique, shell, . . .).
1.6.3 Mémoire et processeur
Il faut voir la RAM7 comme une bande de cases contenant des entiers, un gros tableau
d'entiers. Chaque case a une taille xe. Une case contient un octet8 et est adressable. Par
adressable on entend que l'on peut dire à la machine d'aller chercher la valeur contenue dans
telle ou telle case. Cette dernière y accèdera par un pointeur.
Un programme est un chier sur le disque. Un processus est le résultat de l'exécution d'un
programme. Un processus dispose d'un espace mémoire contenant son code machine, une pile
et un tas. Le tas est en bas, la pile en haut ; le tas monte et la pile descend à mesure que le
programme a besoin de mémoire. La pile contient les informations relatives à chaque appel de
fonction (qu'il s'agisse d'une fonction du programme ou d'une fonction d'une des bibliothèques).
La machine y stockera les paramètres passés en argument à ladite fonction, de la place pour le
résultat et encore d'autres choses.
L'adressage de la mémoire permet des sauts dans les suites d'instructions. En principe le
processeur exécute les instructions de manière séquentielle. Des structures comme
if (condition)
instruction
else
autre_instruction
fi
ou
7Random Access Memory.
8Un octet correspond à la taille d'un caractère soit 8 bits sur la majorité des machines actuelles. Il existe
des architectures sur lesquelles les octets sont codés sur 7 ou 9 bits. Une autre dénition d'octet est : unité
élémentaire de mémoire ou plus petite quantité de mémoire adressable .
1.7 - Conclusion 13
for i = 0 .. n do
instruction(i)
done
nécessitent de pouvoir accéder à tout instant à n'importe quel mot machine, qu'il s'agisse d'instructions
ou de données. Les mots mémoire codant des instructions correspondent à des circuits
imprimés dans le silicium du processeur. Il peut s'agir d'opérations arithmétiques, d'opérations
de lecture/écriture dans la mémoire, d'instructions de saut, etc.
1.7 Conclusion
Le paysage est le suivant : un programmeur doit résoudre un problème donné. Sa première
réaction sera de s'aranchir de l'environnement pour se demander comment le résoudre dans
l'absolu. Il mettra donc au point un algorithme puis il en évaluera les performances. Pour cette
dernière tâche, il a à sa dispoition un cadre théorique que l'on vient d'esquisser. Ceci fait, il
devra implémenter son algorithme pour obtenir un programme exécutable qu'il livrera à l'usager
après moult tests et au moins autant de corrections (éventuellement de l'algorithme lui-même).
La qualité du produit ni, le programme, dépendra fortement des machines sur lesquelles
ce dernier sera utilisé et surtout des ressources dont elles disposent. Il ne viendrait à l'idée de
personne (sauf des constructeurs informatiques) de livrer des programmes utilisables uniquement
sur des machines dernier cri, gâvées de RAM et équipées d'un CPU on ne peut plus puissant.
2 Récursivité
2.1 Exemple
Un algorithme récursif s'appelle lui-même. Considérons la fonction factorielle : elle associe
à un entier positif n le nombre n! = 1:2: : : : :(n ¡ 1):n.
Algorithme 2.1.1 Problème : Calcul de n! étant donné n.
Factorielle-rec(n)
si n = 0 ou n = 1, alors :
renvoyer 1
sinon :
renvoyer n:Factorielle-rec(n ¡ 1)
Ici, pour calculer n!, on calcule n:(n ¡ 1)!. Le calcul de (n ¡ 1)! est le même que celui de n!,
seules les données ont changées. Comme elles diminuent à chaque fois et que l'on dispose des
conditions initiales 1! = 1 et 0! = 1 (par dénition), l'algorithme termine évidemment. Notez
que ce type d'algorithme se décompose en deux phases : une phase descendante pour déterminer
chacun des termes à évaluer puis une remontée pour assembler ces résultats. La phase de
descente s'arrête parce que l'on dispose d'une condition d'arrêt.
Cet exemple est particulièrement simple et on ne voit guère où peut apparaître un quelconque
problème. En fait, il est très lent du fait qu'il nécessite n appels à Factorielle-rec et 2n tests. De
14 2. Récursivité
plus, il demande beaucoup de mémoire. Souvenons-nous que chaque appel de fonction demande
de créer une zone dans la pile et d'y enregistrer diérentes valeurs. En eet, après avoir eectué
tous les appels pour arriver à la condition d'arrêt, il faut renvoyer les diérents résultats pour
chacun des appels. Il y a donc une phase de descente puis une phase de remontée consistant
essentiellement à vider la pile.
2.2 Contre exemple
Exemple 2.2.1 Soit la fonction d'Ackermann A : N £ N 7! N dénie par les relations suivantes
:
A(m; n) = A(m ¡ 1;A(m; n ¡ 1)) si m > 0 et n > 0,
A(m; 0) = A(m ¡ 1; 1) si m > 0,
A(0; n) = n + 1 si n > 0.
Exercice 2.2.2 Se convaincre que cette fonction est parfaitement dénie.
Trivialement, A(0; 1) = 2. Que vaut A(1; 1) ? A(1; 1) = A(0;A(1; 0)) = A(0;A(0; 1)) = 2, ce qui
a demandé quatre appels de fonctions, 6 tests. Hum. . . que vaut A(5; 1) ? On démontre et nous
admettrons que :
A(0; n) = n + 1;
A(1; n) = n + 2;
A(2; n) = 2n;
A(3; n) = 2n;
A(4; n) = 22
:::2
| {z }
n
On a A(5; 1) = A(4;A(5; 0)) or A(5; 0) = A(4; 1) = 2222
= 65536 donc :
A(5; 1) = A(4; 65536) = 22
:::2
| {z }
65536
Finalement, A(5; 1) est énormément plus grand que le nombre d'atomes de l'Univers ( seulement
1080). Le lecteur sceptique pourra tenter d'exécuter ack.c (cf. gure 3) non sans oublier
que sa machine fonctionne en arithmétique entière modulo 232 (voire 264).
Exercice 2.2.3 Pourquoi A(5; 1) ne peut-il pas être calculé sur un ordinateur ?
Exercice 2.2.4 Écrire l'algorithme de calcul de A(4; n).
Remarque 2.2.5 Ces algorithmes récursifs sont mauvais du fait, on l'a dit, du coût des appels
de fonctions. En eet, lorsqu'un programme appelle une fonction, cela nécessite de nombreux
accès à la mémoire (qui est très lente par rapport au processeur) pour y enregistrer entre autres
les variables et l'adresse de retour de la fonction. Il faut voir l'espace mémoire du programme
comme une pile. À chaque appel de fonction, on empile dessus. Pour obtenir le résultat, il faut
donc dépiler. La machine doit donc empiler un certain nombre de fois, puis dépiler autant de
2.3 - Ranements 15
#include <stdlib.h>
#include <limits.h>
#include <stdio.h>
long compteur;
unsigned long
ack (unsigned long m, unsigned long n) {
compteur++;
if (0 == m) {
return n + 1;
} else if (0 == n) {
return ack (m - 1, 1);
} else {
return ack (m - 1, ack (m, n - 1));
}
}
int
main (int argc, char *argv[]) {
unsigned long i, j;
i = strtoul (argv[1], (char**)NULL, 10);
j = strtoul (argv[2], (char**)NULL, 10);
compteur = 0;
printf ("A(%u,%u) = %u\n", i, j, ack (i, j));
printf ("Appels a ack() : %u\n", compteur);
exit(EXIT_SUCCESS);
}
Fig. 3 Implémentation en C de la fonction d'Ackermann.
fois. On se méera comme de la peste des fonctions qui s'appellent plusieurs fois elles-mêmes
(ici 2).
Remarque 2.2.6 La terminaison d'un algorithme récursif n'a rien de triviale. Pour vous en
convaincre, lisez cette démonstration de Robert Cori et Jean-Michel Lévy : http://www.enseignement.
polytechnique.fr/informatique/TC/polycopie-1.6/main006.html#toc5.
2.3 Ranements
Voici une manière bien meilleure d'implémenter la fonction factorielle :
Algorithme 2.3.1
16 3. Structuration des données
Factorielle-iter(n)
1 i à 1, m à 1.
2 si n = 0 ou n = 1, aller en [4].
3 i à i + 1, m à m:i.
4 si i < n aller en [3]. Sinon renvoyer m.
Nous utiliserons désormais la forme suivante, plus proche des langages de programmation actuels
:
Factorielle-iter(n)
m = 1
Si n 6= 0 et n 6= 1, alors :
Pour i = 2 jusqu'à i = n, faire :
m = m:i
renvoyer m
Certains algorithmes récursifs sont pourtant bons. Il s'agit des cas où la phase de remontée
est inutile. Ces cas apparaissent quand l'appel récursif est l'instruction nale d'une fonction et
si le résultat n'est terme d'aucune expression. On dit que tout appel est récursif terminal. Soit la
fonction : Á : N£N 7! N avec Á(n;m) = m si n = 0 ou n = 1 et Á(n;m) = Á(n¡1;nm) sinon.
La relation : Á(n; 1) = n! est évidente et permet par l'entremise de Á une récursion terminale
bien plus ecace.
Exercice 2.3.2 Se convaincre du gain par rapport à Factorielle-iter. Écrire au besoin l'algorithme
détaillé. Que vaut Á(5; 1) ?
3 Structuration des données
On a vu que la manière de représenter les données (en machine ou dans l'abstrait) inue sur
l'algorithme. Nous allons maintenant nous attacher à étudier quelques structures de données
classiques. Durant tout ce paragraphe, il faut garder à l'esprit que pour chacune des structures
suivantes, il faudra savoir créer une structure vide puis y insérer des éléments, en eacer,
en déplacer, etc. Selon les structures, ces opérations n'auront pas le même coût en terme de
temps de calcul et d'espace mémoire. Souvent, l'implémentation de ces opérations dépendra de
l'environnement de programmation (langage, système).
3.1 Tableaux
Un tableau est une suite indexée de données de même type9, stockée de manière contigüe
en mémoire. Par exemple, on rencontrera souvent des tableaux de chaînes de caractères et des
tableaux d'entiers. C'est un type simple que l'on utilise souvent et il tient plus de l'outil de base
que de la structure de données avancée.
Remarque 3.1.1 Malheureusement (heureusement ?), les langages dièrent aussi me faut-il
m'arrêter un instant sur certaines spécicités des langages.
9La notion de type est évidente : les données sont soient des entiers, soient des caractères, etc.
3.2 - Listes 17
Certains langages de programmation n'orent pas de type chaîne de caractères. Ainsi, en
C, on utilise un tableau de caractères pour représenter une chaîne tandis qu'en Pascal on
dispose du type string, en Java des objets String, etc.
Selon le langage utilisé on peut ou non redimensionner à la volée un tableau au cours de
l'exécution d'un programme. Il se peut donc que l'on doive déterminer à l'avance (lors de
l'écriture du programme) de combien de mémoire on aura besoin.
Selon les langages, les tableaux commencent à 0 (C, C++, Java, Perl) ou à 1 (Pascal,
Fortran). Ici, ils commenceront à 0.
Remarque 3.1.2 Lorsque l'on déclare un tableau, il faut indiquer sa taille. Certains langages
permettent de redimensionner à la volée un tableau (realloc() en C) mais ce n'est pas le
cas général. Une idée qui ne marche pas trop mal est d'estimer ses besoins au plus juste (ie. 2
éléments) dans un premier temps quitte à créer à chaque fois que le besoin s'en fait sentir un
tableau de taille double pour y recopier les données du précédent. Cette opération est coûteuse
en temps de calcul (on se souvient que les accès à la mémoire sont lents) et en quantité de
mémoire mais demeure à la fois simple et pas trop mauvaise statistiquement10 mais évite de
trop nombreuses recopies. Évidemment, il faut libérer le vieux tableau à chaque fois, sans quoi
la consommation mémoire devient gargantuesque.
Exercice 3.1.3 Écrire le algorithme Add-tab qui ajoute un élément e dans un tableau nontri
é T, en utilisant la méthode proposée dans la remarque 3.1.2. Soit n le plus petit entier
vériant : lenght(T) · 2n. Que se passe-t-il lorsque l'on ne libère pas la mémoire des tableaux
intermédiaires au fur et à mesure que l'on ajoute des éléments ? Quelle place mémoire mobiliset-
on ?
Si l'on veut déterminer si un élément est présent ou non dans tableau, soit on sait que le
tableau n'est pas trié auquel cas on en est réduit à le parcourir séquentiellement.
Exercice 3.1.4 Écrire un algorithme (déterministe) récursif pour trouver un élément dans un
tableau trié, opérant en O(log n).
3.2 Listes
Une liste s'apparente à un tableau. Outre une donnée, un élément d'une liste contient aussi
l'adresse de son successeur pour les listes simplement chaînées,
les adresses de son successeur et de son prédécesseur pour les listes doublement chaînées.
Enn, on pourra rencontrer des listes circulaires. Elles sont construites comme des listes simplement
chaînées mais le dernier élément pointe sur le premier. Ces listes permettent de
réduire le temps de parcours d'une liste.
Remarque 3.2.1 Le lecteur attentif aura déjà noté que les listes simplement chaînées peuvent
nécéssiter plus d'opérations lors de la recherche d'un élément que les autres types de listes mais
moins d'instructions pour insérer ou supprimer un élément.
10Cette remarque est valable pour des manipulations de maillages en deux et trois dimensions. Je ne sais pas
ce qu'elle donne statistiquement dans le cas général.
18 3. Structuration des données
Ici, les données sont allouées dynamiquement : on initialise la liste puis on insère des éléments
un à un. Les éléments étant éparpillés dans la mémoire, il faut savoir au moins où se trouve
l'élément suivant. Si l'on perd l'adresse d'un élément, on perd la n de la liste. . . Évidemment,
ce type de structure de données nécéssite de pouvoir gérer la mémoire à sa guise, ce que tous
les langages ne permettent pas.
Remarque 3.2.2 Le lecteur attentif se demande comment on stocke une adresse. Le plus
souvent par un pointeur. Il s'agit d'un type de données particulier qui contient l'adresse d'un
mot mémoire. La gestion de ce type de données est toujours délicate ; elle demande toujours
soin et rigueur, parfois beaucoup d'expertise.
Dans le cadre des listes simplement chaînées, on a besoin de marquer la n d'une liste et
dans tous les cas, il faudra que l'on sache initialiser correctement une liste. On utilise alors le
pointeur nul, sa représentation dépend du langage : par exemple en C et C++, sa valeur est
NULL, en Pascal NIL, en Java null.
Remarque 3.2.3 Comment procéder sans pointeurs ?
Sous les yeux du public ébahi, je vais montrer comment utiliser astucieusement des tableaux
et leurs indices. Imaginons la liste doublement chaînée suivante : f5; 1; 4; 7g. On a d'une part :
5 ! 1, 1 ! 4, 4 ! 7, 7 ! ¡1 et d'autre part : 7 ! 4, 4 ! 1, 1 ! 5. Considérons trois tableaux
de même taille, le premier contient les données, le second les pointeurs suivants et le dernier les
pointeurs précédents, soit :
elem succ prec
0 5 1 ¡1
1 1 4 5
2 4 7 1
3 7 ¡1 4
Ici, on a représenté le pointeur nul par ¡1. Une autre méthode consiste à n'utiliser qu'un
unique tableau. On représente alors la valeur et les deux pointeurs par des cases contigües :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
tab 7 15 ¡1 5 ¡1 9 £ £ £ 1 3 15 £ £ £ 4 9 0
Le premier élément est tab[3] = 5, le dernier tab[0] = 7. Le suivant de tab[3] = 5 est
tab[tab[5]] = tab[9] = 1 tandis que le précédent est tab[4] = ¡1.
Exercice 3.2.4 Étant donné des fonctions d'allocation Malloc (prend en argument une taille
de données et renvoie un pointeur sur la zone allouée, NULL en cas d'erreur) de libération Free
(prend en argument un pointeur sur une zone allouée), écrire les algorithmes :
New-lst qui crée une liste simplement chaînée vide,
Dele-lst qui détruit une liste simplement chaînée vide,
Add-lst-item qui ajoute un élément e dans une liste non-triée,
Dele-lst-item qui supprime un élément e d'une liste,
Get-lst-next qui renvoie l'élément suivant d'une liste.
Reprendre ces algorithmes avec les méthodes indiquées dans les remarques 3.1.2 et 3.2.3.
3.3 Arbres
C'est une structure fondamentale, largement utilisée en informatique. Les arbres informatiques
sont particuliers : leur racine est placée en haut et ils poussent vers le bas. Pour le reste,
3.3 - Arbres 19
ils sont comme les vrais : ils ont des n÷uds et des feuilles. Ici, le facteur de classement est la
hiérarchie. Chaque élément est appelé noeud. Il en est un particulier, placé au sommet de la
hiérarchie : la racine. Les n÷uds placés immédiatement dessous dans la hiérarchie sont les ls
de la racine, lesquels ont pour père ladite racine. Ces ls ont leurs propres ls et ainsi de suite.
Les n÷uds sans descendance sont aussi appelés feuilles. On dénit la profondeur d'un n÷ud
comme étant le nombre de n÷uds (hormis lui-même) le séparant de la racine.
Un n÷ud dans un arbre est, en général, représenté par l'élément lui-même et un tableau de
pointeurs, pour stocker un pointeur vers le père, un autre vers le ls gauche et un dernier vers
le frère droit.
Dans la suite de ce paragraphe, je ne considèrerai plus que des arbres binaires (chaque n÷ud
a au plus deux ls). Plutôt que le frère droit, on stockera donc l'adresse du ls droit.
Exercice 3.3.1 Imaginons un arbre binaire dont le dernier niveau est plein ; soit n le nombre
de feuilles. Que dire de n ? Combien l'arbre a-t-il de n÷uds ? Quelle est sa hauteur (profondeur
maximale d'une feuille) ?
3.3.1 Parcours d'un arbre
Il y a quatre manières de parcourir un arbre. La première est dite parcours par niveaux et
consiste à explorer un à un tous les n÷uds de même profondeur, de gauche à droite. Les trois
autres sont dénis récursivement sur l'arbre lui-même :
parcours préxe : on parcoure la racine, puis le sous-arbre de gauche et enn le sous-arbre
de droite ;
parcours inxe : on parcoure le sous-arbre de gauche, puis le n÷ud racine et enn le sousarbre
de droite ;
parcours postxe : on parcoure le sous-arbre de gauche, puis celui de droite et enn la racine.
3.3.2 Arbres de recherche
Pour faire une recherche ecace dans un arbre, il faut des informations précises sur la
hiérarchie utilisée. Dans un arbre de recherche, on utilise une relation d'ordre (ordre numérique,
alphabétique, lexicographique, etc.). Quand on rencontre un n÷ud supérieur, on suit le ls
gauche et pour un n÷ud inférieur, le ls droit. Évidemment, il faut avoir enregistré les n÷uds
de sorte que cette hiérarchie soit respectée (ou il faut trier l'arbre, à suivre. . .).
Remarque 3.3.2 On note que la recherche dans un arbre est tributaire du nombre de n÷uds
mais aussi et surtout de sa hauteur.
3.3.3 Des arbres particuliers : les tas
Il s'agit d'arbres de recherche triés de sorte que le plus grand élément soit aisément accessible.
Ce type d'arbres,
est tel que chaque n÷ud a une valeur inférieure à celle de son père,
20 3. Structuration des données
est équilibré à gauche.
On les stocke en général dans un tableau, disons T, dans le même ordre que lors d'un parcours
par niveaux. Autrement dit T[i] a pour ls gauche T[2i+1], pour ls droit T[2i+2] et pour père
T[bi¡1
2 c].
Exercice 3.3.3 Écrire les algorithmes Read-heap-pre (resp. Read-heap-in et Read-hep-suf) qui
parcoure un tas par parcours préxe (resp. inxe, suxe). Écrire un algorithme Read-heap-lev
qui parcoure un tas par niveau.
Ici, la structure est assez complexe à préserver. Voici comment arranger un arbre en tas.
Dans un premier temps, il faut, étant donné un tableau T et un indice i (tels que le sous-arbre
Tg[i] (resp. Td[i]) ayant pour racine le ls gauche (resp. droit) de T[i] soit un tas) faire en sorte
que le sous-arbre de T, de racine T[i], soit un tas.
Algorithme 3.3.4
Entasser(T, i)
g à Tg[i]
d à Td[i]
Si g · Length(T) et T[g] > T[i], alors :
max à g
sinon :
max à i
Si d · Length(T) et T[d] > T[max], alors :
max à r
Si max 6= i, alors :
T[i] $ T[max]
Entasser(T,max)
Exercice 3.3.5 Quel est le temps de calcul requis par Entasser pour traiter n éléments ?
Pour construire un tas à partir d'un tableau, il ne reste plus qu'à trier tout le tableau :
Algorithme 3.3.6
Make-tas(T)
Pour i = b(Length(T)¡1)
2 c jusqu'à i = 0, faire :
Entasser(T, i)
Exercice 3.3.7 Quel est le temps de calcul requis par Make-tas pour traiter n éléments ?
Enn, insérons un élément e dans un tas :
Algorithme 3.3.8
Ins-tas(T,e)
Length(T) Ã Length(T) + 1
i à Length(T)
Tant que i > 0 et T[bi¡1
2 c] < e, faire :
T[i] Ã T[bi¡1
2 c]
i à bi¡1
2 c
Exercice 3.3.9 Quel est le temps de calcul requis par Ins-tas pour traiter n éléments ?
3.4 - Hachages 21
3.4 Hachages
Le principe d'un hachage est de pouvoir accéder à n'importe quel élément d'une table en
temps constant (ie. en O(1)), y compris si ce dernier se trouve à la n. Cette structure permettra
des recherches et des tris très ecaces. Elle généralise la notion de tableau et utilise des listes
chaînées.
Pour cela, on se donne des clefs et une fonction qui fait correspondre à chaque clef un entier.
Cet entier sera le code de hachage de la clef et il est calculé à l'aide de la fonction de hachage.
Le type des clefs est indiérent mais la fonction doit toujours renvoyer un entier (qui est un
indice dans un tableau).
Remarque 3.4.1 Ce type de structures de données est tellement pratique que certains langages
de programmation, comme Perl ou Java, fournissent un type de données et/ou des outils pour
les manipuler plus aisément, sans avoir à réinventer la roue à chaque fois.
Exemple 3.4.2 Considérons l'alphabet § = fa; b; : : : ; zg et donnons-nous plusieurs mots :
fonction, table, hachage et tri. Considérons la fonction a : § 7! f0; : : : ; 25g qui associe à
l'initiale son ordre alphabétique. On choisit la fonction de hachage ´ : §¤ 7! f0; : : : ; 25g dénie
par : ´(¾) = a(¾0). Ainsi, fonction aura pour code 5, hachage 7, table et tri 19 ; on dit que
table et tri entrent en collision.
Le choix d'une fonction de hachage doit donc minimiser les collisions. Pour cela, il vaut
mieux choisir un espace de clefs de taille comparable au nombre d'éléments. Lorsqu'il n'y a
aucune collision possible, on dit que la table est à adressage direct mais c'est dicile dans la
pratique, pour des raisons évidentes d'espace mémoire.
Remarque 3.4.3 La fonction de l'exemple 3.4.2 est mauvaise : en eet, chacun sait que les
mots français commençant par un c sont très nombreux, tandis que ceux ayant un z à l'initiale
sont rares. Elle ne distribuera donc pas les mots de manière uniforme sur l'espace des clefs.
3.4.1 Où l'on retrouve les listes chaînées
On stocke les éléments dans un tableau de listes chaînées. Chaque case du tableau est appel
é conteneur, c'est une liste chaînée d'éléments à stocker. L'indice dans le tableau correspond
au code de hachage. La recherche de la position d'un élément nécessite donc le calcul de son
code, puis le parcours du conteneur. Si un code est sujet à un grand nombre de collisions, il y
aura beaucoup d'éléments dans la liste et le parcours de cette dernière prendra du temps. On
cherche donc à distribuer uniformément les éléments dans les conteneurs, de sorte qu'ils soient
tous de taille comparable et raisonnable. Évidemment, s'il y a peu de conteneurs et beaucoup
d'éléments, les listes sont longues.
On dénit le facteur de charge par ' = e=c où e est le nombre d'éléments et c le nombre de
conteneurs où les éléments peuvent être distribués. Il s'agit en fait du nombre moyen d'éléments
par conteneur. Comme de bien entendu, on ne parviendra que rarement à une distribution uniforme
dans les conteneurs et ce facteur de charge n'est qu'une moyenne, aussi le choix d'une
22 4. Divers algorithmes de tri
fonction de hachage est-il fondamental pour approcher l'uniformité.
Dans la littérature, toutes les fonctions de hachages prennent des entiers pour argument ; en
eet, il est facile de se ramener à ce cas et le traitement d'un entier est simple. Par exemple, si l'on
a des chaînes de caractères à manipuler, l'usage du code ASCII ou de l'ordre alphabétique sera
probablement la solution. Quant aux fonctions de hachage proprement dites, elles s'inspirent
des PRNG11 uniformes classiques basées sur les congruences. Ainsi, une fonction classique est
´(c) ´ c mod m où m est un entier premier assez éloigné d'une puissance de 2.
3.4.2 Tables de hachages à adressage ouvert
Il est dicile de redimensionner à la volée un tableau, de part sa nature statique. Dans
quelques cas il peut être indispensable d'avoir à sa disposition une table de taille xe. Il n'est
alors plus question de liste chaînée ni de conteneur et on est contraint à stocker les éléments à
même un tableau. On a alors un sérieux problème avec les collisions. On va donc utiliser une
fonction de hachage donnant un facteur de charge ' < 1. On note dores et déjà que cela implique
une consommation de mémoire importante d'autant plus que certaines cases du tableau seront
vides.
3.5 Piles & les
Une pile permet de traiter les données d'une source (votre programme, un autre, un chier,
etc.) dans l'ordre LIFO (Last In, First Out ou dernier arrivé, premier parti ). Une le permet
de traiter les données d'une source dans l'ordre FIFO (First In, First Out, autrement dit dans
l'ordre où les données ont été transmises). On peut utiliser des listes simplement chaînées ou
tout bêtement des tableaux pour représenter ces structures.
4 Divers algorithmes de tri
Il est un algorithme que les Shadocks n'auraient pas renié : le bogo-tri. Prenez un jeu de
cartes et regardez s'il est trié. S'il ne l'est pas, jettez le par terre et recommencez. La probabilité
de le ramasser trié approche de un à mesure que le temps de calcul approche de cinq fois l'âge
de l'Univers, aussi conviendrez vous que le temps de calcul est inacceptable. Notez au passage
que ce n'est pas un algorithme au sens de la dénition 1.1.1.
4.1 Tri par insertion
C'est un algorithme assez bon sur de petits ensembles de données. Il s'agit d'un tri sur place
autrement dit, on ne manipule qu'une seule structure. Il formalise la manière dont un joueur
de cartes trie une donne : il prend un tas de cartes en vrac et, de gauche à droite, les range par
ordre croissant.
Exercice 4.1.1 Quel est l'intérêt d'un tri sur place ?
11Pseudo-Random Number Generator, cf. A.1 page 31.
4.2 - Tri bulle 23
Algorithme 4.1.2
Tri-insert(T)
Pour j à 1; : : : ; length(T) ¡ 1, faire :
temp à T[j]
i à j ¡ 1
Tant que i > 0 et T[i] > temp, faire :
T[i + 1] Ã T[i]
i à i ¡ 1
T[i + 1] Ã temp
Dans la boucle sur j, on insère T[j] dans le tableau, trié entre 0 et j¡1. La variable temp permet
de ne pas perdre la valeur que l'on échange.
Remarque 4.1.3 Échanger deux valeurs
Ça peut paraître trivial de le dire mais je vous rappelle que pour échanger i et j, ce que j'ai noté
jusqu'ici i $ j, les instructions i à j, j à i ne sauraient convenir. Quelque chose du genre :
temp à i, i à j, j à temp donnera de biens meilleurs résultats ;-)
Exercice 4.1.4 Montrer que le tri par insertion s'exécute en O(n2) où n = Length(T).
4.2 Tri bulle
Il s'agit d'un autre algorithme inecace en O(n2). Il consiste à échanger deux à deux les
éléments voisins pour les classer. Le nom de cet algorithme rappelle des bulles remontant à la
surface d'un verre d'une quelconque boisson à base de houblon ou de malt.
Exercice 4.2.1 Écrire l'algorithme du tri bulle. Fonctionne-t-il sur place ?
4.3 Tri par tas ou heapsort
On se donne un tableau T que l'on veut trier. On peut utiliser une structure de tas comme
on va le voir. On commence par transformer le tableau en tas. On sait alors que le plus grand
élément est T[0] que l'on échange avec le dernier et l'on décrémente la taille du tableau en
s'assurant que c'est encore en tas ; en itérant, le tour est joué :
Algorithme 4.3.1
Tri-tas(T)
Make-Tas(T)
Pour i = Length(T) jusqu'à i = 1, faire :
T[0] $ T[i]
Length(T) Ã Length(T) ¡ 1
Entasser(T)
Exercice 4.3.2 Étant donné le calcul de la compléxité de Entasser (cf. l'algortihme 3.3.4, page
20) et de Make-tas (cf. l'algortihme 3.3.6, page 20), évaluer le temps de calcul de cet algorithme.
Fonctionne-t-il sur place ?
24 4. Divers algorithmes de tri
4.4 Tri par fusion
Ce type de tri s'applique aux tableaux. Le tri par fusion est le prototype des algorithmes de
type diviser pour régner .
Remarque 4.4.1 Diviser pour régner
Un algorithme diviser pour régner est récursif. Il découpe le problème initial en sousprobl
èmes similaires mais plus petits ( diviser ), résoud ces sous-problèmes ( régner ) puis
combine les résultats pour obtenir la solution cherchée ( combiner ).
Algorithme 4.4.2
Tri-fusion(T,i,j)
Si i < j, alors :
k à bi+j
2 c
Tri-fusion(T, i, k)
Tri-fusion(T, k + 1, j)
Fusion(T, i, j, k)
où Fusion est laissé à la sagacité du lecteur. On démontre par un calcul assez simple que cet
algorithme est en O(n log n).
Exercice 4.4.3 Écrire un algorithme Fusion qui, étant donné un tableau T, tel que T[i; : : : ; k]
et T[k +1; : : : ; j] avec i · k < j soient triés, fusionne ces deux sous-tableaux en un tableau trié
T[i; : : : ; j]. Fusion devrait être en O(j ¡ i + 1).
Exercice 4.4.4 Comment trier T avec Tri-fusion ? Fonctionne-t-il sur place ?
4.5 Tri rapide ou quicksort
Il est dû à C.A.R. Hoare (1960). Il n'est pas très bon dans le pire des cas (O(n2)), mais il
s'avère souvent le meilleur dans la pratique. C'est encore un algorithme diviser pour régner .
Soit un sous-tableau non-vide T[i; : : : ; j]. Le principe est :
diviser : de partitionner T[i; : : : ; j] en deux sous-tableaux T[i; : : : ; k] et T[k + 1; : : : ; j]
non-vides et tels que chaque élément du premier soit plus petit que tout élément du
second ;
régner : de trier les deux sous-tableaux par le même algorithme ;
combiner : de. . . ne rien faire : T[i; : : : ; j] est trié puisque les deux sous-tableaux le sont !
Algorithme 4.5.1
Quicksort(T, i, j)
Si i < j, alors :
k à Pivot(T; i; j)
Quicksort(T, i, k)
Quicksort(T, k + 1, j)
Reste à calculer k. . . Pour cela, on se donne deux sous-tableaux (vides pour commencer) de
T[i; : : : ; j] (il s'agit de T[i; : : : ; n] et T[j; : : : ;m] ci-dessous) et un pivot p (on choisit T[i]). On
construit les deux sous-tableaux petit à petit de sorte que les éléments du premier soient plus
petits que le pivot et ceux du second plus grand. Au fur et à mesure, n croit et m décroît et l'on
4.6 - Tris linéaires 25
doit parfois échanger des éléments entre les deux sous-tableaux. À la n, m vaut le k recherché
ci-dessus.
Algorithme 4.5.2
Pivot(T, i, j)
p à T[i], n à i ¡ 1, m à j + 1
Tant que VRAI faire :
Répéter :
m à m ¡ 1
jusqu'à ce que T[m] · p
Répéter :
n à n + 1
jusqu'à ce que T[n] ¸ p
Si n < m, alors :
T[n] $ T[m]
Sinon :
renvoyer m
Pour améliorer cet algorithme, on le randomise : soit Alea un algorithme qui renvoie un
nombre aléatoire 0 · Alea(r) · r (cf. A.1, page 31).
Algorithme 4.5.3
Quicksort-rand(T, i, j)
Si i < j, alors :
k à Pivot-rand(T; i; j)
Quicksort-rand(T; i; k)
Quicksort-rand(T; k + 1; j)
Algorithme 4.5.4
Pivot-rand(T, i, j)
l à Alea(j ¡ i) + i
T[i] $ T[l]
Retourner Pivot(T, i, j)
Qu'apporte donc le terme choix stochastique de k ? Dans la version déterministe, il peut
arriver qu'à chaque itération on ait un sous-tableau d'un unique élément (le tableau de départ
est trié à l'envers). Pour obtenir un cas moyen, il faut supposer que les éléments sont distribués
aléatoirement. Le choix stochastique du pivot rétabli cette hypothèse. L'algorithme stochastique
est en O(n log n). On peut encore l'améliorer en prenant pour pivot p une moyenne12 entre trois
valeurs choisies au hasard, c'est la méthode de la médiane de trois .
Remarque 4.5.5 En C, on utilisera qsort(), déclaré dans <stdlib.h>.
4.6 Tris linéaires
Ces algorithmes améliorent encore la limite O(n log n) mais ne sont malheureusement pas
applicables à tout type de données. En eet, on démontre que les précedents algorithmes qui
12Moyenne arithmétique évidemment.
26 4. Divers algorithmes de tri
utilisent tous des comparaisons eectuent au pire O(n log n) opérations.
4.6.1 Tri par comptage ou par dénombrement
Soit un tableau de n entiers compris entre 0 et k ¡ 1. Pour chaque élément e, l'algorithme
détermine le nombre d'éléments qui lui sont inférieurs et place e en fonction.
Algorithme 4.6.1
Tri-compt(T, Tt, k)
Pour i = 0 jusqu'à i = k ¡ 1, faire :
Ttemp[i] Ã 0
Pour j = 0 jusqu'à j = Length(T) ¡ 1, faire :
Ttemp[T[j]] Ã Ttemp[T[j]] + 1
Pour i = 1 jusqu'à i = k ¡ 1, faire :
Ttemp[i] Ã Ttemp[i] + Ttemp[i ¡ 1]
Pour j = Length(T) ¡ 1 jusqu'à j = 0, faire :
Tt[Ttemp[T[j]]] Ã T[j]
Ttemp[T[j]] Ã Ttemp[T[j]]
Exercice 4.6.2 (Trivial) Est-ce un tri sur place ?
Dans la première boucle sur i, on initialise le tableau temporaire Ttemp. Puis, on comptabilise
dans Ttemp[i] le nombre d'éléments égaux à i (première boucle sur j). Dans la boucle suivante
(sur i), on comptabilise maintenant les éléments inférieurs ou égaux à i dans Ttemp[i]. Enn,
il ne reste plus qu'à placer les éléments dans Tt, qui sera trié quand on aura ni. T[i] va dans
Tt[Ttemp[T[i]]] (car il y a alors Ttemp[T[i]] éléments inférieurs ou égaux à i). Pour traîter le cas
où tous les éléments ne sont pas distincts, on décrémente Ttemp[i].
Exercice 4.6.3 (Trivial) Combien d'opérations faut-il pour trier un tableau de taille donnée ?
Quel est l'espace mémoire requis ?
Remarque 4.6.4 L'intérêt de ce tri est que l'on ne fait aucune comparaison. Par contre, les
hypthèses sur le type de données triées sont très contraignantes mais c'est à ce prix que l'on a
réduit le nombre d'opérations. Ce sera toujours le cas avec les tris linéaires.
Remarque 4.6.5 Stabilité du tri par comptage Soient deux éléments égaux dans le tableau
d'entrée T. Si l'on fait bien attention, ils apparraissent dans Tt dans le même ordre que dans T.
Si la dernière boucle est croissante (Pour j = 0 jusqu'à j = Length(T) ¡ 1. . .), alors l'ordre est
inversé.
4.6.2 Tri par base
Le tri par base est un héritage des trieuses de cartes perforées d'après Cormen et al. (cf.
[CLR94], paragraphe 9.3, page 174). On considère ici encore des entiers à c chires stockés dans
un tableau T. On se donne une base d < c et on considère les entiers du tableau comme des
nombres exprimés dans la base d.
27
5 Recherche de motifs
On présente ici les techniques élémentaires de recherche de motifs. On pourra poursuivre
par l'étude de l'annexe ??, page ?? qui développe des méthodes beaucoup plus abouties et bien
moins coûteuses.
On se souvient que l'on appelle alphabet un ensemble § ni non vide. Ses éléments s 2 §
sont des lettres ou des caractères. On note ² le mot vide (qui ne contient aucune lettre). On
note jsj la longueur de s : c'est le nombre de lettres de s.
5.1 Première approche
Exercice 5.1.1 Écrire un algorithme Length qui prend en argument une chaîne de caractères
et renvoie sa longueur.
On veut rechercher un mot m dans un texte t13. On note jmj la longueur de m et jtj, la
longueur de jtj. On utilise la technique dite des fenêtres glissantes Il s'agit de faire glisser m le
long de t vers la droite. Il existe de nombreuses variantes. En eet, l'algorithme peut calculer
lors de chaque tentative la longueur du prochain décalage (pour réduire le nombre de tentatives)
et/ou de mémoriser certaines informations (pour réduire le nombre de tests). On fera au plus
jtj ¡ jmj tentatives.
Algorithme 5.1.2
Rech-motif-naif(m, t)
Pour i = 0 jusqu'à i = jtj ¡ jmj, faire :
j à 0.
Tant que ti+j = mj et j < jmj, faire :
j à j + 1.
Si j = jmj, alors :
répondre i.
Répondre jtj.
C'est simple mais inecace dès que t est peu long. Ici, si une tentative échoue, on décale m vers
la droite d'un cran. Lors de chaque tentative, on compare une à une chaque lettre de m avec
sa correspondante sur la largeur de la fenêtre dans t. Au pire, on exécute la première boucle
jtj ¡ jmj + 1 fois et à chaque itération, on fait jmj ¡ 1 comparaisons.
13t n'est rien de plus qu'un mot.
28 5. Recherche de motifs
Exercice 5.1.3
1. Quelle est la complexité (utilisez la notion O(n)) de Rech-motif-naif ?
2. Faire tourner Rech-motif-naif avec y = 1011010110010100101 et x = 1010.
Remarque 5.1.4 On démontre et nous admettrons que l'algorithme 5.1.2 Rech-motif-naif a
une complexité en moyenne de O(jtj ¡ jmj). Comprendre : il n'est pas si mauvais que ça dans
la pratique.
5.2 Utilisation d'un hachage
On se donne un alphabet § et des mots sur cet alphabet. On interprête ces derniers comme
des entiers représentés en base d = j§j. Pour simplier, prenons § = f0; : : : ; 9g mais ce qui suit
reste valable pour tout alphabet. On va noter ¹ la représentation décimale de m et ts celle du
sous-mot ts : : : ts+jmj¡1. Évidemment, ts = ¹ si m est un sous-mot de t à la position s.
Remarque 5.2.1 Règle de Horner
On peut écrire un polynôme P sous la forme : P(x) = a0+x(a1+x(a2+: : :+x(an¡1+xan) : : :)).
L'avantage est que le calcul de P(x0) se fera après O(n) additions et mulitplications et évite les
exponentiations.
On a que ¹ = m0+10(m1+: : :+10(mjmj¡2+10mjmj¡1) : : :) et une formule similaire donne
t0. En regardant attentivement cette formule pour ts, on note que le calcul de ts+1 se déduit de
celui de ts : en eet, ts+1 = 10(ts ¡ 10jmj¡1ts+1) + ts+jmj+1. De plus, 10jmj¡1 est une constante
que nous réutiliserons aussi n'est-il pas indispensable de la recalculer à chaque itération mais
on la stockera à l'aide d'une constante. Par quel miracle cela fonctionne-t-il ? Avec le terme
¡10jmj¡1ts+1 on fait disparaître le chire de gauche de ts, en multipliant par 10, on décale le
tout vers la gauche et en ajoutant ts+jmj+1 on remplace le 0 inséré par la multiplication par 10
par le chire suivant, ie. ts+jmj+1 ; il n'y a donc rien de divin là-dedans.
Il reste un dernier problème de taille : il se peut que ¹ et ts deviennent très grands auquel
cas, notre bel édice tombera à l'eau. En eet nos machines ont la triste particularité d'être
nies aussi ne calculent-elles que sur 32 ou 64 bits soient au mieux la possibilité de représenter
un nombre décimal de 19 chires. . . Plutôt que de se lancer dans l'arithmétique des grands
entiers qui prend un temps considérable, on va travailler modulo q où q sera choisi de telle
sorte que 10q tienne juste dans un mot machine (pour limiter les calculs nécéssaires). Dans le
cas général on a donc : ts+1 ´ q(ts ¡ hts+1) + ts+jmj+1 mod q avec h ´ 10jmj¡1 mod q.
C'est joli, mais rien ne va plus : avec cette nouvelle formule, ts ´ ¹ mod q ne signie pas
que ts = ¹. Oui, mais on sait tout de même que si ts 6´ ¹ mod q alors ts 6= ¹. On évitera donc
nombre de comparaisons inutiles mais pas toutes. Dans la pratique, on choisit q premier.
Remarque 5.2.2 Le lecteur attentif n'aura pas manqué de noter que le titre de ce paragraphe
a déjà pris tout son sel. En fait, on a repris l'algorithme Rech-motif-naif en évitant les décalages
sûrement inutiles. Il en reste quelques uns qui s'apparentent à des collisions et qu'il faut encore
traiter.
5.2 - Utilisation d'un hachage 29
Algorithme 5.2.3
Karp-Rabin(t, m, d, q)
h à djmj¡1 mod q
¹ Ã 0
¿ Ã 0
Pour i = 0 jusqu'à i = jmj, faire :
¹ Ã d¹ + mi mod q
¿ Ã d¿ + ti mod q
Pour s = 0 jusqu'à s = Length(t) ¡ Length(m), faire :
Si ¹ = ¿ , alors :
Si m0 : : :mjmj¡1 = ts : : : ts+jmj, alors :
Renvoyer s
Si s < Length(t) ¡ Length(m), alors :
¿ Ã q(¿ ¡ hts+1) + ts+jmj+1 mod q
Remarque 5.2.4 On a évité de stocker inutilement tous les ts en ne manipulant qu'une seule
variable ¿ .
L'algorithme Karp-Rabin est simple avec la construction qui précède. On commence par des
initialisations : celle de la constante h et celles des variables ¹ et ¿ . On calcule ensuite ¹ et t0
(stocké dans ¿ par la méthode de Horner rappelée à la remarque 5.2.1, page 28). Enn, on
parcoure le texte t à la recherche de possibles occurences de m, en ne vériant que si l'on a
l'égalité modulo q : ¹ = ¿ .
Exercice 5.2.5 Quelle est la complexité de Karp-Rabin ? Mézalors, n'aurait-on travaillé que
pour la gloire ?
30 6. Conclusion
6 Conclusion
6.1 Pour nir. . .
Les algorithmes sont les outils de base du programmeur. S'il les utilise intelligement, il
pourra tirer toute la puissance de sa machine. Pour reprendre l'exemple de Comer et al.14,
imaginons deux programmeurs, l'un américain riche à millions et l'autre, russe, travaillant avec
des bouts de celles. Le premier dispose d'une machine ultra-puissante à un million de MIPS15
et l'autre d'un vieux coucou peinant à un MIPS. Tous deux doivent trier un tableau d'un million
d'éléments. Le buveur de bourbon utilise un bête tri par insertion tandis que l'amateur de vodka
préfère le tri par fusion. Finalement, à l'exécution, l'américain attend 1062
1012 = 1012
1012 = 1 seconde
tandis que le russe patiente 106 log 106
106 = 6 secondes. Si maintenant ils veulent trier un tableau
d'un milliard d'éléments, l'américain a le temps d'écluser les troquets alentours : il lui faudra
1092
1012 = 1018
1012 = 106 secondes (11 jours et demi), tandis que le russe aura son résultat au bout
de 109 log 109
106 = 9000 secondes (deux heures et demi) soit quelques chopines seulement, pourtant
avec un ordinateur bien moins puissant.
6.2 Conseils bibliographiques
Pour poursuivre l'étude de l'algorithmique, on pourra se plonger dans [CLR94] pour une
solide introduction ou dans LA référence : [Knu97]16. [CHL01] ore une étude approfondie
des principaux algorithmes de manipulation de textes : index, recherches de motifs, . . . Dans
[NR2.1], la lecture du chapitre 7.1 pourra être utile pour choisir un PRNG.
On trouvera énormément de ressources sur Internet dont en particulier l'annuaire du NIST :
http://www.nist.gov/dads/ qui recense tous les algorithmes connus. De plus, sur le site personnel
de Thierry Lecroq on trouvera l'annuaire Exact string matching algorithms (avec des
animations en Java) de Thierry Lecroq et Christian Charras. On peut consulter [NR2.1] en
ligne : http://www.nr.com/. Plus généralement, on trouve des dizaines de cours, de polycopiés,
etc. sur le Web. Citons :
le cours de Jean-Jacques Lévy et Robert Cori à l'École Polytechnique :
http://www.enseignement.polytechnique.fr/informatique/TC/polycopie-1.6/,
une liste des liens divers concernants l'algorithmique, tous plus fabuleux les uns que les
autres : http://brassens.upmf-grenoble.fr/IMSS/limass/algoprog/algoref.html,
de nombreux cours d'informatique répertoriés et classés :
http://dept-info.labri.u-bordeaux.fr/dicky/EXOS/,
le serveur du SPEDAGO : http://spedago.unice.fr (apparemment éteint en ce moment).
14[CLR94], pp. 15-16.
15Millions of Instructions Per Second.
16 Je vois qu'on a sorti le vitriol !
31
A Manipulations numériques
A.1 Génération de nombres aléatoires
Le sujet est vaste et délicat, certaines applications critiques reposant sur la qualité d'aléa de
nombres générés par des machines parfaitement déterministes. Dans la majorité des langages
de programmation utilisés, on aura à sa disposition une source aléatoire uniforme (fournie par
le système et/ou le langage) que l'on aura intérêt à utiliser. Les générateurs à la fois pas trop
mauvais et simples sont des suites entières de congruences linéaires : °n+1 ´ a°n + c mod m
et on conseille en général c = 0, a = 75 et m = 231 ¡ 117 ; on utilise en général une fonction de
temps pour générer °0 qui doit évidemment être non-nul. Knuth (cf. [Knu97]) propose une
pléthore d'autres générateurs.
A.2 Nombres premiers
Le programme suivant donne les premiers nombres premiers.
/* Crible d'Erathostene
* argument : M
* resultat : fichier primes.txt contenant les nb premiers < 2*M+1
*/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define TRUE ((char)(1==1))
#define FALSE ((char)(!TRUE))
typedef char BOOL;
#define setfalse(Tab,i) Tab[i/8] |= (0x01 << (i%8)) ;
#define istrue( Tab,i) (!((Tab[i/8] >> (i%8)) &0x01))
int
main (int argc, char *argv[]) {
if (argc == 1) {
printf ("Pas d'arguments... Tchao !\n");
return EXIT_FAILURE;
} else {
unsigned long M;
BOOL *pp = 0;
M = atol (argv[1]);
pp = calloc (M/8 + 1, sizeof *pp);
17 Standard minimal de Park et Miller ; pour bien faire, il vaut mieux choisir m premier et assez loin
d'une puissance de 2.
32 A. Manipulations numériques
printf ("Memoire requise : %ld KB\n", M * sizeof (*pp)/1024);
if (!pp) {
perror ("\nMemoire insuffisante... exit(1)...\n\n");
} else {
unsigned long j, p, q, i;
FILE* file = 0;
memset (pp, 0, M / 8 + 1); /* True */
j = 0;
i = 1;
p = 3;
q = 4;
while (q <= M) {
if (istrue (pp, i)) { /* True */
j = q; /* on vire ses multiples */
while (j <= M) {
setfalse (pp, j); /* False */
j += p;
}
}
i++;
p = 2 * i + 1;
q += 2 * p - 2;
}
file = fopen("primes.txt","w");
if (file == NULL) {
fprintf(stderr,"## Erreur : impossible d'ouvrir le fichier ##\n");
return EXIT_FAILURE;
} else {
for (j = 0; j < M; j++) {
if (istrue (pp, j))
fprintf(file,"%lu\n",2*j+1);
}
}
fclose(file);
free(pp);
}
}
return EXIT_SUCCESS;
}
BIBLIOGRAPHIE 33
Bibliographie
[B&M77] Boyer R. S. & Moore J. S., (1977), A fast string-searching algorithm, Communications
of the ACM, vol. 20, n±10, pp. 762-772.
[CLR94] Cormen T., Leiserson C., Rivest R. (1994), Introduction à l'Algorithmique, Dunod,
Paris.
[CHL01] Crochemore M., Hancart C., Lecroq T. (2001), Algorithmique du texte, Vuibert,
Paris.
[Hoa61] Hoare C. A. R. (1961), Algorithm 63 (partition) and algorithm 65 (nd), Communications
of the ACM, vol. 4, n±7, pp. 321-322.
[K&R81] Karp R. M., Rabin M. O. (1981), Ecient randomized pattern matching algorithms,
Technical Report n±TR-31-81, Aiken Computation Laboratory, Harvard
University.
[K&P99] Kernighan B. W. & Pike R. (1999), The Practice of Programming, Addison Wesley,
Reading, Massachusetts.
[Knu97] Knuth D. E. (1997), The Art of Computer Programming, Addison-Wesley, Reading,
Massachusetts.
[KMP77] Knuth D. E., Morris J. H., Pratt, V. R. (1977), Fast pattern in strings, SIAM
Journal of Computing, vol. 6, n±2, pp. 323-350.
[Lou99] Loudon K. (1999), Mastering Algorithms with C, O'Reilly, Sebastopol, California.
[Meh84] Mehlhorn K. (1984), Data Structures and Ecient Algorithms, Vol. 1 : Sorting
and Searching, EATCS Monographs, Springer Verlag, Berlin.
[Pol45] Polya G. (1945), How to Solve It, Princeton University Press, Princeton, New Jersey.
[NR2.1] Press W. H., Teukolsky S. A., Vetterling W. T. & Flannery B. P. (1992),
Numerical Recipes in C, The Art of Scientic Computing, Cambridge University
Press, Cambridge.
[Seg91] Sedgewick R. (1991), Algorithmes en langage C, InterÉditions, Paris.
[Sti95] Stinson D. (1995), Cryptography, Theory and Practice, CRC Press, Boca Raton,
Florida.
[Ta01] Tanenbaum A. (2001), Architecture de l'ordinateur, Dunod, Paris.
Index
Ackermann
fonction, 14
Adressage ouvert, voir Hachage
Adresse, 12
Al Khwarizmi, 3
Algorithme, 4
complexité, 8
diviser pour régner, 24
récursif, 13
récursif terminal, 16
terminaison, 4
Alphabet, 5
Arbre, 1820
binaire, 19
de recherche, 19
parcours inxe, 19
parcours préxe, 19
parcours suxe, 19
tas, 1920
Archimède, 3
Binaire, 6
arbre, voir Arbre
Caractère, 5
Clef de hachage, voir Hachage
Code de hachage, voir Hachage
Collision, voir Hachage
Cormen, 3
Diophante d'Alexandrie, 3
État
d'une machine de Turing, 5
nal d'une machine de Turing, 5
initial d'une machine de Turing, 5
Euclide, 3
Exponentielle, 8
Facteur de charge, voir Hachage
Factorielle, 13
Feuille, 18
FIFO, voir File
File, 22
Fils, 18
Fonction
de hachage, voir Hachage
de transition
d'une machine de Turing, 5
Hachage, 20, 21
à adressage direct, 21
à adressage ouvert, 22
clef, 21
collision, 21
facteur de charge, 21
fonction, 21
Hauteur, voir Noeud
Heapsort, voir Tri
Hoare, 24
Horner
méthode, 28
Inxe
parcours, voir Arbre
Karp, 29
Lettre, 5
LIFO, voir Pile
Liste chaînée, 17
Logarithme, 9
Machine de Turing, voir Turing
Miller, 31
MIPS, 30
Mot, 5
longueur, 5
mémoire, 10
vide, 27
Neumann, voir von Neumann
N÷ud, 18
hauteur, 19
34
INDEX 35
Octet, 12
Opération élémentaire
d'une machine de Turing, 8
Park, 31
Partie entière inférieure, 7, 9
Père, 18
Pile, 12, 22
Pointeur, 12, 18
Polynôme, 8
Préxe
parcours, voir Arbre
PRNG, 22
Processus, 12
Quicksort, voir Tri
Récursion terminale, voir Algorithme
Rabin, 29
Racine, 18
Randomiser, 25
Recherche, voir Arbre
Recherche de motif, 2629
Suxe
parcours, voir Arbre
Table de hachage, voir Hachage
Tableau, 16
Tas, 12, voir Arbre
Tri, 2226
bogo, 22
bulle, 23
linéaire, 25
par base, 26
par comparaisons, 25
par comptage, 26
par dénombrement, 26
par fusion, 23
par insertion, 22
par tas, 23
rapide, 24
stable, 26
sur place, 22
Turing, 1
machine de, 5
Type, 4
von Neumann, 10
machine de, 10
proposition de, 10
Pour les autres termes anglais non répertori
és, voir http://wall.jussieu.-
fr/foldoc/ et http://www.tuxedo.
org/esr/jargon/
Pour les autres termes français non répertori
és, voir http://sysadmin.eila.-
jussieu.fr/jargon/
