Introduction aux algorithmes et leur étude
Introduction aux algorithmes et leur étude
Pierre Boudes
creative common 1
31 mars 2011
2
Al Khuwārizmi ([Link])
Chapitre 1
Introduction
3
se restreint au cas où la liste à trier sera toujours la liste des entiers de 0 à
n − 1 dans le désordre (une permutation de {0, . . . , n − 1}) alors nul besoin
de trier, il suffit de lire la taille n de la liste donnée en entrée et de rendre la
liste 0, . . . , n − 1 sans plus considérer l’entrée. Il serait incorrect de dire de
ce procédé qu’il est un algorithme de tri.
Un algorithme doit toujours terminer en un temps fini, c’est à dire en un
nombre fini d’étapes, toutes de temps fini. Contre-exemple : tri bogo (encore
dénommé tri stupide). Ce tri revient, sur un jeu de cartes, à les jeter en l’air, à
les ramasser dans un ordre quelconque puis à vérifier si les cartes sont dans
le bon ordre, et si ça n’est pas le cas, à recommencer. Cet algorithme termine
presque sûrement mais il est toujours possible qu’il ne termine jamais (de
même qu’un singe tapant à la machine alétoirement pendant suffisamment de
temps produira presque sûrement une série de pages contenant l’ensemble
de l’œuvre de Shakespeare).
En général, un algorithme est déterministe : son exécution ne dépend que
des entrées (ce n’est pas le cas du tri bogo ).
En particulier, un algorithme déterministe réalise une fonction (au sens
mathématique) : il prend une entrée et produit une sortie qui ne dépend que
de l’entrée.
Toutefois, pour une même fonction mathématique il peut y avoir plusieurs
algorithmes, parfois très différents. Il y a par exemple plusieurs algorithmes
de tri, qui réalisent tous la fonction « ordonner les éléments d’un tableau ».
Nous verrons également des algorithmes randomisés (i.e. à méthodes aléa-
toires) qui ne sont pas déterministes. Toutefois la seule part de hasard dans
l’exécution se ramènera à une modification de l’entrée sans conséquence sur
la justesse du résultat. Par exemple, un algorithme de tri randomisé désor-
donne la liste d’éléments qu’on lui donne à trier avant de se lancer dans le
tri.
4
2. La nature des algorithmes est plus mathématique que celle des pro-
grammes et la vocation d’un algorithme n’est pas forcément d’être exé-
cutée sur un ordinateur. Les humains utilisaient des algorithmes bien
avant l’ère de l’informatique et la réalisation de calculateurs mécaniques
et électroniques. En fait, les algorithmes ont été au cœur du dévelop-
pement des mathématiques (voir [CEBMP+ 94]). Pour autant, ce cours
porte sur les algorithmes pour l’informatique.
1.1.2 Histoire
Le terme algorithme provient du nom d’un mathématicien persan du IXe
siècle, Al Kwarizmi (Abou Jafar Muhammad Ibn Mūsa al-Khuwārizmi) à qui
l’ont doit aussi : l’introduction des chiffres indiens (communément appelés
chiffres arabes) ainsi que le mot algèbre (déformation du titre d’un de ses
ouvrages). Son nom a d’abord donné algorisme (via l’arabe) très courant au
moyen-âge. On raconte que la mathématicienne Lady Ada Lovelace fille de
Lord Byron (le poète) forgea la première le mot algorithme à partir d’algo-
risme. En fait il semble qu’elle n’ait fait qu’en systématiser l’usage. Elle tra-
vaillait sur ce qu’on considère comme le premier programme informatique de
l’histoire en tant qu’assistante de Charles Babbage dans son projet de réa-
lisation de machines différentielles (ancêtres de l’ordinateur) vers 1830. Le
langage informatique Ada (1980, Défense américaine) a été ainsi nommé en
hommage à la première informaticienne de l’histoire. Son portrait est aussi
sur les hologrammes des produits Microsoft.
L’utilisation des algorithmes est antérieure : les babyloniens utilisaient
déjà des algorithmes numériques (1600 av. JC).
En mathématiques le plus connu des algorithmes est certainement l’algo-
rithme d’Euclide (300 av. JC) pour calculer le pgcd de deux nombres entiers.
Un autre algorithme très connu est le crible d’Ératosthène (IIIe siècle av.
JC) qui permet de trouver la liste des nombres premiers plus petits qu’un en-
tier donné quelconque. On écrit la liste des entiers de 2 à N . (i) On sélectionne
le premier entier (2) on l’entoure d’un cercle et on barre tous ses multiples (on
avance de 2 en 2 dans la liste) sans les effacer. (ii) Lorsqu’on a atteint la fin
de la liste on recommence avec le premier entier k non cerclé et non barré :
on le cercle, puis on barre les multiples de k en progressant de k en k . (iii) On
5
recommence l’étape (ii) tant que k 2 < N . Les nombres premiers plus petits
que N et supérieurs à 1 sont les éléments non barrés de la liste.
Il y a aussi le pivot de Gauss (ou de Gauss-Jordan) qui est en fait une
méthode bien antérieure à Gauss. Un mathématicien Chinois, Liu Hui, avait
déjà publié la méthode dans un livre au IIIe siècle.
Mais la plupart des algorithmes que nous étudierons datent d’après 1945.
Date à laquelle John Von Neumann introduisit ce qui est sans doute le premier
programme de tri (un tri fusion).
1.2 Algorithmique
L’algorithmique est l’étude mathématique des algorithmes. Il s’agit notam-
ment d’étudier les problèmes que l’ont peut résoudre par des algorithmes et
de trouver les plus appropriés à la résolution de ces problèmes. Il s’agit donc
aussi de comparer les algorithmes, et de démontrer leurs propriétés.
La nécessité d’étudier les algorithmes a été guidée par le développement
de l’informatique. Ainsi l’algorithmique est une activité jeune qui s’est déve-
loppée dans la deuxième moitié du XXe siècle, principalement à partir des
années 60-70 avec le travail de Donald E. Knuth [Knu68, Knu69, Knu73]. Ac-
tuellement, un très bon livre de référence en algorithmique est le Cormen
[CLRS02].
Parmi les critères de comparaison entre algorithmes, les plus détermi-
nants d’un point de vue informatique sont certainement les consommations
en temps et en espace de calcul. Nous nous intéresserons particulièrement à
l’expression des coûts en temps et en espace à l’aide de la notation asymp-
totique qui permet de donner des ordres de grandeur indépendemment de
l’ordinateur sur lequel l’algorithme est implanté.
À côté des études de coûts, les propriétés que nous démontrerons sur les
algorithmes sont principalement la terminaison : l’algorithme termine ; et la
correction : l’algorithme résout bien le problème donné. Pour cela une notion
clé sera celle d’invariant de boucle.
6
terminaison bien entendu il faut aussi que cette propriété soit utile à quelque
chose, à la fin. La dernière étape consiste donc à établir une propriété
intéressante à partir de l’invariant, en sortie de boucle.
La notion d’invariant de boucle est à rapprocher de celle de raisonnement
par récurrence (voir exercice 20). Il s’agit d’une notion clé pour démontrer les
propriétés d’un algorithme. Souvent, la propriété invariante est étroitement
liée à l’idée même à l’origine de l’algorithme et l’invariant est construit en
fonction du but de l’algorithme, au moment de sa mise au point.
32 main(){
33 init();
34 while(1){ /* <------------- Boucle principale */
35 arbitre("Joueur"); /* Faut-il déclarer Joueur perdant ? */
36 Joueur(); /* Sinon Joueur joue. */
37 arbitre("Opposant"); /* Faut-il déclarer Opposant perdant ? */
38 Opposant(); /* Sinon Opposant joue. */
39 }
40 }
7
15 }
16 }
18 opposant(){
19 if (p == 1) q = 1; /* si p == 1 opposant gagne en un coup */
20 else if (q == 1) p = 1; /* de même si q == 1 */
21 else if ( random() % 2 ) /* Opposant choisit p ou q au hasard */
22 p == random() % (p - 1) + 1; /* croque un bout de p */
23 else q == random() % (q - 1) + 1; /* croque un bout de q */
24 }
8
26 joueur(){
27 if (p > q) p = q; /* Si la tablette n’est pas carrée */
28 else if ( q > p) q = p; /* rend un carré. */
29 else p--; /* Sinon, gagner du temps ! */
30 }
En résumé on a trouvé une propriété qui est préservée par le tour de jeu
(un invariant) et qui permet à Joueur de gagner. Ce type de raisonnement
s’applique à d’autres jeux mais trouver le bon invariant est souvent difficile.
si n = 0 alors
retourner 1; unsigned int fact(unsigned int n){
sinon if (n == 0) return 1;
retourner n × Fact(n − 1); return n * fact(n - 1);
}
9
Fonction Fact(n ) /* Fonction fact en C */
r = 1;
pour j = 1 à n faire unsigned int fact(unsigned int n){
r = r × j; int j, r = 1;
retourner r ; for (j = 1; j <= n; j++){
r = r * j;
}
return r;
}
10
1.2.3 Complexité en temps et en espace
Dans la suite nous nous intéresserons surtout au coût en temps d’un algo-
rithme et nous travaillerons moins sur le coût en espace. À cela deux raisons.
Les règles d’études du coût en espace s’appuient sur les mêmes notions
que celles pour le coût en temps, avec la particularité que si le temps va
croissant au cours de l’exécution, il n’en va pas de même de l’utilisation de
l’espace. On mesure alors le plus grand espace occupé au cours de l’exécution,
en ne comptant pas la place prise par les données en entrée. Nous appellerons
empreinte mémoire de l’algorithme cet espace.
Le coût en temps borne le coût en espace. En effet, il est réaliste d’estimer
que chaque accès à une unité de la mémoire participe du coût en temps pour
une certaine durée, minorée par une constante d. Ainsi en un temps t un
algorithme ne pourra pas occuper plus de dt espaces mémoires. Il n’aurait pas
le temps d’accéder à plus d’espaces mémoires. Le coût en espace sera donc
toujours borné par une fonction linéaire du coût en temps. En général, il sera
même bien inférieur.
Le coût en temps (ou en espace mémoire) est fonction des données four-
nies en entrée.
Il y a bien sûr des bons cas et des mauvais cas : souvent un algorithme
de tri sera plus efficace sur une liste déjà triée, par exemple. En général on
classe les données par leurs tailles : le nombre d’éléments dans la liste à trier,
le nombre de bits nécessaires pour coder l’entrée, etc.
On peut alors s’intéresser au pire cas. Pour une taille de donnée fixée,
quel est le temps maximum au bout duquel cet algorithme va rendre son ré-
sultat ? Sur quelle donnée de cette taille l’algorithme atteint-il ce maximum ?
Avoir une estimation correcte du temps mis dans le pire des cas est souvent
essentiel dans le cadre de l’intégration de l’algorithme dans un programme.
En effet, on peut rarement admettre des programmes qui de temps en temps
mettent des heures à effectuer une tâche alors qu’elle est habituellement ra-
pide.
On s’intéressera plus rarement aux études en meilleur cas, qui est comme
le pire cas mais où on prend le minimum au lieu du maximum.
Il est particulièrement utile de faire une étude en moyenne. Dans ce cas,
on travaille sur l’ensemble des données possibles Dn d’une même taille n.
Lorsque l’ensemble Dn est fini, pour chacune de ces données, d ∈ Dn , on
considère sa probabilité p(d) ainsi que le temps mis par l’algorithme t(d). Le
11
temps moyen mis par l’algorithme sur les données de taille n est alors :
X
tn = p(d) × t(d).
d∈Dn
Jusqu’ici nous avons été évasif sur la manière de mesurer le temps d’exé-
cution pour un algorithme en fonction de la taille des entrées.
Nous pourrions implanter nos algorithmes sur ordinateur et les chronomé-
trer. Il faut faire de nombreux tests sur des jeux de données importants pour
pouvoir publier des résultats utiles. Pour les tailles de donnée non testée on
extrapole ensuite les résultats. On obtient ainsi une courbe de l’évolution du
coût mesuré en fonction de la taille des donnée (courbe de la moyenne des
temps, courbe du temps en pire cas, etc.).
Si ce genre de mesure peut avoir un intérêt ce sera plutôt pour dépar-
tager plusieurs implantations de quelques algorithmes, sélectionnés aupara-
vant, pour une architecture donnée. Autrement, la mesure risque de rapide-
ment devenir obsolète à cause des changements d’architecture.
Il est beaucoup plus intéressant de faire quelques approximations per-
mettant de mener un raisonnement mathématique grâce auquel on obtient la
forme générale de cette courbe exprimée sous la forme d’une fonction ma-
thématique simple, f (N ), en la taille des données, N . On dit que la fonction
exprime la complexité (en temps ou en espace, en pire cas ou en moyenne) de
l’algorithme. On peut alors comparer les algorithmes en comparant les fonc-
tions de complexité. S’il faut vraiment optimiser, alors seulement on compare
différentes implantations.
Voyons comment on procède pour trouver une fonction de complexité et
quelles approximations sont admises.
12
[Link]
...
13
Définition 1.1. Soient f et g deux fonctions des entiers dans les réels. On dit
que f est asymptotiquement dominée par g , on note f = O(g) et on lit f est
en « grand o » de g , lorsqu’il existe une constante c1 strictement positive et
un entier n1 à partir duquel 0 ≤ f (n) ≤ c1 g(n), i.e.
Les notations asymptotiques à l’aide du signe égal, adoptées ici, sont trom-
peuses (par exemple, ce n’est pas parce que f = O(g) et h = O(g) que
f = h) mais assez répandues, il faut éviter de prendre cela pour une véritable
égalité.
Pour comprendre pourquoi cette approche est efficace le mieux est de
regarder quelques exemples.
Supposons que l’on ait affaire à plusieurs algorithmes et que leurs temps
moyens d’exécution soient respectivement exprimés par les fonctions formant
les lignes du tableau ci-dessous.
Pour fixer les idées, disons que nos algorithmes sont implantés sur un
ordinateur du début des années 70 (premiers microprocesseurs sur quatre
bits ou un octet) qui effectue mille opérations significatives par seconde (la
fréquence du processeur est meilleure, mais il faut une bonne centaine de
cycles d’horloge pour effectuer une opération significative).
Le tableau 1.1 exprime le temps d’exécution en approximation asympto-
tique de chacun de ces algorithmes en fonction de la taille des données en
entrée. L’unité 1 C correspond à un siècle (cent ans). L’unité 1 U correspond
à l’estimation courante de l’âge de l’Univers, c’est à dire 13, 7 milliards d’an-
nées.
Les écarts entre les ordres de grandeurs des temps de traitement, rappor-
tés au temps humain, sont tels qu’un facteur multiplicatif dans l’estimation du
temps d’exécution sera généralement négligeable par rapport à la fonction à
laquelle on se rapporte. Il faudrait de très grosses ou très petites constantes
multiplicatives en facteur pour que celles-ci aient une incidence dans le choix
des algorithmes. En négligeant ces facteurs, on ne perd donc que peu d’infor-
mation sur un algorithme. Les coûts réels, fonction de l’implantation, serviront
14
N 10 50 100 1 000 10 000 100 000 1 000 000
log N 3 ms 6 ms 7 ms 10 ms 13 ms 17 ms 20 ms
log2 N 11 ms 32 ms 44 ms 0, 1 s 0, 2 s 0, 3 s 0, 4 s
N 10 ms 50 ms 0, 1 s 1s 10 s 17 min 17 min
N log N 33 ms 0, 3 s 0, 7 s 10 s 2 min 28 min 6h
N (3/2) 32 ms 0, 3 s 1s 30 s 17 min 9h 12 j
N2 0, 1 s 2, 5 s 10 s 17 min 1, 2 j 4 mois 32 a
N3 1s 2 min 17 min 12 j 32 a 32 C 107 a
2N 1s 35 C 109 U
1.2.6 Optimalité
15
N 90 103 106 108 109 1012
log N 6 10 20 27 30 40
log2 N 42 0, 1 µs 0, 4 µs 0, 7 µs 0, 9 µs 1, 5 µs
N 90 1 µs 1 ms 100 ms 1s 17 min
N log N 584 9 µs 20 ms 3s 30 s 11 h
N (3/2) 854 31 µs 1s 17 min 9h 32 a
N2 8 µs 1 ms 17 min 4 mois 32 a 107 a
N3 0, 7 ms 1s 32 a 107 a 2U 109 U
2N 3U
16
Lemme 1.3. Soit A un algorithme résolvant le problème P de recherche du
maximum, soit t un tableau en entrée dont tous les éléments sont différents,
et soit imax l’indice de l’élément maximum. Alors pour tout indice i du tableau
différent de imax , l’élément t[i] est comparé au moins une fois avec un élément
plus grand au cours de l’exécution de l’algorithme.
17
Chapitre 2
Les algorithmes
élémentaires de recherche
et de tri
Le Parc des idoles de Paul Klee, façon Art en bazar, Ursus Wehrli, éditions
Milan jeunesse.
18
Si on veut trier des objets par leurs masses, on considérera par exemple
que la clé associée à un objet est son poids terrestre et on comparera les objets
à l’aide d’une balance à deux plateaux.
Dans la suite on considérera une fonction de comparaison :
(
−1 si a > b
Comparer(a, b) qui rend : 1 si a < b
0 lorsque a = b (même masse).
Un élément ne se réduit pas à sa clé, on considérera qu’il peut contenir
des données satellites (un numéro de téléphone, une adresse, etc.).
19
avec le sous-tableau des éléments de m + 1 à N − 1. On s’arrête soit sur
un élément ayant la clé recherchée et on rend son indice soit parce que le
sous-tableau que l’on est en train de considérer est vide et on rend une valeur
spéciale d’indice, disons −1, pour dire que l’élément n’est pas dans le tableau.
Dans cet algorithme, on considère la comparaison des clés comme seule
opération significative.
On représente tous les branchements conditionnels possibles au cours de
l’exécution sous la forme d’un arbre binaire. L’arbre obtenu s’appelle un arbre
de décision. Ici les tests qui donnent lieu à branchement sont les comparaisons
entre la clé de l’élément recherché et la clé d’un élément du tableau. On peut
donc représenter le test en ne notant que l’indice de l’élément du tableau dont
la clé est comparée avec la clé recherchée. Considérons le cas N = 23 −1 = 7.
L’arbre de décision est alors :
1 5
0 2 4 6
Cet arbre signifie qu’on commence par comparer la clé recherchée avec l’élé-
ment d’indice 3 (car ⌊7/2⌋ = 3). Il y a ensuite trois cas : soit on s’arrête sur
cet élément soit on continue à gauche (avec ⌊3/2⌋ = 1), soit on continue à
droite (avec l’élément d’indice ⌊3/2⌋ = 1 du sous-tableau de droite, c’est à
dire l’élément d’indice 4 + 1 dans le tableau de départ). Et ainsi de suite.
Si l’élément recherché n’est pas dans le tableau on parcourt toute une
branche de l’arbre de la racine à une feuille.
Supposons que l’on applique cet algorithme à un tableau de taille N =
2k − 1. La hauteur de l’arbre est k . Si l’élément n’est pas dans le tableau on
fait donc systématiquement k comparaisons. De même, par exemple, lorsque
l’élément est dans la dernière case du tableau. C’est le pire cas. Comme N =
2k − 1, k − 1 ≤ log N < k et on en déduit facilement que le pire cas est
en Θ(log N ) (pour N > 2, 21 log N ≤ k ≤ log N ). Ceci lorsque N est de la
forme 2k − 1.
On peut faire moins de comparaisons que dans le pire cas. Combien en
fait on en moyenne lorsque la clé recherchée est dans le tableau, en un seul
exemplaire, et que toutes les places sont équiprobables ?
Exactement :
Pk
i=1 i × 2i−1
moy(N ) =
N
20
Puisque dans un arbre binaire parfait de hauteur k il y a 2i−1 éléments de
hauteur i pour chaque i ≤ k .
On cherche une forme close pour exprimer moy(N).
Pk i−1
Pk i−1
On remarque que i=1 i × 2 est la série i=1 i × z où z = 2. On
peut commencer la sommation à l’indice 0, puisque dans ce cas le premier
Pk i ′
Pk i−1
terme est nul. En posant S(z) = i=0 z il vient S (z) = i=0 i × z .
Mais S(z) est une série géométrique de raison z donc :
z k+1 − 1
S(z) = et, par conséquent
z−1
(k + 1)z k (z − 1) − (z k+1 − 1)
S ′ (z) =
(z − 1)2
En fixant z = 2 on obtient :
k
moy(N ) = k − 1 +
N
Ceci est une formule exacte. Comme k = ⌊log N ⌋ + 1, on en déduit sans trop
de difficultés que moy(N ) = Θ(log N ) (prendre, par exemple, l’encadrement
1
2 log N ≤ moy(N ) ≤ 2 log N ).
L’étude du nombre moyen de comparaisons effectuées par une recherche
dichotomique, comme celle du pire cas, a été menée pour une taille particu-
lière de tableau : N = 2k − 1. Il est tout à fait possible de généraliser le
résultat moy(N ) = Θ(log N ) à N quelconque en remarquant que pour N tel
que 2k−1 − 1 < N < 2k − 1 la moyenne du nombre de comparaisons est entre
Ω(log(N − 1)) et O(log N ), puis en donnant une minoration de log(N − 1)
par un c × log N . De même pour le pire cas. Nous ne rentrons pas dans les
détails de cette généralisation.
En général, on pourra supposer que les fonctions de complexité sont crois-
santes et ainsi déduire des résultats généraux à partir de ceux obtenus pour
une suite infinie strictement croissante de tailles de données (ici la suite est
uk = 2k − 1).
21
que ces tris sont par comparaison : les seuls tests effectués sur les éléments
donnés en entrée sont des comparaisons.
Pour qu’un algorithme de tri soit correct, il faut qu’il satisfasse deux choses :
qu’il rende un tableau trié, et que les éléments de ce tableau trié soient exac-
tement les éléments du tableau de départ.
Stable. Il arrive fréquemment que des éléments différents aient la même clé.
Dans ce cas on dit que le tri est stable lorsque toute paire d’éléments ayant la
même clé se retrouve dans le même ordre à la fin qu’au début du tri : si a et b
ont mêmes clés et si a apparaît avant b dans le tableau de départ, alors a ap-
paraît encore avant b dans le tableau d’arrivée. On peut toujours rendre un tri
par comparaison stable, il suffit de modifier la fonction de comparaison pour
que lorsque les clés des deux éléments comparés sont égales, elle compare
l’indice des éléments dans le tableau.
22
2.3 Les principaux algorithmes de tri
Il est facile de montrer que ce tri est toujours en Θ(N 2 ) quelle que soit la
forme de l’entrée.
23
a 0 < a1 ?
oui non
a 0 < a2 ? a 1 < a2 ?
oui non oui non
a0 , a1 , a2 a0 , a2 , a1 impossible a2 , a0 , a1 a1 , a0 , a2 a3 , a2 , a0 a2 , a1 , a0 impossible
tiendra pas compte des cas d’égalité entre clés : on suppose que toutes les
clés sont différentes.
Voici, figure 2.2, l’arbre de décision du tri par sélection dans le cas où le
tableau contient trois éléments. Le tableau de départ contient les éléments
a0 , a1 et a2 (d’indices 0, 1, 2). Ce tableau est modifié au cours de l’exécution :
dans l’arbre de décision, on regarde quel élément est comparé avec quel autre
élément, non pas quel indice est comparé avec quel autre indice : ainsi si a0 se
retrouve à l’indice 1, et a2 à l’indice 2, on notera a0 < a2 le nœud de l’arbre
de décision correspondant à la comparaison entre ces deux éléments, et non
T [1] < T [2]. À chaque fois la branche de gauche correspond à la réponse oui
et la branche de droite à la réponse non.
Comme on considère tous les cas possibles, toutes les permutations pos-
sibles de l’entrée apparaissent comme une feuille de l’arbre de décision. Et
ce toujours en un seul endroit – à chaque permutation correspond une et une
seule feuille – car une permutation détermine complètement l’ordre des élé-
ments et donc le résultat des comparaisons.
Pour le tri sélection, certaines comparaisons faîtes sont inutiles : leurs ré-
sultats auraient pu être déduits des résultats des comparaisons précédentes.
Dans ces comparaisons, un des deux branchements n’est donc jamais em-
prunté, il est noté ici comme impossible.
Il arrive fréquemment que des algorithmes fassent des tests inutiles (quelle
que soit l’entrée). Ce sera encore le cas pour le tri bulle, par exemple.
L’idée du tri bulle est très naturelle. Pour tester si un tableau est trié on
compare deux à deux les éléments consécutifs T [i], T [i + 1] : on doit toujours
24
void tribulle(tableau_t *t){
int n, k, fin;
for (n = taille(t) - 1; n >= 1; n--) {
/* Les éléments d’indice > n sont à la bonne place. */
fin = 1;
for (k = 0; k < n; k++){
if ( 0 > comparer(t[k], t[k + 1]) ){ /* t[k] > t[k + 1] */
echangertab(t, k, k + 1);
fin = 0;
}
}
if (fin) break; /* Les éléments entre 0 et n - 1 sont bien ordonnés */
}
}
Figure 2.3 – Tri bulle
Mais le tri bulle est assez lent en pratique. Il s’agit d’un algorithme en
Θ(N 2 ) (pire cas et moyenne) qui est plus lent que d’autres algorithmes de
même complexité asymptotique (tri insertion, tri sélection).
Le tri bulle admet plusieurs variantes. Dans chacune de ces variantes, les
tortues trouvent leur place plus vite.
25
Tri bulle bidirectionnel
Tri gnome
Tri Shell
Le tri Shell, due à D. L. Shell (1959), et que nous ne verrons pas, peut être
considéré comme une amélioration du tri insertion.
Le tri fusion (von Neumann, 1945) est un très bon tri, sur le principe du
diviser pour régner. Mais il a le défaut de ne pas être en place et de nécessiter
une mémoire auxiliaire de la taille de la donnée. Ainsi l’empreinte mémoire du
tri fusion est de l’ordre de N , où N est la taille du tableau fourni en entrée
(attention : on ne compte pas la taille du tableau en entrée – uniquement
26
void triinsertion(tableau_t *t){
int n, k;
element_t e;
for (n = 1; n < taille(t); n++) {
/* --- Invariant: le sous-tableau entre 0 et n - 1 est trié --- */
/* Insertion du n + 1 ième élément dans ce sous-tableau trié : */
/* --1) Le n + 1 ième élément est sauvegardé dans e */
e = t[n];
/* --2) Décalage des éléments plus grands que e du sous-tableau */
k = n - 1;
while ( (k >= 0) && (0 < comparer(e, t[k]) ) ){ /* e < t[k] */
t[k + 1] = t[k];
k--;
}
/* --3) La nouvelle place de l’élément e est à l’indice k + 1 */
t[k + 1] = e;
}
}
Figure 2.4 – Tri insertion
27
de taille 2k−1 , qui est 2k − 1. On a donc la relation :
uk = 2uk−1 + 2k − 1.
vk = 2vk−1 + 2k .
28
tableau T , un indice i et une taille n, qui rend le sous-tableau de T commen-
çant à l’indice i et de longueur n, sans en faire de copie : une modification du
sous-tableau entraîne une modification du tableau T.
Partitionner un tableau de taille n coûte un temps n (on fait comme dans
l’exercice 6 sauf qu’au lieu de la couleur on utilise le résultat de la comparai-
son contre le pivot).
Il peut arriver que la partition soit complètement déséquilibrée. Suppo-
sons qu’on choisisse toujours le premier élément du tableau comme pivot.
Alors le tableau des éléments déjà triés laisse le pivot à sa place à chaque
appel, et dans ce cas, le tableau des valeurs inférieures au pivot est toujours
vide. On fera donc N appels récursifs au tri, le premier sur tout le tableau,
demandera N − 1 comparaisons pour faire le partitionnement, le deuxième
demandera N − 2, etc. Le nombre total de comparaisons est alors en Θ(N 2 ).
La profondeur de pile d’appel en N implique une utilisation de la mémoire en
Θ(N ). C’est le pire cas.
Mais on peut montrer (on ne le fera pas ici) que le tri rapide est en
moyenne en Θ(N log N ) pour le temps et en Θ(log N ) pour l’espace, lorsque
toutes les permutations possibles sont équiprobables en entrée. Comme il uti-
lise peu de mémoire, contrairement au tri fusion, cela fait de ce tri un très
bon tri, qui donne d’ailleurs de bons résultats pratiques. Il est ainsi souvent
employé.
Lorsqu’on n’est pas certain que les entrées sont équiprobables on peut
randomiser l’entrée de manière à donner la même probabilité à chaque per-
mutation. Pour cela, il suffit de changer l’ordre de la donnée en tirant au ha-
sard la place de chaque élément. En fait, plutôt que de changer l’ordre de
tous les éléments à l’avance, on peut se contenter de tirer le pivot au hasard
à chaque appel.
Voici, figure 2.5, une version en C du tri rapide randomisé.
Nous venons de voir deux tris, le tri fusion et le tri rapide, qui fonctionnent
sur le principe du diviser pour régner. Pour l’un, le tri fusion, la division est
facile mais il y a du travail pour régner (la fusion par entrelacement) et pour
l’autre c’est l’inverse, la division est plus difficile (le partitionnement) mais
régner est simple (il n’y a rien besoin de faire).
On récapitule les résultats de complexité sur les principaux algorithmes
de tri généralistes dans le tableau 2.1 (nous n’avons pas tout démontré).
Dans ce tableau, nous faisons aussi figurer le tri par tas, que nous ne
verrons qu’au prochain chapitre.
29
void trirapide (tableau_t *t){
if (taille(t) > 1) {
int k;
tableau_t *t1, *t2;
int p = 0;
/* Randomisation: on choisit le pivot au hasard */
echangertab(t,0, random()%taille(t));
/* Partition -------------------------------------------------- */
/* Invariant : pivot en 0, éléments plus petits entre 1 et p,
plus grands entre p + 1 et k - 1, indéterminés au delà. */
for (k = 1; k < taille(t); k++){
if ( 0 > comparer(t[0], t[k]) ){ /* t[0] > t[k] */
p++;
echangertab(t, p, k);
}
}
/* Range le pivot à sa place, p. ------------------------------ */
echangertab(t, 0, p);
/* Tri du sous-tableau [0..p - 1] ---------------------------- */
t1 = soustab(t, 0, p);
trirapide(t1);
/* tri du sous-tableau [p + 1..N - 1] ------------------------- */
t2 = soustab(t, p + 1, taille(t) - p - 1);
trirapide(t2);
}
}
Figure 2.5 – Tri rapide (quicksort )
30
deux des éléments du tableau en entrée.
Pour simplifier nous nous restreignons aux tableaux dont les éléments
sont tous deux à deux différents. De plus, nous identifions les tableaux qui
correspondent à une même permutation de la liste triée : ainsi, sur des en-
tiers, les entrées 11, 14, 13, 12 ou −10, 1, 20, 0 ou 100, 20000, 10000, 1000
sont considérées comme équivalentes et nous les identifions à la permutation
σ = 0, 3, 2, 1.
Enfin, on considère que toutes les permutations sont équiprobables.
a2 impossible a1 a2 a3 a4
impossible a1 a3 a4
31
Lemme 2.1. Dans un arbre binaire, si la profondeur maximale des feuilles
est k alors le nombre de feuilles est au plus 2k .
Lemme 2.3. Un arbre binaire complet équilibré qui a K feuilles est tel que
chaque feuille est de profondeur supérieure ou égale à log(K) − 1.
32
profondeur
0
p′ c n
p′ + 1 a b
p−1 n c
p a b
P − P ′ = p′ + 2p − (p − 1) − 2(p′ + 1) = p − (p′ + 1)
Théorème 2.4. La complexité en moyenne (et en pire cas) d’un tri par compa-
raison, est minorée asymptotiquement par N log N (c’est à dire en Ω(N log N )).
33
2.5.1 Tri du postier
Les lettres et colis postaux sont triés selon leurs adresses. Cette clé de tri
est très particulière. Quel que soit la quantité de courrier, il est possible de
faire un nombre borné de paquets par pays, puis de trier chaque paquet par
ville (là encore le nombre est borné), puis par arrondissement, par rue, par
numéro et enfin par nom (on simplifie). Le résultat est un tri linéaire en le
nombre de lettres : à chaque étape répartir le courrier en paquets de destina-
tion différentes se fait en temps N et il y a un nombre borné d’étapes. Ce type
de tri peut aussi s’appliquer à certaines données.
34
Deuxième partie
Structures de données,
arbres
35
Chapitre 3
Structures de données
Dans le chapitre précédant, nous avons utilisé des tableaux pour organiser
des données ensemble. Il existe beaucoup d’autres structures de données que
les tableaux qui répondent chacune à des besoins particuliers.
Une structure de données contient des données et est caractérisée par les
opérations fondamentales (ou primitives) qui permettent d’accèder à ces don-
nées 1 . L’ajout et le retrait d’un élément sont deux opérations fondamentales
que l’on retrouve dans toutes les structures données. Le test à vide, qui ré-
pond vrai lorsque la structure ne contient aucun élément, est également une
opération que l’on retrouvera dans toutes les structures de données.
D’autres primitives sont disponibles selon les structures. Par exemple dans
les tableaux, on peut accèder à un élément à partir de son rang (son indice)
pour lire ou modifier sa valeur.
Une structure abstraite de données est une structure de données pour
laquelle la manière dont les données sont organisées en mémoire et la ma-
nière dont les primitives sont programmées ne sont pas renseignés. La seule
information intéressante retenue des réalisations concrètes de ces structures
(leurs implantations) est le coût en temps ou en espace des primitives, exprimé
de manière asymptotique, c’est à dire leur complexité.
Cette complexité doit être faible : temps ou espace constant, sub-linéaire
(log), plus rarement linéaire. Autrement l’opération ne mérite pas l’appella-
tion fondamentale.
Par exemple, accéder à un élément dans un tableau à partir de son rang
se fait en temps et en espace constant. Mais l’insertion et la suppression d’un
1. Pour les informaticiens, les structures de données entrent bien évidemment tout à fait dans
le cadre de la programmation modulaire. En programmation objet, chaque structure de donnée
sera une classe et les primitives seront ses méthodes publiques.
37
élément à un rang quelconque demande, en pire cas et en moyenne, un temps
linéaire en la taille du tableau, car il faut décaler les éléments suivants.
Nous étudions dans ce chapitre trois structures de données élémentaires :
la pile, la file et la file de priorité.
Si les tableaux sont directement implantés dans les langages de program-
mation, ce n’est pas nécessairement le cas des autres structures de données.
Pour réaliser concrétement les piles et les files, il est courant d’utiliser des
listes chaînées. Ce chapitre contient donc un rappel sur les listes chaînées et
leur(s) implantation(s) en C, ainsi que les primitives qui leurs sont associées.
On peut également utiliser des tableaux pour implanter les piles et les files
(voir exercice 48).
Pour réaliser algorithmiquement, sinon concrétement, les files de priorités
nous utilisons la structure arborescente de tas (encore appelée maximier, ou
minimier). La présentation des tas étant liée à celle d’arborescence, les tas
sont traités au chapitre suivant.
Ces trois structures de données, pile, file, file de priorité, ne fournissent
pas d’opération fondamentale pour la recherche d’un élément quelconque.
Dans les implantations courantes de ces structures de données, l’opération
de recherche serait en moyenne en Θ(N ). Dans le chapitre suivant, nous ver-
rons des structures de données (arbres de recherche et arbre rouge noir) qui
optimisent la recherche d’un élément quelconque (Θ(log N ) comme pour les
tableaux triés) tout en préservant une insertion et une suppression en temps
raisonnable ( Θ(log N ), contrairement aux tableaux triés).
Comme pour les tableaux, pour chacune des trois structures de données,
pile, file, file de priorité, on peut ajouter sans difficulté une opération Taille(S)
en Θ(1) qui renvoie le nombre d’élément contenus dans la structure de don-
née S (il suffit de maintenir un compteur du nombre d’éléments à chaque
ajout/retrait). Au niveau concret, on peut également compter comme primitive
une opération de création (un constructeur) d’une nouvelle structure vide, en
O(1).
n = 0 | Sn
38
La notation Sn peut être vue comme l’application de la fonction successeur :
S : n 7→ n + 1 à son argument, où les parenthèses S(n) ont été omises (pour
faciliter la lecture). Ainsi SSS0 désigne l’entier 3.
De même si A est un ensemble d’éléments a, les listes finies d’éléments de
A (ou mots sur A), dont l’ensemble est noté A∗ , sont les termes du langage :
l := ε | a :: l
3.1.1 Piles
En anglais : stacks
Une pile est une structure de donnée que l’on rencontre très souvent dans
la vie de tous les jours : pile de papiers, pile d’assiettes (ou si on est program-
meur, pile d’exécution). Sa principale caractéristique est que l’élément que
l’on retire est toujours le dernier élément ajouté et qui n’a pas encore été re-
tiré, que nous appellerons sommet de la pile. On parle de structure LIFO (last
in first out ). Les opérations fondamentales sont :
– le test à vide, EstVide(P ),
– l’ajout d’un élément (appelé empilement), Empiler(e, P ),
– le retrait (dépilement), Dépiler(P ), qui retire le dernier élément empilé
non encore retiré et le renvoie,
– et la lecture de l’élément au sommet de la pile, Sommet(P ), qui rend la
même valeur que Dépiler(P ) sans modifier la pile.
Ces quatres opérations peuvent être réalisées de manière à ce que leurs
temps d’exécution soit constant, c’est à dire en Θ(1) et avec en espace constant.
En termes plus mathématiques, les piles peuvent être vues comme des
listes d’éléments sur lesquelles les opérations disponibles sont définies par :
EstVide(ε) = vrai
EstVide(e :: l) = faux
Empiler(e, l) = e :: l
Dépiler(e :: l) = (e, l)
Dépiler(ε) est indéfini
Sommet(e
:: l) = e
Sommet(ε) est indéfini.
39
Du point de vue mathématique, Dépiler renvoie une paire : élément, pile. 2
Mais nous utiliserons toujours la notation au sens informatique, comme dans :
e = Dépiler(P ), en laissant aux effets de bord le soin de modifier la pile.
3.1.2 Files
En anglais : queues
Une file est une structure de donnée que l’on rencontre aussi très souvent
dans la vie de tous les jours : la file d’attente. L’élément que l’on retire est
toujours le premier élément ajouté et qui n’a pas encore été retiré. On l’ap-
pelle tête de la file. Le dernier élément ajouté est l’élément de queue. On parle
alors de structure FIFO (first in first out ). Les opérations fondamentales sont
les mêmes que celles des piles :
– EstVide(F ), le test à vide,
– AjouterFile(e, F ), (ou InsérerFile(e, F )) ajoute l’élément e dans la file,
– RetirerFile(F ), retire l’élément de tête la file et le renvoie,
– TeteFile(F ) renvoie l’élément de tête sans modifier la file.
Ces quatres opérations peuvent être réalisées de manière à ce que leurs
temps d’exécution soit toujours constant, c’est à dire en Θ(1), et en espace
constant.
En termes plus mathématiques, les files peuvent être vues comme des
listes d’éléments sur lesquelles les opérations disponibles sont définies par :
EstVide(ε) = vrai
EstVide(e :: l) = faux
AjouterFile(e, l) = l :: e
RetirerFile(e :: l) = (e, l)
RetirerFile(ε) est indéfini
TeteFile(e :: l) = e
TeteFile(ε) est indéfini.
2. Ceci fait qu’il est mathématiquement correct d’écrire Empiler(Dépiler(l)) qui vaut alors l
lorsque Dépiler(l) est défini (i.e. lorsque l n’est pas vide).
40
[Link]
sont similaires à celles des piles et des files, plus une primitive qui permet de
modifier la priorité d’un élément :
– EstVide(F ), test à vide ;
– Insertion(e, F ), insertion ;
– RetraitMax(F ), retrait
– LectureMax(F ), lecture du prochain élément (renvoie l’élément maxi-
mum sans modifier la file de priorité) ;
– Modifier(x, e, F ) qui permet de modifier un élément quelconque de la
file, et en particulier sa priorité. Pour cela il faut connaître l’adresse x de
l’élément dans la file. L’argument e est la nouvelle valeur de l’élément,
elle contient en particulier sa nouvelle priorité.
Une réalisation des files de priorités à l’aide de tas (vue au prochain cha-
pitre) permet de rendre :
– constant Θ(1) le temps d’exécution des opérations de test à vide et de
lecture du maximum ;
– et en Θ(log N ), où N est le nombre d’éléments, le temps d’exécution
en pire cas des opération d’insertion, de retrait et de modification ;
– de plus toutes ces opérations sont en espace constant.
Liste chaînée. Une liste chaînée est une structure de donnée séquentielle
qui permet de stocker une suite d’éléments en mémoire. Chaque élément est
stocké dans une cellule et les cellules sont chaînées : chaque cellule contient,
en plus d’un élément, l’adresse de la cellule suivante, et éventuellement l’adresse
de la cellule précédente dans le cas des listes doublement chaînées. On peut
représenter graphiquement une cellule de liste simplement chaînée par une
boîte contenant deux champs et une cellule de liste doublement chaînée par
une boîte contenant trois champs :
41
200, 300 se représente ainsi :
struct cellsimple_s {
element_t element;
struct cellsimple_s * suivant;
};
struct celldouble_s {
element_t element;
struct celldouble_s * precedant;
struct celldouble_s * suivant;
};
42
[Link]
qui ne diffère du type des listes simplement chaînées que par l’ajout du champ
precedant dans les cellules.
Dans les deux cas, listes simplement chaînées et listes doublement chaî-
nées, on peut introduire des variantes dans la représentation des listes. En
voici deux qui ne changent pas la manière de définir le type des listes en C,
mais changent la manière de les manipuler.
Utilisation d’une sentinelle. Il est parfois plus facile de travailler avec des
listes chaînées dont le premier élément ne change jamais. Pour cela on in-
troduit une première cellule sentinelle dont l’élément ne compte pas. La liste
vide contient alors cette unique cellule. L’avantage est que la modification (in-
sertion, suppression) du premier élément de la liste (qui est alors celui dans
la seconde cellule) ne nécessite pas de mettre à jour le pointeur qui indique
le début de la liste (voir l’exemple de code C pour la suppression avec et sans
sentinelle un peu plus loin). La liste de notre exemple, se représente alors
comme ceci :
43
primitives sont possibles, par exemple avec des listes doublement chaînées :
l’ajout en fin de liste et la concaténation de deux listes, mais nous n’en parlons
pas dans ce cours.
Voici une réalisation des primitives à l’aide de fonctions en C, pour les
listes simplement chaînées (non circulaires et sans sentinelle). Lorsque ces
fonctions fonctionnent sans modification pour les listes doublement chaînées,
nous utilisons un type générique liste_t.
Test à vide. Le test à vide prend une liste en paramètre, renvoie vrai (ou 1)
si la liste est vide et faux (0) sinon.
44
return y;
}
Suppression.
45
free(y); /* Suppression de la première cellule */
}
typedef listesimple_t pile_t; /* les piles sont réalisées par les listes */
46
liste et la suppression à l’autre bout, une file doit fournir l’adresse du premier
et du dernier élément de la liste chaînée de ses éléments. La tête de la liste
sera la tête de file (où se fait le retrait) et le dernier élément de la liste son
élément de queue (où se fait l’ajout). Voici le code C d’une réalisation des files
basée sur les listes simplement chaînées.
typedef struct {
liste_t tete;
liste_t fin;
} * file_t;
47
Chapitre 4 imilé)
1942, fac-s
D
eap (B
The H
Arborescences
Définition 4.1. Une arborescence binaire est une structure de donnée conte-
nant un nombre fini d’éléments rangés dans des nœuds, telle que :
– lorsque la structure n’est pas vide, un nœud particulier, unique, appelé
racine sert de point de départ ;
48
– tout nœud x autre que la racine fait référence de manière unique à un
autre nœud, appelé son parent et la racine n’a pas de parent ;
– chaque nœud x peut faire référence à zéro, un ou deux nœuds fils : un
fils gauche et un fils droit, chacun de ces fils a alors x pour parent ;
– Tous les nœuds ont la racine pour ancêtre commun (parent, ou parent
de parent, ou parent de parent de parent, etc.).
Comme pour les listes chaînées il est utile de se donner une représentation
graphique sous forme de cellules (ici on parlera de nœud). Cette représenta-
tion, le type en C correspondant et un exemple sont données figure 4.1.
Il y a au moins quatre opérations de lecture (qui ne modifient pas la struc-
ture) communes à toutes les structures de données basées sur les arbores-
cences binaires : le test à vide qui prend un arbre en argument et rend vrai
s’il ne contient pas de nœud et les trois opérations de lecture des références
entre les nœuds. Ces trois opérations prennent en entrée un nœud. L’une rend
son nœud parent (lorsqu’il existe), et les deux autres rendent respectivement
le fils gauche et le fils droit (lorsqu’ils existent).
Type en C
200 300 200 300
typedef struct noeud_s { \\ \
struct noeud_s *parent;
400
struct noeud_s *gauche;
struct noeud_s *droite;
element_t e;
400
} *ab_t;
\\
Définition 4.2. Plus généralement, une arborescence est comme une arbo-
rescence binaire mais où les fils d’un nœud peuvent aussi être en nombre
supérieur à deux et sont donnés par une liste ordonnée.
49
Représentation d’un Un exemple d’arbre Sa représentation
nœud
100
\
parent 100
200 300 400 \
donnée (élément)
50
pour jouer le rôle de la racine. Ainsi il y a une différence subtile entre la dé-
finition mathématique d’arbre et celle d’arborescence : une arborescence est
un arbre dans lequel on a choisi une racine. Quelques mathématiciens parlent
plutôt d’algue pour les arbres sans racine. Dans ce cours nous prenons le parti
d’appeler arbre une structure arborescente et donc de donner une racine aux
arbres.
La distance d’un nœud x à la racine est le nombre de fois où il faut remon-
ter à un parent pour passer de x à la racine : si ce nœud est la racine cette
distance est 0, si le parent de x est la racine c’est 1, etc.
la profondeur d’un nœud x dans un arbre est sa distance à la racine. La
profondeur de la racine est donc 0, de ses fils éventuels 1, etc. Nous définis-
sons la hauteur d’un arbre comme le maximum des profondeurs de ses nœuds,
plus un (ce « plus un » est affaire de convention, et cette convention n’est pas
la même partout). La hauteur d’un nœud est la différence entre la hauteur de
l’arbre et la profondeur du nœud.
p = 0, h = 4 b
p = 1, h = 3 b b
p = 2, h = 2 b b b
p = 3, h = 1 b b b
Figure 4.3 – Exemple d’arbre binaire avec hauteur et profondeur des nœuds
Un nœud qui n’as pas de descendant est une feuille. Un nœud qui n’est
pas une feuille est parfois dénommé nœud interne (ou encore nœud strict ).
Arbre binaire quasi-parfait. Ordonnons les nœuds d’un arbre binaire par-
fait selon leur profondeur puis de gauche à droite. En premier on a la racine,
51
puis ensuite ses deux fils (de profondeur 1), le gauche, puis le droit, ensuite les
nœuds de profondeur 2, d’abord les fils du fils gauche de la racine, le gauche
puis le droit, puis les fils du fils droit de la racine etc. Si on supprime un
nombre quelconque de nœuds, en partant des derniers pour cet ordre, on ob-
tient ce qu’on appelle un arbre binaire quasi-parfait. Voici un exemple d’arbre
quasi-parfait où les nœuds sont numérotés dans l’ordre, en commençant à
zéro. On ne représente pas les éléments contenus dans les nœuds.
1 2
3 4 5 6
7 8 9
typedef struct {
element_t *tab; // le tableau
int mem; // Nombre maximum d’éléments dans le tableau
int taille; // nombre d’éléments de l’arbre (mem => taille)
52
} *arbrebqp_t;
Un tas est une structure de donnée basée sur les arbres binaires quasi-
parfaits, qui réalise efficacement les files de priorité, c’est à dire avec de bons
résultats de complexité algorithmique sur les opérations fondamentale : ajout,
retrait, modification de la priorité d’un élément se font en O(log N ).
Définition 4.3. Un tas max (respectivement tas min ), également appelé maxi-
mier (resp. minimier ), est un arbre binaire quasi-parfait tel que tout nœud dif-
férent de la racine possède une clé (ou priorité) plus petite (resp. plus grande)
que celle de son parent (T [i] ≤ T [Parent(i)]).
Les deux notions, tas max et tas min, sont symétriques, il suffit d’inverser
l’ordre des clés pour passer de l’une à l’autre. On travaille ici avec des tas
max.
53
Propriétés: Première conséquence de la définition de tas : dans un tas max
non vide, l’élément de clé maximum est toujours à la racine.
Tout sous-arbre obtenu à partir d’un tas en sélectionnant un nœud et tous
ses descendants est encore un tas.
Remarque 4.4. Un tableau trié en ordre décroissant est un tas max. Mais il
existe plusieurs manières différentes de structurer une liste d’éléments don-
née sous la forme d’un tas.
54
Ceci a pour effet de faire remonter l’élément e vers la racine par échanges,
jusqu’à ce qu’il se trouve dans un nœud dont le parent a une priorité supé-
rieure, ou bien qu’il est atteint à la racine. Le temps d’exécution du maintien
vers le haut est borné par la hauteur de l’arbre, il est donc en O(log N ) où N
est le nombre d’éléments du tas.
La fonction maintienHaut est une implantation en C de cette opération de
maintien vers le haut.
55
if ( (gauche(i) <= dernier(x)) && (x(gauche(i)).cle > x(imax).cle) )
imax = gauche(i);
if ( (droite(i) <= dernier(x)) && (x(droite(i)).cle > x(imax).cle) )
imax = droite(i);
/* Si ce maximum n’est pas en i on procède à un échange et on
relance sur le noeud qui contenait le maximum */
if ( imax != i ) {
echangetas(x, i, imax);
maintienBas(x, imax);
}
}
4 8 8
8 8 4 8 8 8
5 8 1 6 5 8 1 6 5 4 1 6
2 3 2 2 3 2 2 3 2
Ajout d’un élément. Pour ajouter un élément e dans un tas (InsererTas(x, e)),
on ajoute en fin de tableau un nœud n dans lequel on stocke e (sans modifier
le contenu des autres nœuds). Le nœud n devient ainsi la dernière feuille de
l’arbre. Le nœud n n’ayant pas de descendant la seule violation possible de
la propriété de tas qu’ait pu introduire cette insertion est entre le nœud n et
son parent. Il est en effet, possible que la priorité de e soit supérieure à celle
du parent de n. On appelle donc la procédure de maintien vers le haut sur
le nœud n. Ainsi l’opération d’insertion est en O(log N ) où N est le nombre
d’éléments du tas.
56
Retrait du maximum. Le retrait d’un élément dans un tas (RetirerMax(x))
se fait toujours par retrait de l’élément de priorité maximum, c’est dire l’élé-
ment à la racine de l’arbre. Pour que la structure d’arbre quasi-parfait reste
correcte, après avoir retiré l’élément à la racine, on le remplace par l’élément
de la dernière feuille de l’arbre (le dernier élément du tableau) et on sup-
prime cette feuille. Comme la nouvelle priorité de la racine est inférieure à
l’ancienne, on appelle sur la racine, la procédure de maintien vers le bas de la
propriété de tas. Le retrait du maximum est ainsi en O(log N ).
N
X
log k = log ΠN
k=1 k = log(N !) = O(N log N ).
k=1
57
parfait A contenant tous les éléments et on applique à ses nœuds internes,
en allant du dernier au premier, la procédure de maintien vers le bas de la
structure de tas.
À la fin de ce nouvel algorithme, on obtient un tas. En effet, un arbre réduit
à un seul nœud est toujours un tas. Donc dans A chaque feuille est déjà un tas.
Et si on applique l’algorithme de maintien vers le bas à un nœud dont les fils
sont déjà des racines de tas, alors l’arbre qui a pour racine ce nœud devient
à son tour un tas. Ainsi, en procédant du dernier au premier nœud interne, à
chaque étape, le nœud qui vient d’être traité est la racine d’un tas. Comme le
dernier élément traité est la racine, A est bien transformé en tas. De plus, les
seuls modifications apportées à A le sont par échange d’éléments entre des
nœuds. L’ensemble des éléments à la fin est donc bien le même qu’au début.
h h i+1
X
h−i h−1
X 1
E(h) = i2 =2 · i
i=1 i=1
2
| {z }
Sh
58
On cherche une majoration de Sh .
h
X
fh (z) = zi
i=1
z h+1 − 1
fh (z) =
z−1
D’où :
(h + 1)z h (z − 1) − (z h+1 − 1)
fh′ (z) =
(z − 1)2
1 (h + 1)(1/2)h+1 + ((1/2)h+1 − 1)
fh′ =−
2 (1/2)2
P+∞
Autre méthode. On sait que la somme s = 1 + 21 + 14 + . . . = 1
i=1 2i vaut
2. On a Sh ≤ S+∞ et on remarque que
+∞
1 1 X 1
S+∞ = s + s + s + . . . = s × i
= s2 = 4.
2 4 i=1
2
59
La structure de tas, permet d’écrire un algorithme de tri en place optimal
en temps, c’est à dire en Θ(N log N ). Le principe est de prendre un tableau en
entrée, d’y former un tas (O(N )) et de retirer un a un les maximums successifs
en les rangeant à la fin du tableau (N fois O(log N )). En C, cela donne le code
suivant :
8 1
9 8 8 6
5 3 4
60
2. On forme le tas en faisant appel à la fonction maintienBas sur chaque
nœud interne en allant du dernier au premier. Certains de ces appels
donnent lieu à de nouveaux appels de la fonction maintienBas (appels
récursifs).
8 1
9 8 8 6
5 3 4
8 1
9 8 8 6
5 3 4
2 2
8 1 8 8
9 8 8 6 9 8 1 6
5 3 4 5 3 4
2 2
8 8 9 8
9 8 1 6 8 8 1 6
5 3 4 5 3 4
2 9 9
9 8 2 8 8 8
8 8 1 6 8 8 1 6 2 8 1 6
5 3 4 5 3 4 5 3 4
8 8
5 8 1 6
2 3 4
61
9
8 8
5 8 1 6
2 3 4
8 8 4 8 8 8
5 8 1 6 5 8 1 6 5 4 1 6
2 3 2 3 2 3
3 8 8 [ 85834162 89]
8 8 3 8 5 8
5 4 1 6 5 4 1 6 3 4 1 6
2 2 2
Encore. . .
2 8 8 [ 8563412 889]
5 8 5 2 5 6
3 4 1 6 3 4 1 6 3 4 1 2
. . . et encore. . .
62
2 6 [ 652341 8889]
5 6 5 2
3 4 1 3 4 1
. . . et encore. . .
1 5 5 [ 54231 68889]
5 2 1 2 4 2
3 4 3 4 3 1
. . . et encore. . .
1 4 4 [ 4321 568889]
4 2 1 2 3 2
3 3 1
. . . et encore. . .
1 3 [ 312 4568889]
3 2 1 2
. . . et encore. . .
2 [ 21 34568889]
1 [ 1 234568889]
Le tri par tas est un algorithme de tri efficace : en place et en O(N log N ),
mais ses performances se dégradent lorsque le tableau à trier ne tient pas en
entier dans la mémoire de travail. Dans ce cas, quel que soit le tri, il faut que
le processus charge les portions (pages mémoires) de tableau en mémoire au
moment où il a besoin d’y accéder (lecture ou écriture). Mais contrairement
63
à d’autres tris qui travaillent plus localement, le tri par tas fait des accès
successifs au tableau dans des zones très éloignées les unes des autres ce qui
provoque de nombreux chargements (fautes de pages).
Fonction Rechercher(n )
Entrées : Le nœud racine r d’un arbre binaire de recherche et la clé
d’un élément c
Sorties : Le nœud de l’arbre contenant l’élément de clé c s’il en existe
un, ou le nœud vide N sinon.
si EstVide(r) alors
retourner N ;
sinon
si c = Clé(r) alors
retourner r ;
sinon
si c < Clé(r) alors
retourner Rechercher(Gauche(r), c) ;
sinon
retourner Rechercher(Droite(r), c) ;
64
La hauteur h peut varier entre log n et n où n est le nombre d’éléments
de l’arbre. La coloration rouge noir vue plus loin est une manière d’assurer
le fait que h soit en Θ(log n) et ainsi, que toutes les opérations élémentaires
soient en O(log n).
Le parcours infixe est un parcours séquentiel des nœuds de l’arbre, qui
pour chaque nœud commence par parcourir son sous-arbre gauche, puis traite
le nœud, puis parcours le sous-arbre droit.
Ainsi un arbre binaire de recherche peut être considéré comme une ma-
nière de garder rangée une liste d’éléments (penser à la recherche dichoto-
mique dans un tableau).
On considère également deux opération supplémentaires en O(h), suc-
cesseur et prédécesseur, qui, étant donné un nœud de l’arbre donnent le
nœud contenant l’élément qui lui succède, respectivement qui le précède,
dans l’ordre du parcours infixe, c’est à dire l’ordre naturel des éléments. Ces
deux opérations sont en O(h).
Le code C d’un implantation des arbre binaires de recherche sera vu en
cours d’amphi. Dans cette implantation la clé d’un élément est l’élément lui-
même (simplification).
On peut accepter ou non les répétitions de clés dans un arbre binaire de
recherche. Ici on considère que les arbre sont sans répétitions : l’insertion
d’un élément déjà présent dans l’arbre ne modifie pas l’arbre.
Convention : Pour la suite, on considère que les nœuds d’un arbre binaire
ont soit deux fils, soit aucun fils. Les nœuds sans fils sont les feuilles de l’arbre,
notées N ou NULL, et ne contiennent pas d’élément. On ne compte pas ces
feuilles dans la hauteur de l’arbre.
3 7
2 5 N 8
N N N N N N
Figure 4.4 – Un exemple d’arbre binaire de recherche
65
Les algorithmes pour Insérer, Supprimer, Parcours-infixe, Maximum, Mini-
mum, ainsi que Successeur et Prédécesseur seront détaillés au moment de
l’implantation. Nous donnons juste ici quelques indications.
– Pour Maximum, qui renvoie l’élément maximum de l’arbre il suffit, par-
tant de la racine, de descendre toujours à droite jusqu’à ce que ça ne
soit plus possible. Le maximum est le dernier élément trouvé.
– Pour la fonction Successeur y a deux cas de figure :
– soit le sous-arbre droit du nœud n’est pas vide, et dans ce cas il suffit
de rechercher l’élément de clé minimale (le plus à gauche) dans ce
sous-arbre droit.
– soit le sous-arbre droit du nœud est vide, et dans ce cas il faut recher-
cher le premier ancêtre dont le fils gauche est un ancêtre du nœud.
– Insérer. L’insertion ajoute toujours l’élément comme une nouvelle feuille
de l’arbre dont la place est trouvé de la même manière qu’on effectue la
recherche d’une clé.
– Pour Supprimer, il y a plusieurs cas. Si le nœud à supprimer n’a pas
de fils, on l’ôte. S’il n’a qu’un fils, on ôte le nœud et on rebranche son
fils à la place. S’il a deux fils, on l’échange avec son successeur (ou son
prédécesseur, ça marche aussi), dont on sait qu’il n’a pas de fils (voir
Successeur), et on l’ôte.
Pour une forme d’arbre binaire donnée, il y a une seule manière de ranger
dans ses nœuds des éléments deux à deux comparables de manière à en faire
un arbre binaire de recherche. La répartition des éléments dans les nœuds
mets en correspondance le parcours infixe des nœuds et la liste triée des
éléments.
Par contre pour une liste donnée d’éléments, n’importe quelle forme d’arbre
ayant le même nombre de nœuds qu’il y a d’éléments convient pour les ac-
cueillir.
Une suite d’insertions aléatoires de n éléments différents à partir d’un
arbre vide produit un arbre binaire recherche dont la hauteur est en général
plus proche de log n que de n. Mais il peut être utile de s’assurer que la
hauteur reste proche de log n, comme avec la coloration rouge noir vue plus
loin. Pour agir sur la forme de l’arbre, on utilise des rotations qui sont des
opérations préservant la propriété d’être un arbre binaire de recherche.
4.3.1 Rotations
Les rotations des arbres binaires sont données dans la figure 4.5. Elles
se lisent comme ceci. Une rotation à droite de centre x consiste en : prendre
l’élément a de x, le sous-arbre droite E de x, la racine y du sous-arbre gauche
de x, l’élément b contenu dans y , et C et D les deux sous-arbres gauche et
66
droite de y ; remplacer a par b dans x, remplacer le sous-arbre gauche de x par
C , et le sous-arbre droite de x par un arbre de racine contenant a (on utilise
y pour des raisons d’implantation) et dont les sous-arbres gauche et droite
sont respectivement D et E . La rotation à gauche de centre x est l’opération
réciproque.
Avec cette manière d’écrire les rotations la référence de x à son parent
n’a pas besoin d’être mise à jour. Il est assez standard de trouver une version
qui échange la place de x et de y plutôt que d’échanger leurs éléments mais
nous ne l’utilisons pas ici.
x x
a rotation_droite(x) b
y y
b E rotation_gauche(x) C a
C D D E
Figure 4.5 – Rotations gauche et droite. Dans cette version les éléments a et
b sont échangés entre les nœuds x et y mais x garde sa place dans l’arbre.
Définition 4.8. Un arbre rouge noir est un arbre binaire de recherche com-
portant un champ supplémentaire par nœud : sa couleur, qui peut valoir soit
ROUGE, soir NOIR. En outre, un arbre rouge noir satisfait les propriétés sui-
vantes :
1. Chaque nœud est soit rouge, soit noir.
67
2. Chaque feuille est noire.
3. Si un nœud est rouge, alors ses deux fils sont noirs.
4. Pour chaque nœud de l’arbre, tous les chemins descendants vers des
feuilles contiennent le même nombre de nœuds noirs.
5. La racine est noire.
30
20 40
10 25 35 50
03 15 21 24 32 37 N N
N N N N N N N N N N N N
Figure 4.6 – Un exemple d’arbre rouge noir
68
Troisième partie
Éléments de calculabilité
69
Chapitre 5
Éléments de calculabilité
70
Lorsque (e, s) est dans la relation f , on écrit f : e 7→ s, ou encore f (e) =
s. Lorsque pour tout e ∈ E , f (e) est défini (c’est à dire qu’il existe un s ∈ S
tel que f (e) = s) la fonction est totale, autrement la fonction est partielle. Il
suffit d’adjoindre un élément distingué ⊥ à l’ensemble S pour représenter les
fonctions partielles de E → S par les fonctions totales de E → S ∪ {⊥} (on
envoie les e pour lesquels f n’est pas définie sur ⊥).
Toute partie infinie de N est dénombrable. On dit d’un ensemble qu’il est
au plus dénombrable lorsqu’il existe une bijection entre E et une partie de N.
D = {k ∈ N | k ∈
/ e(k)}
X = {χA | A ⊆ N}
(
1 si n ∈ A
des fonctions χA : n 7→ qui testent l’appartenance à une partie
0 sinon
A de N. Cet ensemble à autant d’éléments que P(N), il est donc non dénom-
NN ne peut pas être dénombrable.
brable, et il s’en suit que
71
On peut toujours considérer qu’un programme calcule une fonction au
sens mathématique : il associe de manière déterministe une sortie d’un cer-
tain ensemble S à une entrée d’un certain ensemble E . Cette fonction est en
général partielle : le programme boucle sur certaines entrée, et ne renvoie pas
de résultat, la fonction n’est donc pas définie sur ces entrées. Par opposition
à partielle, une fonction qui à chaque entrée associe une sortie est dîte totale.
On peut totaliser la fonction (la rendre totale) en ajoutant un symbole ⊥ pour
dénoter que le programme boucle sur l’entré e.
Définition 5.5. Une fonction calculable est une fonction (au sens mathéma-
tique) telle qu’il existe au moins un programme la calculant.
Pour une même fonction calculable il est possible d’écrire une infinité de
programmes qui la calcule (il suffit de partir de l’un ces programmes et d’y
ajouter des blocs d’instructions arbitraire n’ayant pas d’incidence sur le ré-
sultat du calcul).
On oppose parfois l’intension, (ou la compréhension) des programmes à
l’extension des fonctions. Intuitivement, une extension est une liste exhaustive
souvent infinie : la liste des couples (e, s) mis en relation par une fonction,
la liste des entiers pairs, tandis que l’intension est une représentation finie
d’un ensemble potentiellement infinie d’objets, par exemple un programme
calculant f (e) pour tout e, ou l’écriture {n ∈ N | 2 divise n}.
Proposition 5.6. L’ensemble des mots finis d’entiers est dénombrable par
une fonction calculable de réciproque calculable. L’ensemble Pfin. (N) des par-
ties finies de N est dénombrable.
Démonstration. Il est plus facile de démontrer que l’ensemble des mots finis
non-vides d’entiers est dénombrable (voir plus bas). On ajoute le mot vide en
utilisant un décalage n 7→ n + 1 dans l’énumération précédente. Pour ce qui
de la deuxième partie de la proposition, on peut alors rapidement conclure par
le théorème de Cantor-Bernstein mais c’est hors du programme de ce cours.
Ce théorème très pratique établit que s’il existe une injection de f : A ֒→ B
et une injection g : B ֒→ A alors il existe une bijection entre A et B .
Montrons que l’ensemble des mots finis non-vides d’entiers est dénom-
brable. Rappelons que N × N est dénombrable c’est à dire qu’il existe une
bijection calculable dans les deux sens f : N → N × N. Pour les septiques,
prendre l’inverse de la fonction (p, q) 7→ 2p (2q + 1) (notez que cet inverse
est calculable). À un entier k on peut alors associer une paire f (k) = (n, c)
où n + 1 sera la longueur du mot recherché. Il suffit alors d’appeler f , n fois
sur le second terme de la paire trouvée à chaque étape, pour construire un
mot d’entiers : si n = 3 on fait par exemple f (c) = (a1 , c1 ), f (c1 ) = (a2 , c2 ),
f (c2 ) = (a3 , c3 ), a4 = c3 , ce qui donne le mot a1 a2 a3 a4 .
72
Un problème de décision sur un ensemble E est un énoncé D(e) qui pour
chaque élément e de E est soit vrai soit faux. C’est donc une fonction D :
E → {vrai, faux}. Un problème de décision est trivial lorsque il est vrai pour
tous les éléments de E (l’ensemble {e ∈ E | D(e)} est égal à E ) ou bien
lorsqu’il faux pour tous les éléments de E (l’ensemble {e ∈ E | D(e)} est
vide).
D’un point de vue algorithmique, un problème de décision est dit décidable
lorsqu’il existe un un programme qui le calcule (D : E → {vrai, faux} est une
fonction calculable). Autrement il est dit indécidable.
Attention, pour qu’un problème soit décidable il faut que le programme qui
le calcule termine pour chaque entrée e ∈ E en donnant la réponse exacte. Un
problème indécidable D est dit semi-décidable lorsqu’il existe un programme
qui termine et répond vrai sur chaque entrée e ∈ E pour laquelle D(e) est
vrai, et lorsqu’il termine sur les autres entrées, répond faux. Remarquez qu’il
existe nécessairement une entrée e, telle que D(e) est faux, pour laquelle le
programme ne termine pas (autrement le problème serait décidable). D’un
point de vue calculatoire, la semi-décidabilité n’a que peu d’intérêt.
Proposition 5.7. Pour un langage donné, l’ensemble des programmes qui cal-
culent une fonction partielle de N → N est dénombrable, et donc l’ensemble
des fonctions calculables est dénombrable.
Lemme 5.8. Pour un langage donné, on peut énumérer l’ensemble des pro-
grammes, et cette énumération peut être choisie calculable et de réciproque
calculable.
73
alors le n-ième programme, g , boucle sur l’entrée n, ce qui est impossible.
Si non c’est que h(n, n) = 1 mais alors le n-ième programme g , termine sur
l’entrée n, ce qui est également impossible. C’est impossible dans les deux
cas. Contradiction. Donc h n’existe pas.
Jusque là nous avons simplement utilisé le fait que nous pouvions asso-
cier un numéro unique à chaque programme, par contre rien n’exige que la
numérotation soit surjective ou calculable ou de réciproque calculable.
Pour conclure à l’impossibilité de l’existence de H , il nous faut montrer
que l’existence de H implique celle de h.
Si le programme H existe il fonctionne sur les programmes de N → N.
Or d’après le lemme 5.8, il existe une énumération de ces programmes dont la
réciproque est calculable. On a donc une fonction e qui à chaque entier associe
un programme e(p) de type N → N. On peut donc écrire le programme h(p, k)
comme étant le programme qui renvoie la valeur de H(e(p), k). Mais puisque
h n’existe pas c’est que H non plus.
Remarque 5.11. Si les algorithmes sont exécutés sur une machine à mémoire
finie, alors le nombre d’états de n’importe quel programme est fini. Dans ce
cas il est théoriquement possible de décider de l’arrêt de n’importe quel pro-
gramme s’exécutant sur cette machine. En effet, sur une machine à N états si
un programme change plus de N fois d’état avant l’arrêt du programme, alors
le programme ne s’arrêtera jamais (il passe par une suite d’états cycliques).
Nos ordinateurs sont à états finis mais attention N est en général tellement
grand que cet argument de finitude est inapplicable en pratique. Pensez aux
28 589 934 592 états d’un ordinateur ayant un Gibi octet de mémoire (sans parler
des mémoires de masse) !
74
Proposition 5.13 (Indécidabilité de l’égalité extensionnelle (espace)). Si on
restreint notre champs d’étude aux algorithmes de type N → N qui terminent
toujours (sur chaque argument), savoir si deux de ces algorithmes calculent
la même fonction mathématique est un problème indécidable (il n’existe pas
de programme scrutateur qui donne la bonne réponse à tous les coups).
Remarque 5.15. Si E est un ensemble fini de données disons une partie finie
de N, et que l’on considère uniquement les algorithmes E → N qui terminent
toujours, alors il est facile de tester si deux de ces algorithmes calculent la
même fonction de E → N (en calculant effectivement sur toutes les valeurs
de E ).
75
(Asperti 2006). Par exemple, parmi les programmes qui s’exécutent en temps
Θ(N log N ), il est impossible de savoir à coup sûr lesquels font un tri sur leur
entrée.
En terme de complexité en temps ou en espace des programmes, on définit
des classes de programmes, qui ont l’avantage d’être closes par composition 1 .
Par exemple la classe P des programmes qui calculent en temps polynomial est
l’ensemble des programmes f pour lesquels il existe une polynôme réel Q(X)
tel que sur une donnée d, f calcule en pire cas en temps O(Q(N )) où N
est la taille de la donnée d. Si deux programmes f et g sont dans P, alors le
programme qui calcule g(f (d)) pour toute donnée d est également dans P.
1. Ces classes sont très connues. D’ailleurs vous avez peut être déjà entendu parler de la
grande question à un million de dollars P 6= NP ?
76
Quatrième partie
Exercices
77
Chapitre 6
Exercices
78
[Link]
6.1 Exercices du premier chapitre
6.1.1 Récursivité
Exercice 1 (Récursivité).
si n = 0 alors
retourner 1; unsigned toto(unsigned n){
sinon if (n == 0) return 1;
retourner n × Toto(n − 1); return n * toto(n - 1);
}
3. Écrire une fonction récursive qui calcule le pgcd de deux nombres entiers posi-
tifs.
si n ≤ 1 alors
retourner 0; unsigned tata(unsigned n){
5. Il n’est parfois pas suffisant d’avoir un bon cas de base, voici un exemple. En C,
que vaut Morris(1, 0) ?
79
Exercice 2 (La fonction 91 de McCarthy).
Les fonctions récursives mêmes simples donnent parfois des résultats difficiles à pré-
n > 100 la fonction 91 de McCarthy
voir. Pour s’en convaincre voici un exemple. Pour
vaut n − 10. Mais pour n ≤ 100 ? Tester sur un exemple. . . pas trop mal choisi, puis
prouver le résultat en toute généralité.
Fonction Tata(n )
si x > 100 alors
retourner x − 10;
sinon
retourner McCarthy(McCarthy(x + 11));
int McCarthy(int x)
{
if (x > 100) return(x - 10);
80
Exercice 4 (Le robot cupide).
Toto le robot se trouve à l’entrée Nord-Ouest d’un damier rectangulaire de N ×M
cases. Il doit sortir par la sortie Sud-Est en descendant vers le Sud et en allant vers
l’Est. Il a le choix à chaque pas (un pas = une case) entre : descendre verticalement ;
aller en diagonale ; ou se déplacer horizontalement vers l’Est. Il y a un sac d’or sur
chaque case, dont la valeur est lisible depuis la position initiale de Toto. Le but de Toto
est de ramasser le plus d’or possible durant son trajet.
On veut écrire en pseudo-code ou en C, un algorithme Robot-cupide(x, y ) qui, étant
donnés le damier et les coordonnées x et y d’une case, rend la quantité maximum d’or
(gain) que peut ramasser le robot en se déplaçant du coin Nord-Ouest jusqu’à cette
case. En C, on pourra considérer que le damier est un tableau bidimensionnel déclaré
globalement et dont les dimensions sont connues.
A B
C D
6.1.2 Optimisation
Exercice 5 (Exponentiation rapide).
n
L’objectif de cet exercice est de découvrir un algorithme rapide pour le calcul de x où
x est un nombre réel et n ∈ N. On cherchera à minimiser le nombres d’appels à des
opérations arithmétiques sur les réels (addition, soutraction, multiplication, division)
et dans une moindre mesure sur les entiers.
1. Écrire une fonction de prototype double explent(double x,unsigned n) qui cal-
n
cule x (en C, ou bien en pseudo-code mais sans utiliser de primitive d’exponen-
tiation).
2. Combien de multiplication sur des réels effectuera l’appel explent(x, 4) ?
4 8 16
3. Calculer à la main et en effectuant le moins d’opérations possibles : 3 , 3 , 3 ,
10
3 . Dans chaque cas combien de multiplications avez-vous effectué ?
256 32+256
4. Combien de multiplications suffisent pour calculer x ? Combien pour x ?
On note bk−1 . . . b0 pour l’écriture en binaire des entiers positifs, où b0 est le bit de
poids faible et bk−1 est le bit de poids fort. Ainsi
10011 = 1 × 24 + 0 × 23 + 0 × 22 + 1 × 21 + 1 × 20 = 19.
81
De même que pour l’écriture décimale, bk−1 est en général pris non nul (en dé-
cimal, on écrit 1789 et non 00001789 – sauf sur le tableau de bord d’une machine à
voyager dans le temps).
5. Comment calculer x10011 en minimisant le nombre de multiplications ?
6. Plus généralement pour calculer xbk−1 ...b0 de combien de multiplications sur
les réels aurez-vous besoin (au maximum) ?
Rappels. Si n est un entier positif alors n mod 2 (en C : n % 2) donne son bit de
poids faible. La division entière par 2 décale la représentation binaire vers la droite :
10111/2 = 10110/2 = 1011.
7. Écrire une fonction double exprapide(double x, unsigned n) qui calcule xn ,
plus rapidement que la précédente.
8. Si on compte une unité de temps à chaque opération arithmétique sur les réels,
combien d’unités de temps sont nécessaires pour effectuer x1023 avec la fonc-
tion explent ? Et avec la fonction exprapide ?
9. Même question, en général, pour xn (on pourra donner un encadrement du
nombre d’opérations effectuées par exprapide).
10. L’algorithme d’exponentiation rapide peut être considéré comme optimal asymp-
totiquement (ce résultat demanderait à être explicité mais il est trop difficile à
établir pour ce cours). On peut toutefois faire un peu mieux sur certains cas (ça
ne remet pas en cause le résultat asymptotique). Par exemple, on peut calculer
x15 avec cinq multiplications, voyez-vous comment ?
82
3, 4, . . . et dans l’autre direction les immeubles numérotés −1, −2, −3, −4, . . . . Vous
vous rendez chez un ami qui habite rue Z sans savoir à quel numéro il habite. Son nom
étant sur sa porte, il vous suffit de passer devant son immeuble pour le trouver (on
suppose qu’il n’y a des immeubles que d’un coté et, par exemple, la mer de l’autre). On
notera n la valeur absolue du numéro de l’immeuble que vous cherchez (bien entendu
n est inconnu). Le but de cet exercice est de trouver un algorithme pour votre déplace-
ment dans la rue Z qui permette de trouver votre ami à coup sûr et le plus rapidement
possible (d’un point de vue asymptotique).
1. Montrer que n’importe quel algorithme sera au moins en Ω(n) pour ce qui est
de la distance parcourue.
2. Trouver un algorithme efficace, donner sa complexité en distance parcourue
sous la forme d’un Θ(g). Démontrer votre résultat.
3. Démontrer :
2. En notation asymptotique quelle est la borne minimale en temps des tris par 0.5 pt
comparaison, en pire cas et en moyenne ?
3 4 min
83
Exercice 11 (Partiel mai 2008).
Rappeler les définitions utilisées et justifier (démontrer) vos réponses.
1 pt
1. Est-ce que n2 − 2n + 1 = O(n2 ) ? 3 9 min
1 pt
3 9 min 2. Est-ce que
Pn
i=1 log i = Ω(n) ?
1 pt
3 9 min 3. Est-il vrai que si f = O(g) et f = Ω(h) alors g = Ω(h) ?
3 pt Exercice 17.
2 18 min En rappelant les définitions, démontrer chacune des assertions suivantes.
84
Pn
1. 1+ i=2 log i = Ω(n)
2. Si f = Θ(h) et g = O(h) alors f + g = O(h)
3. Il est faux de dire que, en général, si f = O(g) et g = Ω(h) alors f = Ω(h)
(Donner un contre-exemple argumenté).
En supposant que les seules opérations significatives pour le temps d’exécution sont 2 pt
effectuées par f_aux, donner un équivalent asymtpotique du temps d’exécution de f.
3 18 min
Exercice 19.
Montrer que :
85
6.2 Exercices du second chapitre
−1 si T [j] > T [k]
Comparer(T , j , k ) qui rend : 1 si T [j] < T [k]
0 lorsque T [j] = T [k] (même masses).
Exercice 21 (Interclassement).
Soient deux tableaux d’éléments comparables t1 et t2 de tailles respectives n et m,
tous les deux triés dans l’ordre croissant.
86
On note N = n + m le nombre total d’éléments à interclasser. En considérant le
nombre de comparaisons, en fonction de N , discuter l’optimalité de votre algorithme
en pire cas et en meilleur cas à l’aide des questions suivantes (démontrer vos résultats).
2. À votre avis, sans considérer un algorithme en particulier, dans quel cas peut-il
être nécessaire de faire le plus de comparaisons : n grand et m petit ou bien n
et m à peu près égaux ?
Dans la suite, on suppose que n et m sont égaux (donc N = 2n).
3. Dans le pire des cas, combien de comparaisons faut-il faire pour réussir l’in-
terclassement ? Cela correspond t-il au nombre de comparaisons effectuées par
votre algorithme dans ce cas ?
87
3. En déduire une relation entre le nombre total d’inversions dans toutes les per-
mutations de 0, . . . , n − 1 et le nombre moyen d’échanges effectués par le tri
bulle sur une entrée de taille n.
L’image miroir de la permutation a0 , a1 . . . , an−1 est la permutation an−1 , an−2 , . . . , a0 .
4. Montrer que l’ensemble des permutations de 0, . . . , n − 1 est en bijection avec
lui-même par image miroir.
5. Si (i, j) est une inversion dans la permutation a0 , a1 . . . , an−1 , qu’en est-il dans
son image miroir ? Réciproquement ? En déduire le nombre moyen d’inversions
dans une permutation des entiers de 0 à n − 1 et le nombre moyen d’échanges
effectués par le tri bulle.
Une inversion dans une entrée a0 , . . . , an−1 est la donnée d’un couple d’indices (i, j)
tel que i < j et ai > aj .
Rappel. Un échange d’éléments entre deux indices i et j dans un tableau est une
opération qui intervertit l’élément à l’indice i et l’élément à l’indice j , laissant les
autres éléments à leur place.
2. Si le tri gnome effectue un échange entre deux éléments, que peut on dire de
2,5 pt l’évolution du nombre d’inversions dans ce tableau avant l’échange et après
3 22 min l’échange (démontrer) ?
n(n−1)
On suppose que le nombre moyen d’inversions dans un tableau de taille n est 4
.
3. Si un tableau t de taille n contient f (n) inversions, combien le tri gnome ef-
2 pt fectuera d’échanges sur ce tableau (démontrer) ? En déduire le nombre moyen
3 18 min d’échanges effectués par le tri gnome sur des tableaux de taille n.
88
On raisonne maintenant sur les algorithmes de tri généralistes (par comparaison).
5. Sans utiliser le résultat que vous venez de rappeler, montrer que pour N > 2,
il n’y a pas d’algorithme A qui trie n’importe quel tableau de taille N en au
plus N − 1 comparaisons. (Considérer les N ! permutations de 0, . . . , N − 1 en 1,5 pt
entrée et raisonner sur la hauteur de l’arbre de décision de A.)
3 13 min
Exercice 26.
Étant donné un tableau T de N entiers et un entier x, on veut déterminer s’il existe 3 pt
deux éléments de T dont la somme est égale à x. 3 27 min
89
1. Donner un algorithme le plus simple possible, basé sur la comparaison, sans
faire appel à des algorithmes du cours. Quel est le pire cas ? Donner un équi-
valent asymptotique du nombre de comparaisons dans le pire cas. (Justifier)
2. Pouvez-vous donner un algorithme en O(N log N ) comparaisons en pire cas ?
(Justifier) Vous pouvez utiliser des algorithmes vus en cours et les résultats de
complexité sur ces algorithmes.
Exercice 27.
Soit un tableau T de N éléments deux à deux comparables. On souhaite partitionner
le tableau autour de son premier élément T [0], appelé pivot. Après partition, le pivot
p, les éléments plus petits que le pivot sont (dans le désordre) aux in-
est à l’indice
dices inférieurs àp et les éléments strictement plus grands que le pivot sont (dans le
désordre) aux indices supérieurs à p.
Tableau T
| {z } | {z
Éléments plus petits que le pivot Éléments plus grands que le piv
Fonction Maximum(T )
m = 0;
pour i ← 1 à Taille(T ) − 1
faire
si T [i]
≥ T [m] alors
m = i;
retourner m ;
Exercice 29.
tot: 5 pt Le but de cet exercice est trouver un bon algorithme pour la recherche de valeurs
médianes. En économie, le revenu médian est le revenu qui partage exactement en
deux la population : la moitié de la population dispose d’un revenu plus élevé que le
90
revenu médian, l’autre moitié d’un revenu moins élevé. Plus généralement, dans un
tableau l’élément médian (ou valeur médiane) est l’élément qui serait situé au milieu
du tableau si le tableau était trié. Lorsque le nombre d’éléments est pair, il n’y a pas
d’élément exactement au milieu. Par convention nous prendrons, pour tout N , comme
N
médian l’élément d’indice 2
dans le tableau trié (indexé à partir de 0).
Par exemple, dans le tableau suivant le revenu médian est de 1200 €.
individus A B C D E F G H
revenus mensuels 1400 2000 1300 300 700 5000 1200 800
Pour trouver le médian d’un tableau d’éléments deux à deux comparables on peut trier
N
le tableau puis renvoyer la valeur de son élément d’indice 2
.
1. Pour cette solution, quelle complexité en moyenne (en temps) peut on obtenir, .5 pt
au mieux ? Quel algorithme de tri choisir ?
3 4 min
On cherche un algorithme plus rapide. Il n’est sans doute pas nécessaire de trier tout
le tableau pour trouver le médian. Le professeur Hoare suggère d’utiliser l’algorithme
de partition de l’exercice 27 pour diviser les éléments à considérer. Après partition le
tableau T est fait de trois partie : la première partie est un tableau T ′ des éléments
de T plus petits que le pivot la deuxième partie ne contient que l’élément pivot et la
troisième partie est un tableau T ′′ des éléments plus grands que le pivot.
.5 pt
2. En fonction de l’indice p du pivot, dans quelle partie chercher le médian ? 3 4 min
4. Quel est le meilleur cas ? Pour quelle complexité ? Quel est le pire cas ? Pour 1 pt
quelle complexité ?
3 9 min
Pour estimer si la moyenne est plus proche du meilleur cas ou du pire cas, on fait
l’hypothèse que chaque fois que l’on fait une partition sur un tableau T , le médian se
2
trouve dans un sous-tableau contenant 3 des éléments de T.
5. Donner un équivalent asymptotique du nombre de comparaisons faites (on pourra .5 pt
s’aider de l’exercice 14).
3 4 min
91
Dans cette partie on s’intéresse au problème suivant : étant donné un ta-
bleau T de N éléments deux à deux comparables, déterminer quel est l’élé-
ment de rang k (le k -ième plus petit élément), c’est à dire l’élément x de T tel
que exactement k − 1 éléments de T sont plus petits que x. Bien entendu, on
peut supposer que k est choisi tel que 1 ≤ k ≤ N . On pourra considérer que
les éléments de T sont distincts (la comparaison ne les déclare jamais égaux).
Si on a par exemple les éléments 23, 62, 67, 56, 34, 90, 17 (N vaut 7) alors
l’élément de rang 3 est 34.
Exercice 30.
Le moyen le plus simple d’écrire une fonction Rang(T, k) résolvant ce problème est de
trier le tableau et de renvoyer l’élément d’indice k − 1 du tableau obtenu (les tableaux
0.5 pt commencent à l’indice 0). En choisissant au mieux l’algorithme de tri, quel sera en pire
3 4 min cas le temps d’exécution de cette fonction ?
92
le pivot dans le même ordre qu’ils étaient avant partitionnement et de même pour les
éléments plus grands. En représentant les tableaux et sous-tableaux obtenus successi-
vement, exécuter à la main Rang(T, 4) où T contient dans cet ordre les éléments : 3, 1 pt
2, 8, 6, 9, 1, 5. 3 9 min
Exercice 32.
En supposant que partitionner un tableau de n éléments prend un temps n, on étudie
le temps d’exécution global (appels récursifs compris) de Rang(T, k) en fonction de la 3 pt
taille N de T , en notation asymptotique. 3 27 min
1. Quel est le meilleur cas et quel temps obtient-on ? (Donner un exemple géné-
rique de tableau et de valeur de k réalisant ce meilleur cas et un équivalent
asymptotique du temps d’exécution).
2. Quel est le pire cas et quel temps obtient-on ? (Donner un exemple générique
de tableau et de valeur de k réalisant ce pire cas et un équivalent asymptotique
du temps d’exécution).
3. Supposons que T est de taille N = 2m et qu’au cours de la recherche de l’élé-
n
ment de rang 1, chaque partitionnement d’un tableau de taille n donne 2 élé-
ments plus petits que le pivot (c’est à dire que la fonction de partionnement ren-
n
voie l’indice p = 2
) jusqu’à arriver à la taille 1 dans la récursion. Quel est alors
le temps d’exécution en notation asymptotique ? (Ne pas chercher d’exemple de
tableau réalisant ce cas).
4. Que penser du temps d’exécution dans le cas plus général où, après chaque
n, l’appel récursif a lieu sur un tableau de taille
partition d’un tableau de taille
r × n où r < 1 est une proportion fixée globalement (à la question précédente
r valait 12 ) ?
3. lorsque les clés sont des entiers entre −n et n, cet algorithme peut-il être adap-
tée en un tri en temps linéaire ? Et lorsque on ne fait plus de supposition sur la
nature des clés ?
93
Rappel. Un tri est stable lorsque, à chaque fois que deux éléments ont la même clé,
l’ordre entre eux n’est pas changé par le tri. Par exemple, en triant (2, a), (3, b), (1, c), (2, d)
par chiffres croissants, un tri stable place (2, d) après (2, a).
1 pt
3 9 min 1. Écrire les trois listes obtenues. Comment s’appelle cette méthode de tri ?
k
On se donne un tableau t contenant N entiers entre 0 et 10 −1, où k est une constante
entière. Sur le principe de la question précédente (où k = 3 et N = 5), on veut
appliquer un tri par base, en base 10 à ces entiers.
On se donne la fonction auxiliaire :
1,5 pt 2. Que valent cle(123, 0), cle(123, 1), cle(123, 2) (inutile de justifier votre ré-
3 13 min ponse) ? Plus généralement, que renvoie cette fonction ?
On suppose que l’on dispose d’une fonction auxiliaire de tri void triaux(tableau_t t, int i)
qui réordonne les éléments de t de manière à ce que
94
exercice est de donner un algorithme rapide qui prend en entrée une suite finie s ayant
deux types d’éléments et qui rend la longueur maximale des sous-suites équilibrées de
s.
Par exemple, si s est la suite aababba alors la longueur maximale des sous-suites
équillibrées de s est 6. Les suites aababb et ababba sont deux sous-suites équilibrées
de s de cette longueur.
Pour faciliter l’écriture de l’algorithme, on considérera que :
– la suite en entrée est donnée dans un tableau de taille n, avec un élément par
case ;
– chaque cellule de ce tableau est soit l’entier 1 soit l’entier −1 (et non pas a et
b).
1. Écrire une fonction qui prend deux indices i et j du tableau, tels que 0 ≤ i <
j < n, et rend 1 si la sous-suite (sk )i≤k≤j est équilibrée, 0 sinon.
2. Écrire une fonction qui prend en entrée un indice i et cherche la longueur de la
plus grande sous-suite équilibrée commençant à l’indice i.
3. En déduire une fonction qui rend la longueur maximale des sous-suites équili-
brées de s.
4. Quel est la complexité asymptotique de cette fonction, en temps et en pire cas ?
5. Écrire une fonction qui prend en entrée le tableau t des éléments de la suite
sPet crée un tableau d’entiers aux, de même taille que t et tel que aux[k] =
k
j=0 sj .
6. Pour que (sk )i≤k≤j soit équilibrée que faut-il que aux[i] et aux[j] vérifient ?
Supposons maintenant que chaque élément de aux est en fait une paire d’entiers, (clé,
Pk
donnée), que la clé stockée dans aux[k] est j=0 sj et que la donnée est simplement
k.
7. Quelles sont les valeurs que peuvent prendre les clés dans aux ?
8. À votre avis, est-il possible de trier aux par clés croissantes en temps linéaire ?
Si oui, expliquer comment et si non, pourquoi.
9. Une fois que le tableau aux est trié par clés croissantes, comment l’exploiter
pour résoudre le problème de la recherche de la plus grande sous-suite équili-
brée ?
10. Décrire de bout en bout ce nouvel algorithme. Quelle est sa complexité ?
11. Écrire complétement l’algorithme.
95
1. Quel serait le temps d’exécution d’un algorithme fondé sur cette méthode, en
1 pt notation asymptotique et en fonction de N ? (Il faut expliquer comment vous
3 9 min écririez l’algorithme mais sans nécessairement le détailler).
Supposons maintenant que l’on fabrique un autre tableau S de même taille que
T de la manière suivante. Chaque élément S[i] est un couple d’entiers. Au départ,
j=i
le premier de ces deux entiers, S[i].somme en C, est égal à la somme Σj=0 T [j]. Le
second, S[i].indice, a simplement pour valeur l’indice i. On tri ensuite S par sommes
croissantes à l’aide d’un tri stable.
1 pt 3. Quel temps d’exécution global peut on obtenir par cette méthode (donner un
3 9 min temps d’exécution pour chaque étape).
Exercice 37.
n
Classer les fonctions de complexité n log n, 2 , log n, n2 , n par ordre croissant et pour
chacune d’elle donner l’exemple d’un algorithme (du cours ou des TD) qui a asymptoti-
2 pt quement cette complexité en pire cas, en temps. Répondre dans un tableau en donnant
3 18 min le nom de l’algorithme ou le nom du problème qu’il résout.
Exercice 38.
Classer les fonctions de complexité n log n, log n, n2 , n par ordre croissant. Pour les
1.5 pt complexités log n et n donner l’exemple d’un algorithme (du cours ou des TD) qui a
3 13 min asymptotiquement cette complexité en pire cas, en temps.
Exercice 39.
2
Classer les fonctions de complexité n , n, 2n , n log n par ordre croissant. Pour les com-
2
1.5 pt plexités n log n et n donner l’exemple d’un algorithme (du cours ou des TD) qui a
3 13 min asymptotiquement cette complexité en pire cas, en temps.
Exercice 40.
Soit la fonction MaFonction donnée ci-dessous en pseudo-code et en langage C (au
tot: 2 pt choix).
1. En supposant que le tableau passé en entrée est trié par ordre croissant, que
0,5 pt renvoie exactement cette fonction (sous quel nom connaissez-vous cet algo-
3 4 min rithme) ?
96
Fonction MaFonction(T, c)
Entrées : Un tableau croissant d’entiers T [0..n − 1] de taille Taille(T ) = n et
un entier c.
Sorties : Une case du tableau T ou bien une case vide.
si Taille(T ) > 0 alors
m = ⌊Taille(T )/2⌋ (partie entière inférieure);
si c = T [m] alors
retourner T [m];
sinon
si c < T [m] alors
T ′ = le sous tableau T [0..m − 1];
′
retourner MaFonction(T , c);
sinon
T ′′ = le sous tableau T [m + 1..Taille(T ) − 1];
′′
retourner MaFonction(T , c);
sinon
retourner case vide;
Exercice 41.
Montrer que dans un arbre binaire, si la profondeur maximale des feuilles est k alors
97
le nombre de feuilles est au plus 2k − 1.
98
6.3 Exercices du troisième chapitre
Exercice 42 (Piles).
On forme une nouvelle pile en empilant successivement 1, 2, 3 puis on dépile deux 0,5 pt
éléments. Quel élément reste-t-il dans la pile ? (Facile)
2 3 min
2. Écrire un algorithme pour copier dans P2 les nombres pairs contenus dans P1 .
Le contenu de P1 après exécution de l’algorithme doit être identique à celui
avant exécution. Les nombres pairs doivent être dans P2 dans l’ordre où ils 1 pt
apparaissent dans P1 .
2 6 min
1. On suppose que l’on a trois files f1 , f2 dont les éléments sont déjà triés et une
file f3 initialement vide. Écrire une fonction Interclasser(f1 , f2 , f3 ) qui range
dans l’ordre les éléments de f1 et f2 dans f3 .
99
2. Proposer une manière d’effectuer le partage des éléments d’une file f1 en deux
files f2 et f3 ayant le même nombre d’éléments. L’écrire sous la forme d’une
fonction Scinder(f1 , f2 , f3 ) (f2 et f3 sont initalement vides).
3. Écrire le tri.
4. Ce tri nécessite t-il, comme dans les tableaux, une mémoire auxilliaire de l’ordre
du nombre d’éléments à trier ?
1. En supposant que ces éléments sont initalement dans un tableau et que l’on
dispose de la structure de donnée file de priorité, proposer un algorithme de tri
utilisant cette structure.
2. Quel serait le temps d’exécution d’un tel tri, en pire cas ?
Rappel : l’insertion et la suppression dans les files de priorité est en Θ(log N ) en pire
cas (où N est le nombre d’éléments dans la file).
1. Pourriez-vous rappeler cette réalisation des piles (type des piles, empiler, depi-
ler, estVide, sommet), sans vous référer à vos notes de cours ? Pour simplifier,
considérer qu’il y a au plus NMAX (une constante) élements dans la pile.
2. Donner une réalisation des files (estVide, tete, ajouter, retirer) de taille bornée
par NMAX.
1. Écrire un algorithme récursif (et itératif) qui permet de fusionner deux listes
triées dans l’ordre croissant et retourne la liste finale. On pourra utiliser la
fonction
cmpListe(liste_t l1, liste_t l2);
qui retourne 1 si le premier élément de l1 est inférieur au premier élément de
l2, 0 s’ils sont égaux et -1 sinon.
2. Écrire un algorithme qui permet d’éliminer toutes les répétitions dans une liste
chaînée.
100
Exercice 50 (Juin 2007).
On suppose que 4 wagons numérotés de 1 à 4 sont placés en entrée sur le réseau
: 4 pt ferroviaire suivant.
sortie ent
1 2 3 4
| {z } | {z }
G F
C A
}
B
{z
|
Les actions possibles sont : Ajouter(wagon) qui fait entrer un nouveau wagon sur le
réseau (le wagon arrive par l’entrée dans la zone A), Retirer() qui fait sortir un wagon
(le wagon sort de la zone C par la sortie) ainsi que F() qui fait passer un wagon de
la zone A à la zone B et G() qui fait passer un wagon de la zone B à la zone C . Par
exemple, la séquence d’actions : Ajouter(1), Ajouter(2), Ajouter(3), Ajouter(4), F(), F(),
F(), F(), G(), G(), G(), G(), Retirer(), Retirer(), Retirer(), Retirer() donnera, par ordre de
sorties : 4, 3, 2, 1.
1. Si la séquence de wagons ajoutés est 1, 2, 3,
4 dans cet ordre, peut-on obtenir 0.5 pt
en sortie les wagons dans l’ordre 2, 4, 3,
1 (expliquer) ? 3 4 min
4. On suppose que l’on a une structure de données réalisant le réseau et ses quatre
actions. Comment l’utiliser pour réaliser une pile ? Une file ? (Décrire les opé-
rations d’ajout et de retrait de ces deux structures de données élémentaires à 1 pt
partir des quatre actions).
3 9 min
5. Donner une séquence de wagons en entrée, la plus courte possible, et un ordre 0.5 pt
de sortie que l’on ne peut pas réaliser (expliquer).
3 4 min
101
grand nombre d’états du jeu ce qui est hors de portée de notre esprit. Nous proposons
ici de trouver la solution optimale sous la forme d’une méthode à appliquer pas à pas
pour résoudre le jeu.
Un état du jeu est une distribution des disques sur les trois piquets, représen-
tés par des piles, a (départ), b (intermédiaire), c (arrivée). Dans l’état initial la pile a
contient les n disques, représentés par les entiers de 1 à n, empilés du plus grand n (à
la base), au plus petit 1 (au sommet). Les deux autres piles sont vides. Il faut déplacer
un par un les disques d’une pile vers une autre sans que jamais un disque ne soit posé
sur un disque plus petit. L’état final que l’on veut atteindre est celui où la pile d’arrivée
contient les n disques.
L’opération de base est le déplacement d’un disque d’une pile p vers une autre pile
q.
.5 pt
3 4 min 1. Définir Deplacer(p, q) à l’aide des primitives sur les piles.
1 pt 5. Quel disque est déplacé exactement un coup sur deux ? Combien de fois est-il
3 9 min déplacé en tout, en fonction de n?
On admet la propriété suivante. Lors d’un déplacement du disque 1 celui-ci ne
revient jamais sur la pile qu’il occupait avant son déplacement précédent. On en déduit
qu’il y a deux possibilité pour les déplacements du disque 1:
.5 pt 6. soit il occupe tour à tour les piles a, b, . . . (compléter, sur votre copie) soit il
3 4 min occupe tour à tour les piles a, c, . . . (compléter).
7. En raisonnant en arithmétique modulo trois, trouver une condition sur n per-
1 pt mettant de déterminer exactement quelle sera la séquence des déplacements
3 9 min du disque 1.
.5 pt 8. Déduire de ce qui précède les trois déplacements qui suivent celui-ci (n vaut
3 4 min 6) :
2
5 2 1 5 1
6 3 4 6 3 4
−−−−−−−−−→
a b c Deplacer(b, a) a b c
102
Exercice 52 (Réussite patience sort (partiel 2007)).
On se donne un paquet σ de N cartes sur lesquelles sont inscrites des valeurs deux à tot: 8,5 pt
deux comparables. Pour simplifier, on considérera que ces valeurs sont les entiers de
0 à N − 1, dans le désordre mais sans répétition.
On fait une réussite de la manière suivante :
– prendre la première carte du paquet et la poser devant soi, à sa gauche, inscrip-
tion au dessus (de manière à pouvoir voir sa valeur).
– Poser tour à tour les cartes suivantes sur la table, inscription au dessus, en
formant des piles de cartes. Pour chaque nouvelle carte x on peut :
– soit la poser sur une carte déjà posée sur la pile y , à la condition que la valeur
de x soit inférieure à la valeur de y ;
– soit commencer une nouvelle pile de carte en la posant à droite de toutes les
piles existantes.
– On s’arrête losqu’il n’y a plus de cartes dans le paquet.
Le but du jeu est de finir avec un nombre minimum de piles de cartes devant soi.
On emploie la stratégie qui consiste à placer une nouvelle carte toujours le plus
à gauche possible. Par exemple, si le paquet de cartes contient au départ la suite de
cartes :
σ = 6, 1, 5, 0, 7, 2, 9, 4, 3, 8
alors les piles de cartes seront successivement comme ceci (en gras le dernier élément
empilé) :
0 0 0 0 0 0 3 0 3
1 1 1 1 1 2 1 2 1 2 4 1 2 4 1 2 4 8
6 6 6 5 6 5 6 5 7 6 5 7 6 5 7 9 6 5 7 9 6 5 7 9 6 5 7 9
103
Au départ de l’algorithme Réussite(σ ) on dispose d’un tableau T de piles suffise-
ment grand, et qui ne contient que des piles vides (p vaut 0). Au cours de l’exécution de
l’algorithme Réussite(σ ), on empile des éléments de σ dans les piles de T . Pour poser
une nouvelle carte x il faut comparer la valeur de x avec les valeurs des têtes de piles.
Une suite extraite de σ est une suite formée d’éléments de σ pris dans le même ordre
qu’ils apparaissent dans σ , sans forcément choisir des éléments successifs. On consi-
dère les suites extraites croissantes de σ . Par exemple, 1, 5, 7, 8 et 0, 2, 3 sont des
suites extraites croissantes de σ = 6, 1, 5, 0, 7, 2, 9, 4, 3, 8. On note l(σ) la longueur
maximum des suites extraites croissantes de σ . Dans notre exemple l(σ) = 4.
3. Montrer que l(σ) minore le nombre de piles obtenues quel que soit la stratégie.
1 pt (Indication : il faut montrer que si a1 < . . . < ak est une suite extraite de σ
3 9 min alors il faut au moins k piles).
On veut montrer que si Réussite(σ ) forme p piles, alors il existe une suite extraite
croissante de σ de longueur p. À chaque fois qu’on pose une nouvelle carte x sur une
pile, sauf si on la pose sur la première pile, on dessine une flêche de x vers la carte du
dessus de la pile à sa gauche.
Voici ce que ça donne sur l’exemple, pour les six premières insertions.
0 0 0
1 1 1 1 1 2
6 6 6 5 6 5 6 5 7 6 5 7
0,5 pt
3 4 min 4. Compléter l’exemple précédent (sur votre copie).
5. En prenant un élément d’une pile et en suivant les flêches on obtient une suite
0,5 pt d’éléments de σ (en ordre inverse). Par exemple, 1 5 7. À quoi correspond
3 4 min une telle suite par rapport à σ ? (Justifier.)
0,5 pt 6. Montrer que si Réussite(σ ) a formé p piles, alors il existe une suite extraite
3 4 min croissante de σ de longueur p.
1 pt 7. Comment peut-on déduire de la question 3 et de la question précédente que
3 9 min p = l(σ) ? Que la stratégie du plus à gauche est optimale ?
Ainsi la stratégie du plus à gauche, qui peut s’écrire comme un algorithme Réussite(σ ),
permet de caluler la taille de la plus grande suite extraite croissante en O(N log N )
comparaisons.
On veut maintenant écrite un algorithme RassemblerPiles(T ) qui prend en entrée
le tableau T rendu par Réussite(T ) et rend le tableau trié des éléments de σ . Dans
chacune des p piles les éléments sont triés (le plus petit en haut de la pile), il suffit
donc d’interclasser les p piles d’éléments. On peut rendre l’interclassement plus effi-
cace, en observant qu’au départ les éléments du dessus des piles sont également bien
104
ordonnés :
Tête(T [0]) < Tête(T [1]) < . . . < Tête(T [p − 1]). (6.6)
Mais si on retire un élément du dessus d’une des piles, la propriété (6.6) n’est plus
forcément vraie.
8. Pouvez-vous donner une suite σ la plus courte possible, telle que depiler un 0,5 pt
élément de la première pile rend la suite des têtes de piles non croissante ?
3 4 min
9. Après un Dépiler(T [0]) tel que T [0] contient encore un élément, que faut-il faire 0,5 pt
pour réordonner les piles de manière à avoir de nouveau la propriété (6.6) ?
3 4 min
2 pt
10. Écrire l’algorithme RassemblerPiles(T ), en pseudo-code ou en C. 3 18 min
Au besoin on pourra faire appel à une fonction Echanger(T, i, j ) qui échange dans le
tableau T , la pile T [i] avec la pile T [j]. En C, on pourra considérer tous les arguments
auxilliaires éventuellement nécessaires. Par exemple on pourra considérer que le pre-
mier argument est le tableau de piles, que p est donné comme second argument, que le
tableau dans lequel ranger le résultat est donné comme troisième argument et que N
est donné comme quatrième argument : B(pile_t T[], int nb_piles, elements_t res[], int nb_elts)
105
6.4 Exercices du quatrième chapitre
Exercice 53 (Tas, septembre 2007).
1 pt Dans un tas max où se trouve l’élément maximum ? Où peut-on trouver l’élément mini-
2 6 min mum ? (Facile)
0.5 pt 2. En repartant du tas initial, retirer l’élément de clé maximale. Répondre en re-
3 4 min présentant le nouveau tas.
20
15 18
13 14 12 10
11
Exercice 56 (Indexation).
Dans le cours nous avons vu qu’un tas max est un arbre quasi-parfait ayant de plus
la propriété de dominance des tas : le parent est toujours plus grand que ses fils.
Nous avons également vu qu’un arbre quasi-parfait est efficacement représenté par un
tableau en mettant la racine à la première case.
20 19 10 7 15 12 3 6 5 1
Est-ce un tas ?
106
Un nœud du tas sera représenté par un indice du tableau. Étant donné un nœud i
nous voulons pouvoir obtenir son parent à l’indice parent(i), son fils gauche à l’indice
gauche(i) et son fils droit à l’indice droite(i).
2. En vous aidant de l’exemple, proposer des fonctions pour le calcul de ces in-
dices.
– Aucune pile n’est vide et il y a en tout N entiers répartis dans les piles (donc
p ≤ N)
– les sommets des piles vont décroissants :
– Dans chaque pile les entiers sont ordonnés du plus grand (au sommet) au plus
petit.
107
On souhaite réaliser l’interclassement des éléments des
p piles de manière à obtenir
N éléments dans l’ordre croissant.
un nouveau tableau contenant les
Pouvez vous donner un algorithme en O(N log N ) comparaisons pour ce pro-
blème ? (Justifier) Vous pouvez utiliser des algorithmes vus en cours et les résultats
de complexité sur ces algorithmes.
Indication : le tableau T est un tas max dont les éléments sont des piles et où les
clés sont les entiers au sommet des piles.
Exercice 59 (Indexation).
Dans le cours nous avons vu qu’un tas max est un arbre quasi-parfait ayant de plus
la propriété de dominance des tas : le parent est toujours plus grand que ses fils.
Nous avons également vu qu’un arbre quasi-parfait est efficacement représenté par un
tableau contenant les éléments donnés dans l’ordre du parcours en largeur de l’arbre.
Ainsi la racine est à l’indice racine() = 0 et le dernier élément à l’indice dernier() =
N − 1 (où N est le nombre total d’éléments). Lorsqu’il existe, le parent de l’élément
i−1
à l’indice i est à l’indice parent(i) = ⌊ 2 ⌋. Lorsqu’ils existent, le fils gauche de
l’élément d’indice i est à l’indice gauche(i) = 2i+1 et le fils droit à l’indice droite(i) =
2i + 2. On introduit également les fonctions suivant(i) = i + 1 et précédant(i) =
i − 1 qui permettent de se déplacer respectivement à l’élément suivant et à l’élément
précédant dans l’ordre du parcours en largeur de l’arbre qui est ici le même que l’ordre
des indices du tableau.
2. Même question mais cette fois-ci, on change également l’ordre des éléments :
les éléments sont maintenant rangés dans le tableau dans l’ordre inverse du
parcours en profondeur (le dernier élément est à l’indice r − N + 1).
Exercice 60 (Biprocesseur).
Nous utilisons ici les files de priorités pour gérer l’ordonnancement de processus sur
une machine biprocesseur. Les processus arrivent alternativement aux fils d’attentes
f0 et f1 des deux processeurs P0 et P1 . Chaque processus possède une charge (qui
représente un temps de travail) et une valeur d’attente. Plus l’attente est faible plus le
processus est prioritaire.
Chaque processeur traite en un tour le processus de plus haute priorité (attente la
plus faible) puis diminue sa charge d’une constante c et augmente son attente de c. Si
la charge d’un processus est nulle il est retiré de sa file d’attente.
Le traitement s’effectue en parallèle sur les deux processeurs tour par tour. À la
fin d’un tour de traitement, si les deux files d’attente ont une différence en nombre de
processus supérieure ou égale à deux, il faut rééquilibrer en faisant passer un proces-
sus d’une file à l’autre. On choisit pour cela le processus ayant l’attente la plus faible
de la plus longue file et on le fait passer dans la file la plus courte.
Lorsque deux processus d’une même file ont même temps d’attente c’est le pre-
mier arrivé qui a la priorité (quelle que soit la file d’arrivée).
108
1. Pour c = 1, simuler l’exécution du biprocesseur sur la liste de processus (pid,
charge, attente) suivante : (p1 , 2, 0), (p2 , 3, 1), (p3 , 1, 2), (p4 , 1, 2), (p5 , 5, 2), (p6 , 1, 4), (p7 , 1, 5)
Représenter les deux files sous forme d’arbres (tas min) après chaque tour.
On suppose qu’il y a au plus N processus en tout dans les deux files d’attente, ce
qui nous permet de représenter ces deux files de priorité comme deux tas (min) dans
un même tableau. Les définitions de types seront les suivantes :
Exercice 61.
Combien y a t’il de formes d’arbres binaires différents à (respectivement) 1, 2, 3, 4
nœuds ? Les dessiner (sans donner de contenu aux nœuds).
Pour n fixé quelconque donner un exemple d’arbre binaire de hauteur majorée par
log n + 1, et un exemple d’arbre binaire de hauteur n.
Exercice 62.
Écrire une fonction Taille(x) prenant un arbre binaire et rendant le nombre de ses
éléments.
Exercice 63.
Écrire une fonction Hauteur(x) prenant un arbre binaire et rendant sa hauteur, c’est à
dire le nombre d’éléments contenus dans la plus longue branche.
109
Exercice 65 (Insertion / suppression ABR).
Former un arbre binaire de recherche en insérant successivement et dans cet ordre
les éléments : 10, 7, 3, 9, 11, 5, 6, 4, 8 (répondre en représentant l’arbre obtenu). Sup-
primer l’élément 7. (répondre en représentant le nouvel arbre. Il y a deux réponses
1,5 pt correctes possibles, selon la variante choisie pour l’algorithme de suppression, n’en
2 9 min donner qu’une seule).
Exercice 67.
Écrire une fonction Hauteur(x) prenant un arbre binaire et rendant sa hauteur, c’est
1,5 pt à dire le nombre d’éléments contenus dans la plus longue branche. Vous pouvez faire
2 9 min appel à des fonctions Parent(x), Gauche(x), Droite(x).
Rappel. un nœud d’un arbre binaire contient : un élément, une référence vers le
nœud parent, une référence vers le nœud fils gauche et une référence vers le nœud fils
droit. S’il n’y a pas de nœud parent, fils gauche ou fils droit, les références prennent
la valeur spéciale « nulle ». L’arbre est donné par une référence vers son nœud racine.
Type en C :
Exercice 68.
Dans les deux exemples d’arbres binaires de recherche de la figure 6.3 :
1. où peut-on insérer un élément de clé 13 ?
2. comment peut-on supprimer l’élément de clé 14 ?
Les rotations des arbres binaires sont données dans la figure 6.4. Elles se lisent
comme ceci. Une rotation à droite de centre x consiste en : prendre l’élément a de x,
le sous-arbre droite E de x, la racine y du sous-arbre gauche de x, l’élément b contenu
dans y , et C et D les deux sous-arbres gauche et droite de y ; remplacer a par b dans
x, remplacer le sous-arbre gauche de x par C , et le sous-arbre droite de x par un arbre
110
12 14
3 14 5 18
2 5 15 2 9 15 19
de racine contenant a (on utilise y pour des raisons d’implantation) et dont les sous-
arbres gauche et droite sont respectivement D et E . La rotation à gauche de centre x
est l’opération réciproque.
Avec cette manière d’écrire les rotations la référence de x à son parent n’a pas
besoin d’être mise à jour. Il est assez standard de trouver une version qui échange la
place de x et de y plutôt que d’échanger leurs éléments mais nous ne l’utilisons pas
ici.
x x
a rotation_droite(x) b
y y
b E rotation_gauche(x) C a
C D D E
Figure 6.4 – Rotations gauche et droite. Dans cette version les éléments a et
b sont échangés entre les nœuds x et y mais x garde sa place dans l’arbre qui
le contient.
3. Sur le premier exemple de la figure 6.3, faire : une rotation à droite de centre
le nœud de clé 3 ; puis une rotation à gauche de centre le nœud de clé 14.
4. Sur le second exemple de la figure 6.3, à l’aide de rotations dont vous préciserez
le sens et le centre, amener le nœud de clé 9 à la racine.
5. Démontrer que toute rotation préserve la propriété d’être un arbre de recherche.
6. Écrire l’algorithme de rotation à droite en C.
7. Écrire un algorithme permettant de remonter à la racine n’importe quel nœud
d’un arbre binaire de recherche, à l’aide de rotations.
111
1,5 pt correctes possibles, selon la variante choisie pour l’algorithme de suppression, n’en
2 9 min donner qu’une seule).
Exercice 71.
On peut afficher les éléments d’un ABR de taille n en ordre trié en un temps O(n).
1. Expliquer comment et argumenter sur le temps d’exécution.
2. Est-ce que la propriété de tas permet d’afficher en ordre trié et en temps
O(n)
les éléments d’un tas de taille
n ? Argumenter. Indication : on peut planter (for-
mer) un tas de n éléments en un temps Θ(n).
112
est rendu en place). Le principe de fonctionnement est le suivant. Si le tableau
contient un ou zéro élément, il n’y a rien à faire.
Partition Si le tableau contient plus d’un élément, on choisit (au hasard ou
bien en prenant le premier élément du tableau) un élément du tableau,
d’indice i, appelé pivot et on partitionne le tableau autour de cet élé-
ment. Plus précisément, la partition fait en sorte que, après partition,
le pivot est à l’indice p, les éléments plus petits que le pivot sont (dans
le désordre) aux indices inférieurs à p et les éléments plus grands que
le pivot sont (dans le désordre) aux indices supérieurs à p. Le pivot est
donc à sa place définitive.
pivot à l’indice i
Tableau T
| {z } | {z
Éléments plus petits que le pivot Éléments plus grands que le p
Appels récursifs On relance le tri sur chacun des deux sous-tableaux obte-
nus par partition : le tableau des éléments d’indices inférieurs à p et le
tableau des éléments d’indices supérieurs à p.
Exercice 73.
Dans cet exercice, on va mettre en œuvre un algorithme inspiré du tri rapide pour
réaliser la fonction Sélection(T, k). L’idée est qu’il n’est pas besoin de trier tout le
tableau pour trouver l’élément de rang k.
On suppose que les indices du tableau commencent à 1. La remarque importante
est que le pivot est l’élément de rang p (p + 1 si les indices commencent à zéro). Si
après partition on trouve un p égal à k, alors l’élément de rang k est le pivot.
On suppose que l’on a une fonction Partitionner(T, i) qui effectue la partition au-
tour de l’élément d’indice i (pivot) et renvoie l’indice p du pivot après partition.
1. Après partition autour d’un pivot où chercher l’élément de rang k lorsque k <
p ? Et lorsque k > p ? Décrire simplement le principe d’un algorithme récur-
sif, basé sur la partition, réalisant Sélection(T, k). (A t-on besoin de faire deux 1.5 pt
appels récursifs comme dans le tri rapide ?)
3 13 min
113
Rang dans un arbre binaire de recherche avec comptage
des descendants
50 | total = 6
20 | total = 3 70 | total = 2
Dans la suite, on suppose que les éléments de A sont stockés dans un ABR
enrichie par ce comptage, de racine r .
Exercice 74.
Écrire un algorithme (C ou pseudo-code) réalisant la fonction Sélection(r, k). Donner
1.5 pt en fonction de la hauteur h de l’arbre, un majorant asymptotique de son temps d’exé-
3 13 min cution.
114
Fonction Rechercher(r, c )
Entrées : Le nœud racine r d’un arbre binaire de recherche et une clé
c.
Sorties : Le nœud de l’arbre contenant l’élément de clé c s’il en existe
un, ou le nœud vide N sinon.
si EstVide(r) alors
retourner N ;
sinon
si c = Clé(r) alors
retourner r ;
sinon
si c < Clé(r) alors
retourner Rechercher(Gauche(r), c) ;
sinon
retourner Rechercher(Droite(r), c) ;
Exercice 75.
Pour réaliser les ABRs avec comptage des descendants, il faut adapter les fonctions
d’ajout et de suppression d’un élément. Expliquer les modifications à apporter. Et pour 1.5 pt
les rotations ?
3 13 min
Exercice 76.
Soit un tableau t de n entiers tous différents. Quel est le rapport entre :
– l’arbre des appels récursifs de la fonction de tri du quicksort lorsque le pivot est
toujours choisi dans la première case et que partitionner conserve dans chaque
sous-tableau l’ordre des éléments du tableau d’origine ;
– et les arbres binaires de recherche ?
Exercice 77.
Notre but est de montrer que la hauteur d’un arbre rouge noire est logarithmique en
son nombre de nœuds.
Rappel. Soit x un nœud d’un arbre rouge noir. On appelle hauteur noire de x,
notée Hn (x), le nombre de nœuds noirs présents dans un chemin descendant de x
(sans l’inclure) vers une feuille de l’arbre.
1. Dans l’arbre rouge noir donné en figure 6.6, que valent Hn (30), Hn (20), Hn (35), Hn (50) ?
Montrer que, pour un nœud x quelconque dans un arbre rouge noir, le sous-arbre
enraciné à x contient au moins 2Hn (x) − 1 nœuds internes.
En déduire qu’un arbre rouge noir comportant n nœuds internes a une hauteur au plus
égale à 2 log(n + 1).
Exercice 78.
Est-il possible de colorier tous les nœuds de l’arbre binaire de recherche de la figure 78 1 pt
pour en faire un arbre rouge noir ?
3 9 min
115
30
20 40
10 25 35
3 15 21 28 32 37 N
N N N N N N N N N N N N
Figure 6.6 – Un exemple d’arbre rouge noir
30
15 40
10 25 N 50
N N 20 N N N
N N
Exercice 79.
1 pt Pour chaque arbre de la figure 6.7, dire s’il s’agit d’un arbre rouge noir. Si non, pour-
2 6 min quoi ?
116
40
20 60
N 30 N N
N N
(a)
41
31 61
11 N N N
N N
(b)
32
22 62
12 10 N N
N N N N
(c)
33 ROUGE NOIR
23 N
13 N
N N
(d)
117
Chapitre 7
118
7.1 Premier chapitre
Correction de l’exercice 1.
1. Factorielle de son argument.
2. int Fibonacci(n)
{
if (n < 3) /* cas de base */
{
return 1;
}
return Fibonacci(n - 1) + Fibonacci(n - 2); /* /!\ double appel récursif */
}
Vous pouvez en profiter pour dire rapidement que ce genre de doubles ap-
pels récursifs prennent du temps en montrant par exemple que pour calculer
Fibonacci(n) il faut revenir Fibonacci(n) fois au cas de base (puisque le résul-
tat est calculé comme une somme 1 + 1 + . . . + 1 où les 1 proviennent du cas de
base, n’hésitez pas à dessiner un arbre). Et la suite croît très vite, pour n = 31
on est déjà au delà du million.
3. On utilise pgcd(a, b) = a si b = 0 et pgcd(a, b) = pgcd(b, a mod b).
unsigned int pgcd(unsigned int a, unsigned int b){
if (a < b) return pgcd(b, a);
if (b == 0) return a;
return pgcd(b, a % b);
}
Correction de l’exercice 2.
Note : c’est le John McCarthy du Lisp, pas celui de la terreur rouge.
Prenons 91 comme exemple (ce n’est pas le meilleur choix mais un des plus na-
turels au regard de l’énoncé) et notons f la fonction. Comme 91 < 100 le résul-
tat de f (91) sera f (f (91 + 11)) = f (f (102)). Mais f (102) = 92 donc f (91) =
f (f (102)) = f (92). Maintenant f (92) = f (f (92 + 11)) = f (f (103)) = f (93) et
119
par le même raisonnement f (93) = f (94) = . . . = f (99) = f (f (110)) = f (100) =
f (f (111)) = f (101) = 91. Donc f (91) = . . . = f (100) = 91. Finalement, pour
90 on a f (90) = f (f (101)) = f (91) = 91. Voyons ce que ça donne pour 89. On a
f (89) = f (f (100)) = f (91) = 91.
On conjecture que f (n) vaut 91 pour tout n ≤ 100 (y compris les négatifs).
Commençons par prouver plus proprement que f (n) = 91 pour les onze entiers n
compris entre 90 et 100.
On montre alors par récurrence sur k que lorsque 90−k ×11 ≤ n ≤ 100−k ×11,
f (n) = 91. Ceci démontrera que f (n) = 91 pour (n ≤ 100).
Le cas de base k = 0 est démontré. Supposons l’assertion vraie pour k on montre
qu’elle l’est encore pour k + 1. Soit n un entier dans l’intervalle [90 − (k + 1) ×
11, 100 − (k + 1) × 11]. Alors n ≤ 100 donc f (n) = f (f (n + 11)). Mais f (n + 11)
est dans l’intervalle [90 − k × 11, 100 − k × 11] donc par hypothèse de récurrence
f (n + 11) = 91 et ainsi f (n) = f (91) qui est égal à 91 (cas de base). Finalement le
résultat est prouvé pour tous les intervalles [90 − k × 11, 100 − k × 11] et leur union
([90, 100] ∪ [79, 89] ∪ [68, 78] ∪ . . .) correspond à l’ensemble des entiers inférieurs à
100.
Correction de l’exercice 3.
1. Facile :
deplacerdisque(p1, p2);
deplacerdisque(p1, p3);
deplacerdisque(p2, p3);
120
void deplacertour(unsigned n, piquet_t p1, piquet_t p2, piquet_t p3){
if (n > 0){
/* tour(n) = un gros disque D et une tour(n - 1) */
deplacertour(n - 1, p1, p3, p2); /* tour(n - 1): p1 -> p2 */
deplacerdisque(p1, p3); /* D: 1 -> 3 */
deplacertour(n - 1, p2, p1, p3); /* tour(n - 1): p2 -> p3 */
}
}
Correction de l’exercice 4.
1. Le gain maximum en D est la valeur en D plus le maximum entre : le gain
maximum en A ; le gain maximum en B et le gain maximum en A. On peut
oublier de considérer le gain en A, puisqu’avec des valeurs non négatives sur
chaque case, c’est toujours au moins aussi intéressant, partant de A, de passer
par B ou C pour aller en D plutôt que d’y aller directement.
2. On considère que les coordonnées sont données à partir de zéro.
int robot_cupide(int x, int y){
/* Cas de base */
if ( (x == 0) && (y == 0) ) then return Damier[x][y];
121
/* Cas général x, y > 0 */
return Damier[x][y] + max(robot_cupide(x - 1, y),
robot_cupide(x, y - 1));
}
On retrouve alors le triangle de Pascal à une rotation près (il faut prendre
comme sommet du triangle le coin inférieur droit du tableau). Rien d’étonnant
du fait de l’identité binomiale :
! ! !
n n−1 n
= + . (7.1)
p p−1 p−1
Une version itérative stockant les gains max dans un nouveau tableau (gain[n][m]
variable globale) permet d’éviter ces répétitions inutiles.
gain[0][0] = Damier[0][0];
/* Bord Nord */
for (i = 1; i <= x; i++) {
gain[i][0] = Damier[i][0] + gain[i - 1][0];
}
/* Bord Ouest */
for (j = 1; j <= y; j++) {
gain[0][j] = Damier[0][j] + gain[0][j - 1];
}
/* Autres cases */
122
for (j = 1; j <= y; j++) {
for (i = 1; i <= x; i++) {
gain[i][j] = Damier[i][j]
+ max(gain[i - 1][j], gain[i][j - 1];
}
}
// affiche(x, y); <--- pour afficher...
return gain[x][y];
}
123
Correction de l’exercice 5.
1. Une solution :
!2
2 2
2 2
2
32+256 2 2
x = x × x32
124
double exprapide(double x, unsigned n){
double acc = 1;
while ( n != 0 ){
if ( n % 2 ) acc = acc * x;
n = n / 2; // <-- Arrondi par partie entière inférieure
x = x * x;
}
return acc;
}
multiplications. Alors que, avec l’exponentiation rapide on fait (au mieux) six
multiplications.
Correction de l’exercice 6.
1. Une solution :
125
} /* fin du while :
On sort avec j = k sans avoir regardé la couleur de l’élément à
cette place. Aucune importance. */
}
2. Une solution :
drapeau3(tableau_t t){
int i, j, k;
i = 0; /* Les éléments 0, ..., i - 1 sont rouges */
j = 0; /* Les éléments i, ..., j - 1 sont verts */
k = taille(t) - 1; /* Les éléments k + 1, ..., n - 1 sont bleus */
while ( j <= k ){
switch ( couleur(t, j) ){
case 0: /* ----------- rouge ---------------------------------*/
/* t[j] doit être mis avec les rouges. */
if ( i < j ){ /* Si il y a des verts */
echange(t, i, j); /* on doit le deplacer, */
} /* sinon il est à la bonne place. */
i++; /* Il y a un rouge de plus. */
j++; /* Le nombre de verts reste le même. */
break;
case 1: /* ----------- vert --------------------------------- */
j++; /* t[j] est à la bonne place. */
break;
case 2: /* ----------- bleu --------------------------------- */
echange(t, j, k); /* t[j] est mis avec les bleus. */
k--; /* Le nombre de bleus augmente. */
}
}
}
Correction de l’exercice 7.
Au minimum, il faut bien se rendre chez notre ami, donc parcourir une distance de
n immeubles, ce qui donne bien Ω(n). Ceci suppose que l’on sache dans quel direction
partir. Autrement dit, même si on suppose un algorithme capable d’interroger un oracle
qui lui dit où aller, la complexité minimale est Ω(n).
Nous n’avons ni oracle ni carnet d’adresses. Pour être sûr d’arriver, il faut passer
devant l’immeuble numéro n et devant l’immeuble numéro −n. On essaye différents
algorithmes.
126
– choisir un certain numéro k
– parcourir les numéros de 0 à k, puis de k à −k puis de −k à 0.
Le choix d’un parcours particulier est donc donné par la suite des valeurs de k. Le
temps de parcours d’une k-étape est de 4k.
Avec cette idée les étudiants doivent arriver à émettre une proposition de parcours
et à estimer la distance totale. Voici les deux parcours qu’il faudra nécessairement
traiter.
Si les valeurs successives de k sont tous les entiers jusqu’à n, la sommation donne
2n(n + 1). On retrance le dernier retour en zéro qui est inutile, ce qui donne : 2n(n +
1) − n = 2n2 + n = Θ(n2 ).
On fait trop souvent demi-tour.
Si on ne fait demi-tour qu’à chaque fois qu’une puissance de 2 est atteinte, les
valeurs successives de k sont les 2i pour i allant de 0 à ⌈log n⌉, alors le parcours total
sera de :
⌈log n⌉
X
4 2i − n = 4(2⌈log n⌉ − 1) − n = Θ(n).
0
Bien entendu il faut développer un peu pour convaincre les étudiants de cette
dernière égalité.
2n−1 2n
X (2n − 1)(2n) X (2n + 1)(2n)
i= respectivement i=
i=1
2 i=1
2
127
En dépliant, on a :
24 +23 +22
23 +22 +21
22 +21 +20 +u0
k−1
X
uk = 2k+1 + 2 × 2k + 3 × ( 2 i ) − 2 1 − 2 × 2 0 + u0
i=0
uk = 7 × 2k − 4 = 7n − 4
Ceci pour n = 2k . Pour 2k ≤ n ≤ 2k+1 , le temps mis sera majoré par 7 × 2k+1 − 4
k
expression elle-même majorée par 7 × (2 × n) − 4 puisque 2 ≤ n. Ce qui donne un
temps mis pour aller en (n, −n) majoré par 14n − 4.
Donc la distance parcourue est strictement majorée par 14 × n ce qui montrer que
la distance parcourue est cette fois en O(n). Conclusion, ce dernier algorithme est en
Θ(n) et, en complexité asymtotique c’est un algorithme optimal. Si notre ami habite
très loin on a économisé quelques années de marche.
Une alternative peut être de doubler la distance parcourue à chaque demi tour : 1,
−1, 3, −5, 11, ce parcours forme une suite (uk )k∈N de terme général :
i=k
X (−2)k − 1
uk = (−2)i = .
i=0
−2 − 1
Correction de l’exercice 8.
Pas de correction.
Correction de l’exercice 9.
0.5 pt
3 4 min 1. On a f (n) = O(n), f (n) = O(n log n), f (n) 6= Θ(n2 ) et f (n) = Ω(log n).
+ +
deux égalités justes = 0, 25, trois 0, 25 , une 0
128
2. En pire cas, comme en moyenne les tris par comparaison font (au moins) Ω(n log n) 0.5 pt
comparaisons.
3 4 min
– f = Ω(g) ssi
– f = Ω(g) ssi
129
Pn Pn
2. Oui. On a log(n!) = i=1 log i ≤ i=1 log n = n log n pour tout n ∈ N.
Ainsi, prendre c = 1 et n0 = 0 convient.
3. Non. Il faudrait quelog(n!) = O(n2 ) (ce qui est vrai) et que log(n!) = Ω(n2 ).
Mais on n’a pas log(n!) = Ω(n2 ). En effet, supposons que ce soit le cas pour un
certain n0 et un certain c et montrons qu’il y a contradiction. À partir du rang
Pn
n0 on a cn2 ≤ log(n!) = i=1 log i ≤ n log n. D’où cn ≤ log n pour tout
n ≤ n0 avec c > 0. Ce qui est impossible puisque limn−>+∞ logn n = 0.
2. On montre que c’est faux, par l’absurde. Supposons que ce soit vrai, alors :
2 × n ≤ log c + n
ce qui donne n ≤ log c
L’ensemble des entiers naturels n’étant pas borné et c étant une constante, ceci
est une contradiction.
n(n + 1)
∃c > 0, ∃n0 ∈ N, ∀n ≥ n0 , ≤ cn2 .
2
n2 n2 +n n(n+1)
Pour n ≥ 1, 2
≥ n
2
donc n2 ≥ 2
= 2
. Ainsi c = 1 et n0 = 1
conviennent.
n(n+1)
Montrons que 2
= Ω(n2 ) c’est à dire que :
n(n + 1)
∃c > 0, ∃n0 ∈ N, ∀n ≥ n0 , ≥ cn2 .
2
130
n 1 2 n2 +n n(n+1) 1
Pour n ≥ 0, 2
≥ 0 donc 2
n ≤ 2
= 2
. Ainsi c = 2
et n0 = 0
conviennent.
2. Non. Supposons que n2 = Ω(2n ) alors, par définition, on aurait un réel positif
c et un entier n0 tels que
∀n ≥ n0 , n2 ≥ c2\ n.
Ou encore :
2n 1
∀n > n0 , ≤ .
n2 c
2n
Mais limn→∞ n2
= +∞, on ne peut donc pas borner par une valeur à partir
d’un certain rang. Contradiction.
3. Oui. Montrons que :
n i
X 2
∃c > 0, ∃n0 ∈ N, ∀n ≥ n0 , ≤ c.
i=0
3
Il s’agit de la somme de termes positifs donc les sommes partielles seront in-
férieures à la somme infinie. Il ne reste qu’à montrer que la somme infinie est
bornée et à prendre cette borne comme valeur pour c (et 0 pour n0 ).
On a
n i
X 2 q n+1 − 1 2
= où q =
i=0
3 q−1 3
2 n+1
Et limn→∞ 3
= 0 donc
∞ i
X 2 0−1
= 2 = 3.
i=0
3 3
−1
Ainsi c = 3 et n0 = 0 conviennent.
Supposons l’existence d’un tel c et d’un tel n0 . Alors pour n’importe quel n ≥ n0
on doit avoir log n ≥ 1c . Ceci est en contradiction avec le fait que lim+∞ log n =
+∞.
131
3. Réponse oui. Par définition, on a log(n!) = O(n log n) si et seulement si :
∃c > 0, ∃n0 ∈ N, ∀n ≥ n0 , 0 < log(n!) ≤ cn log n.
Soient c = 1 et n0 = 0. Supposons n ≥ n0 = 0. On a n! ≤ nn donc par
n
croissance du log, log(n!) ≤ log(n ) = n log n. Ce qui montre bien que
log(n!) = O(n log n).
4. Réponse Oui. Le meilleur cas minore la moyenne donc un minorant asympto-
tique du meilleur cas est également un minorant asymptotique de la moyenne.
De même le pire cas majore la moyenne donc un majorant asymptotique de
la moyenne est également un majorant asymptotique de la moyenne. Ainsi la
moyenne est en Ω(f (n)) et en Γ(f (n)) c’est à dire bien en Θ(f (n)).
(2k)! ≥ (2k) × . . . × k ≥ k × . . . × k ≥ kk
| {z }
k+1 termes
132
Solution 2 On a (faire un dessin)
n
X Z n
log(n!) = log k ≥ log tdt.
k=2 1
n+1
Mais lorsque 1 ≤ k ≤ n, k(n + 1 − k) est maximal pour k = 2 et minimal pour
k = 1 et k = n (on raisonne sur (a + b)(a − b) avec a = n+1
2
et b = k − a).
Ainsi pour tout 1 ≤ k ≤ n, log(k(n + 1 − k)) ≥ log(n).
On en déduit qu’à partir du rang n = 1 :
n log n
log(n!) ≥ .
2
Ce qui montre bien que log(n!) = Ω(n log n).
133
2. On fait exactement taille(tab) − 1 = N − 1 appels.
3. On cherche le minimum du tableau et si il n’est pas déjà à la première
case, on échange sa place avec le premier élément. On recommence
avec le sous-tableau commençant au deuxième élément et de longueur
la taille du tableau de départ moins un. ça s’écrit en itératif comme ceci :
134
la ligne 5 on place l’élément e d’indice n + j à l’indice n (si j vaut zéro
il y est déjà on ne fait donc pas d’échange). L’élément e′ qui était à cette
place est mis à la place désormais vide de e. Ainsi, puisqu’on procède
par échange, les éléments du tableau restent inchangés globalement.
Seul leur ordre change. À la fin de l’étape n est incrémenté. Comme
l’élément que l’on vient de placer à l’indice n est plus grand que les élé-
ments précédents et plus petits que les suivants, l’invariant de boucle
est bien vérifié à l’étape suivante.
135
Donc N − 1 appels pour un tableau de taille N . On fait au plus un
échange à chaque appel et le pire et le meilleur cas sont réalisés comme
précedemment. Cela donne entre 0 et N − 1 échanges.
7. Réponse oui (il faut relire les démonstrations de correction). De plus
on remarque qu’avec la manière dont a été écrite notre recherche du
minimum, le tri est stable. Un tri est dit stable lorsque deux éléments
ayant la même clé de tri (ie égaux par comparaison) se retrouvent dans
le même ordre dans le tableau trié que dans le tableau de départ. Au
besoin on peut toujours rendre un tri stable en augmentant la clé de tri
avec l’indice de départ. Par exemple en modifiant la fonction de compa-
raison de manière à ce que dans les cas où les deux clés sont égales on
rende le signe de k − j.
/* ------------------------------------------------------------------------ */
/* Interclassement de deux tableaux avec écriture dans un troisième tableau */
/* ------------------------------------------------------------------------ */
void interclassement(tableau_t t1, tableau_t t2, tableau_t t){
int i, j, k;
i = 0;
j = 0;
k = 0;
for (k = 0; k < taille(t1) + taille(t2); k++){
if ( j == taille(t2) ){/* on a fini de parcourir t2 */
for (; k < taille(t1) + taille(t2); k++){
t[k] = t1[i];
i++;
}
break; /* <-------- sortie de boucle */
}
if ( i == taille(t1) ){/* on a fini de parcourir t1 */
for (; k < taille(t1) + taille(t2); k++){
t[k] = t2[j];
j++;
}
break; /* <-------- sortie de boucle */
}
if ( t1[i] <= t2[j] ){/* choix de l’élément suivant de t : */
136
t[k] = t1[i]; /* - dans t1; */
i++;
}
else {
t[k] = t2[i]; /* - dans t2. */
j++;
}
}
}
137
comme suit. Dans t1 on met tous les éléments de t d’indices pairs et
dans t2 on met tous les éléments d’indices impairs. Cette entrée maxi-
mise le nombre d’alternance, qui est alors égal à 2n − 1. Par le lemme,
n’importe quel algorithme fera alors au minimum 2n − 1 comparaisons
sur cette entrée (et produira t). Notre algorithme aussi. Donc du point
de vue du pire cas et pour n = m notre algorithme est optimal. Des
résultats en moyenne ou pour les autres cas que n = m sont plus dif-
ficiles à obtenir pour le nombre de comparaisons. On peut remarquer
que pour n = 1 et m quelconque notre algorithme n’est pas optimal en
nombre de comparaisons (une recherche dichotomique de la place de
l’élément de t1 serait par exemple plus efficace).
Par contre, il est clair que le nombre minimal d’affectations sera tou-
jours n + m, ce qui correspond à notre algorithme.
1. Code C :
2. La seule hypothèse est, qu’au cours de l’exécution du tri grome (sur une
entrée non spécifiée), à une certaine étape, un échange à eu lieu. Soit t′
le tableau juste avant cet échange, t′′ le tableau juste après cet échange,
et i0 la valeur de la variable i au moment de l’échange. Un échange ne
se produit que lorsque t[i] > t[i + 1] et il s’agit d’un échange entre t[i]
et t[i + 1]. Ainsi, dans t′ , on avait t′ [i0 ] < t′ [i0 + 1] et t′′ est égal à t′
138
dans lequel on a procédé à l’échange entre les éléments d’indices i0 et
i0 + 1. Cet échange élimine exactement une inversion. En effet :
– dans t′ , (i0 , i0 + 1) est une version, pas dans t′′
– les autres inversions sont préservées :
– lorsque i < j et i, j tous deux différents de i0 et i0 + 1, (i, j) est
une inversion dans t′ ssi c’est une inversion dans t′′ ;
– lorsque i < i0 alors : (i, i0 ) est une inversion dans t′ ssi (i, i0 + 1)
est une inversion dans t′′ et (i, i0 + 1) est une inversion dans t′ ssi
(i, i0 ) est une inversion dans t′′ ;
– lorsque i0 + 1 < j alors : (i0 , j) est une inversion dans t′ ssi (i0 +
1, j) est une inversion dans t′′ et (i0 + 1, j) est une inversion dans
t′ ssi (i0 , j) est une inversion dans t′′ ;
– et ceci prend en considération toutes les inversions possibles dans t′
et t′′ .
3. Nous venons de voir que tout échange au cours du tri gnome élimine
exactement une inversion. Le nombre d’échanges effectués au cours du
tri gnome de t est donc la différence entre le nombre d’inversions au
départ, f (n), et le nombre d’inversions à fin du tri. Mais le tableau final
est trié et un tableau trié ne contient aucune inversion. Donc le nombre
d’échange est simplement f (n).
Le nombre d’échanges est égal au nombre d’inversions dans le tableau
inital. Donc le nombre moyen d’échanges sur des tableaux de taille n
n(n−1)
est 4 .
a<b
oui non
b<c a<c
a, c, b c, a, b b, a, c impossible b, c, a c, b, a
139
2. Le meilleur cas du tri bulle se réalise lorsque la première passe est
sans échange, c’est à dire sur un tableau déjà ordonné, par exemple :
0, 1, . . . , N − 1. Ce tri fait alors C(N ) = N − 1 comparaisons (entre 0
et 1 puis 1 et 2, . . . , N − 2 et N − 1).
3. Il n’est pas possible qu’un algorithme fasse moins de N − 1 compa-
raisons en meilleur cas. En effet, on sait (cours) que pour trouver le
maximum dans un tableau de N éléments, quel que soient les éléments
du tableau, il faut faire au moins N − 1 comparaisons. Or une fois que le
tableau est trié on peut trouver ce maximum sans faire de comparaison
supplémentaire. Il n’est donc pas possible qu’on ai fait moins de N −1
comparaisons au cours du tri.
N ! = N × . . . × 3 × 2 ×1 > 2 × . . . × 2 × 2 ×1 = 2N −1
| {z } | {z }
N −1 termes N −1 termes
1. L’algo en C :
140
3. Pour réaliser l’algorithme il faut plusieurs fois trouver le minimum et le
maximum entre deux entiers a et b, et ceci se fait en une seule compa-
raison (si a < b alors le minimum est a et le maximum est b sinon c’est
l’inverse). On le fait une fois entre T [0] et T [1]. Puis pour chaque paire
suivante, on fait une comparaison pour trouver le minimum (MinLocal)
et le maximum (MaxLocal) dans la paire plus une comparaison pour trou-
ver le minimum entre Minimum et MinLocal et encore une autre compa-
raisons pour trouver le maximum entre Maximum et MaxLocal. Au final
cela fait une comparaison pour la première paire et trois comparaisons
pour les chacune des N/2 − 1 paires suivantes, c’est à dire 3N/2 − 2
comparaisons.
141
y = x - t[i];
j = recherche_dichotomique(t, taille, y); /* indice de y dans t, -1 sin
if (0 <= j) {/* y a été trouvé à l’indice j */
if ((i != j) /* i, j sont déjà distinc
|| ((0 < i) && (t[i - 1] == y)) /* j = i mais j = i - 1 convie
|| ((i + 1 < taille) && (t[i + 1] == y))) /* ou j = i + 1 convie
{
return TRUE;
}
}
}
return FALSE;
}
142
Correction de l’exercice 29.
143
de rang N (où N est la taille du tableau initial), alors chaque partition-
nement laisse inchangé le tableau et élimine de la zone de recherche
un élément à chaque étape (le pivot). Le temps d’exécution est alors la
PN N (N +1)
somme des temps des partitionnements : i=1 i = 2 plus N fois
un temps ne dépendant pas de N , c’est à dire finalement un temps en
Θ(N 2 ).
3. Si T est de taille N = 2m , qu’il faut attendre la taille 1 pour terminer
et que pour chaque appel récursif la taille du tableau est divisée par
Pm
i
deux alors la somme des temps des partitionnement est : i=0 2 =
m+1
2 −1 = 2N −1 à laquelle il faut ajouter un temps constant autant de
fois qu’il y a de termes dans cette somme (m+1 fois, c’est à dire log N ).
Ainsi le temps d’exécution dans ce cas est 2N − 1 + log N = Θ(N ).
4. En généralisant le raisonnement précédent, sur un tableau de taille N
le temps d’exécution des partitionnement sera : P (N ) = N + rN +
r2 N + . . . + rm N plus ou moins 1 où m est le nombre de fois où il faut
multiplierN par r pour trouver 1 : m = −lnlnNr (qui est en Θ(log N )).
m
Pour simplifier on peut supposer que N = 1r . Ainsi on obtient un
temps d’exécution égal à
m
!
X
i
E(N ) = N r + c log N
i=0
1−r m+1
Comme 0 < r < 1, 1−r tend vers une constante et E(N ) est en
Θ(N ).
144
if (aux == NULL) perror("calloc aux trilin1");
for (j = 0; j < n; j++) aux[t[j]]++; // décompte
k = 0;
for (j = 0; j < n; j++) {
while ( aux[j] > 0 ) {
t[k] = j;
k++;
aux[j]--;
}// fin du while
}// fin du for
free(aux);
}
145
}
3. Tant que l’espace des clés est linéaire en n l’algorithme sera linéaire.
Dans le cas général, l’espace des clés est non borné on ne peut donc pas
appliquer cette méthode.
146
le tri auxilliaire, triaux est stable si t[j] et t[k] ont même digits d’indice
i + 1 alors ils sont rangés dans le même ordre qu’à l’étape précédente.
Mais par hypothèse à l’étape précédente ces deux éléments étaient ran-
gés selon des ci croissants, il sont donc rangés par ci+1 croissants. Si
les digits d’indices i + 1 de t[j] et t[k] différent alors celui de t[k] est
le plus grand et ainsi ci+1 (t[j]) < ci+1 (t[k]). Dans les deux cas t[j] et
t[k] sont rangés par ci+1 croissants. Ainsi l’hypothèse est vérifiée après
chaque étape de boucle.
Lorsque i = k − 1, pour tout indice j du tableau ci (t[j]) = t[j] ainsi le
tableau est bien trié à la fin du tri gnome.
La récurrence est faite sur i qui va de 0 à k −1 (on peut aussi considérer
qu’elle porte sur k ). La stabilité de triaux a servi à démonter le passage
de l’étape i à l’étape i + 1 de la récurrence.
6. L’exécution de la fonction cle demande i + 1 étapes de boucle. Comme,
lors d’un appel à triaux, i est borné par k , le temps d’exécution de
cle est linéaire en k . Mais k est considéré comme une constante. Le
temps d’exécution de cle peut don être considéré comme borné par une
constante.
7. Pour réaliser triaux en temps linéaire, il suffit de faire un tri par dé-
nombrement, avec données satellites. Il est alors pratique d’utiliser une
structure de pile : on crée dix piles vides numérotées de 0 à 9, on par-
cours t du début à la fin en empilant chaque élément sur la pile de
numéro la valeur de la clé (son i + 1 ème digit). Ceci prend N étapes.
Lorsque c’est fini on dépile en commençant par la pile numéroté 9 et
en stockant les éléments dépilés dans t en commençant par la fin. Ceci
prend encore N étapes.
147
La recherche dichotomique d’un élément dans un tableau ordonné de n
éléments est asymtpotiquement en log n en pire cas.
La recherche du maximum dans un tableau de n éléments est asymptoti-
quement en n dans tous les cas, en particulier en pire cas.
148
empiler(P3, aux); if( (aux&1)==0)
} empiler(P2, aux);
while(pileVide(P3)==0){ }
aux=depiler(P3); }
empiler(P1, aux);
149
default : }
op1=ctoi(expr[i]); return depiler(p);
empiler(p, op1); }
}
2. Scinder
3. Le tri
150
void tri_fusion (file_t f1) {
file_t f2, file_t f3;
if (!EstVide(f1)) {
f2 = nouvelleFile();
f3 = nouvelleFile();
scinder(f1, f2, f3);
if (!EstVide(f2)) tri_fusion(f2);
if (!EstVide(f3)) tri_fusion(f3);
interclasser(f2, f3, f1);
detruireFile(f2);
detruireFile(f3);
}
}
151
Correction de l’exercice 48.
#define NMAX 10
typedef int element_t;
typedef struct {
element_t t[NMAX];
int taille;
} pile_t;
int estVide(pile_t p) {
return 0 == [Link];
}
element_t sommet(pile_t p) {
if (estVide(p)) {
perror("Exception: sommet sur pile vide");
}
return p.t[[Link] - 1];
}
element_t depiler(pile_t p) {
if (estVide(p)) {
perror("Exception: depiler sur pile vide");
}
[Link]--;
return p.t[[Link]];
}
empiler(element_t e, pile_t p) {
if ([Link] >= NMAX) {
perror("Exception: depassement de capacite du type pile_t");
}
p.t[[Link]] = e;
[Link]++;
}
152
Rappel et remarque. En C, comme un tableau est simplement l’adresse
de sa première case, si tab1 et tab2 sont deux tableaux et que l’on ef-
fectue l’affectation tab2 = tab1, il n’y a pas copie des cases de tab1.
Ainsi tab1[i] a même adresse que tab2[i], ces deux variables sont iden-
tiques.
typedef struct {
int t[3];
} stab_t;
stab_t x = {{100, 200, 300}};
stab_t y;
y = x;
x.t[0] = 0;
/* y.t[0] vaut 100 */
2. Pour implémenter une file dans un tableau nous allons retirer les élé-
ments d’un côté (le début) et les ajouter de l’autre (la fin) le problème
est qu’il faudra revenir au début du tableau lorsque l’indice maximum
sera atteint.
typedef struct {
element_t t[NMAX];
int debut;/* indice de la tete de file */
int taille;
} file_t;
int estVide(file_t f) {
return 0 == taille;
}
element_t tete(file_t f) {
153
if (estVide(f)) {
perror("Exception: tete sur file vide");
}
return f.t[[Link]];
}
ajouter(element_t e, file_t f) {
int fin;
if ([Link] >= NMAX) {
perror("Exception: depassement de capacite du type file");
}
fin = ([Link] + [Link]) %NMAX;
f.t[fin] = e;
[Link]++;
}
element_t retirer(file_t f) {
element_t e;
if (estVide(f)) {
perror("Exception: retirer sur file vide");
}
e = tete(f);
[Link] = ([Link] + 1) %NMAX;
[Link]--;
return e;
}
154
if(liste2==NULL) out->suivant=liste2;
return liste1; else
out->suivant=liste1;
if(cmpListe(liste1, liste2)>=0){
out=liste1; return finale;
liste1=liste1->suivant; }
}
else{
out=liste2; 2. void elimineRepetition(liste_t liste){
liste2=liste2->suivant; liste_t courant, aux, suiv;
} courant=liste;
while(courant!= NULL) {
finale=out; aux=courant;
while((liste1!=NULL)&& do {
(liste2!=NULL) ){ suiv=aux->suivant;
if(cmpListe(liste1, liste2)>=0){ if((suiv!=NULL) &&
out->suivant=liste1; (suiv->element==courant->element)){
liste1=liste1->suivant; aux->suivant=suiv->suivant;
} free(suiv);
else{ }
out->suivant=liste2; else
liste2=liste2->suivant; aux=suiv;
} } while(aux!=NULL);
out=out->suivant;
} courant=courant->suivant;
}
if(liste1==NULL) }
Pas de correction.
1. Déplacer :
155
2. Pour n=3:
1
2 2
3 3 1 3 2 1
−−−−−−−−−→ −−−−−−−−−→
a b c Deplacer(a, c) a b c Deplacer(a, b) a b c
1 1
3 2 2 3 1
−−−−−−−−−→ −−−−−−−−−→ −−−−−−−−−→
Deplacer(c, b) a b c Deplacer(a, c) a b c Deplacer(b, a) a
1
2 2
1 3 3
−−−−−−−−−→ −−−−−−−−−→
Deplacer(b, c) a b c Deplacer(a, c) a b c
156
doit donc déplacer 1.
1
2 2
5 2 1 5 1 5
6 3 4 6 3 4 6 3 4
−−−−−−−−−→ −−−−−−−−−→
a b c Deplacer(b, a) a b c Deplacer(c, a) a b c
1
2 2
5 3 5 3
6 4 6 1 4
−−−−−−−−−→ −−−−−−−−−→
Deplacer(b, c) a b c Deplacer(a, b) a b c
2. La suite des cartes en haut des piles est croissante. Pour trouver l’em-
placement d’une nouvelle carte, il suffit donc de chercher la dernière
pile dont la carte du dessus y a une valeur inférieure à x et de poser
la carte x sur la pile suivante. Pour chercher cette pile, on cherche par
dichotomie x dans le tableau des têtes de piles. Ceci prend un nombre
de comparaisons en log du nombre de piles. Comme il y a au plus N
piles, insérer une carte prend O(log N ) comparaisons. Donc insérer N
cartes prend O(N log N ) comparaisons.
3. On remarque que si x vient d’être placé sur une pile T [j] alors toute
carte y qui suit x dans σ et qui est plus grande que x doit être placée
après la pile T [j]. En effet au moment de placer x, toutes les piles avant
T [j] ont des cartes du dessus de valeur inférieure à x. Ces valeurs du
dessus, jusqu’à T [j] incluse ne peuvent que diminuer par ajout de nou-
velles cartes. Donc au moment de placer y , il n’est pas possible de le
poser sur une des piles avant T [j + 1].
Supposons que a1 < . . . < ak est une sous-suite de σ . Une fois que ai
est placé sur une pile, ai+1 est nécessairement placé sur une des piles
suivantes. Il faut donc au moins k piles.
4.
0 0 0 3 0 3
1 2 1 2 4 1 2 4 1 2 4 8
... 6 5 7 9 6 5 7 9 6 5 7 9 6 5 7 9
157
5. Si il y a une flêche d’un élément x vers élément y alors l’élément x est
plus grand que l’élément y et x a été posé après y . Ainsi une suite obte-
nue en suivant les flêches donne, en ordre inverse, une suite croissante
d’éléments de σ dans l’ordre de leur apparation dans σ , c’est à dire une
sous-suite croissante de σ .
6. Tout élément qui n’est pas dans la première pile possède une flêche vers
un élément dans la pile juste avant. Prenons n’importe quel élément de
la dernière pile T [p − 1] et suivons les flêches. Nous aurons alors une
sous-suite croissante de σ de longueur p.
7. La question précédente nous montre que le nombre de piles p formées
par Réussite(σ ) est égal à la longueur d’au moins une sous-suite crois-
sante de σ , et donc que p minore l(σ). Nous avons aussi montré (ques-
tion 3) que quel que soit la stratégie le nombre de piles est toujours
supérieur ou égal à l(σ). On en déduit l’égalité p = l(σ). D’autre part
puisque toute stratégie forme au moins l(σ) piles et que Réussite en
forme exactement l(σ), c’est que Réussite est optimal.
1
8. En prenant la suite σ = 3, 1, 2 on aura les deux piles : 3 2 et après
avoir enlevé 1 les têtes de piles ne vont plus croissante.
9. Une fois que la carte du dessus de T [0] est enlevée les têtes des piles
T [1], . . . , T [p] sont toujours croissantes mais la tête de T [0] n’a plus
forcément une valeur inférieur à celle de la tête de T [1]. Il faut alors
procéder par insertion de T [0] dans la suite du tableau de manière à
retrouver la propriété.
10. Code :
158
}
}
}
}
Le tas obtenu par insertion successives est donné figure 7.1, et le tas ob-
tenu en supprimant l’élément maximum (11) est donné figure 7.2.
11
10 6
8 9 3 5
4 7
Figure 7.1 – Tas : insertion de tous les éléments
10
9 6
8 7 3 5
4
Figure 7.2 – Tas : suppression de la racine (11)
159
Correction de l’exercice 55.
Pas de correction.
80
45 30
26 31 15 29
12 23 10
80
45 29
31 15 26 12
30 23 10
160
bleau vu comme un arbre quasi-parfait est déjà dans le bon ordre pour la
propriété de domination. On retire les éléments un à un en les dépilant de la
pile en T [0]. Après chaque retrait :
– Si la pile en T [0] est vide, on remplace T [0] par la dernière pile T [p−1],
et on décrémente p.
– On rétablit la propriété de domination par maintien bas à partir de T [0].
On effectue N retrait. Chacun de ces retraits prend au maximum un temps c+
log p, où c est une constante et où log p est la hauteur du tas (coût maximum
en temps de la phase de maintien). Comme p ≤ N , log p est majoré par log N .
Ainsi le temps mis par cet algorithme est majoré par cN + N log N où c est
une constante, ce qui est bien en O(N log N ).
b b
b b
b b b b b
b b b b b b
b b b b
Qui donne ici C4 = C0 ×C3 +C1 ×C2 +C2 ×C1 +C3 ×C1 = 5+2+2+5 = 14.
(nombres de Catalan).
Pour n fixé l’arbre quasi-parfait à n nœuds est tel que si sa hauteur est h
alors :
2h−1 − 1 < n ≤ 2h − 1
D’où h − 1 ≤ log n < h, donc log n + 1 majore h.
L’arbre peigne est quand à lui exactement de hauteur n.
161
Correction de l’exercice 62.
int taille(ab_t x) {
if (estVide(x)) {
return 0;
}
return 1 + taille(gauche(x)), taille(droite(x));
}
void parcours_infixe(x){
if (x) {
parcours_infixe(x->gauche);
affiche_element(x->e);
parcours_infixe(x->droite);
}
}
Espace mémoire L’espace mémoire est consommé par la pile d’appel : chaque
instance de la fonction occupe un espace constant et le nombre d’instances
est plus la hauteur de l’arbre. Le majorant est donc O(h). En fait ça peut être
moins que la hauteur à cause de l’optimisation de la récursion terminale (dans
ce cas le majorant est un plus le max pour toutes les branches de l’arbre du
nombre de fois où dans la branche on est descendu à gauche), voir plus bas.
Avec une pile. On simule le parcours récursif (la pile rend explicite la pile
d’appel qui gère normalement la récursion). On empile les sommets à traiter
comme dans le parcours récursif sauf qu’on élimine la récursion terminale (on
n’empile jamais un fils droite sur son parent, on dépile le parent d’abord – en
mode optimisation, le compilateur va faire ça pour nous).
162
void parcours_infixe_pile(x) {
ab_t y;
pile_t p;
int descendre = 1;
p = nouvellePile() // p est une pile vide, prête à accueillir des noeuds
if (x) empiler(p, x);
while (!estVide(p)) {
y = sommet(p);
if (descendre) { /* Descendre toujours à gauche */
if (y->gauche) {
empiler(p, y->gauche);
} else { /* fin de la descente */
descendre = 0;
}
if (!descendre) { /* On remonte */
depiler(p); /* pour ce y, c’est fini */
afficher_element(y->e);
if (y->droite) { /* reprend la descente à droite */
empiler(y->droite);
descendre = 1;
}
}
}
}
b
c d
e f
Départ : La pile contient a, descendre vaut 1 on entre dans la boucle.
Premier tour : on met descendre à 0 car a n’a pas de fils gauche, puis on
dépile a, on l’affiche, on empile b et on remet descendre à 1.
Tour 2 : On empile c.
Tour 3 : On empile e.
Tour 4 : On met descendre à 0, on dépile e et on l’affiche.
163
Tour 5 : On dépile c et on l’affiche.
Tour 6 : On dépile b, on l’affiche, on empile d et on mets descendre à 1.
Tour 7 : On mets descendre à 0, on dépile d, on l’affiche, on empile f et on
remets descendre à 1.
Tour 8 : On mets descendre à 0, on dépile f , on l’affiche.
Fin la pile est vide on s’arrête.
164
y = y->parent;
afficher_element(y->e);
if (y->droite) {
y = y->droite;
descente = 1;
}
} else { /* Cas 3 */
/* On remonte vraiment ! */
y = y->parent;
}
}
} // fin while
}
void parcours_infixe_espace_constant2(abr_t x) {
abr_t y;
if (x) {
y = minimum(x);
afficher_element(y->e);
while ( y = successeur(y) ) {
afficher_element(y->e);
}
}
}
void parcours_infixe(x){
if (x) {
parcours_infixe(x->gauche);
affiche_element(x->e);
parcours_infixe(x->droite);
}
}
165
Espace mémoire L’espace mémoire est consommé par la pile d’appel : chaque
instance de la fonction occupe un espace constant et le nombre d’instances
est plus la hauteur de l’arbre. Le majorant est donc O(h). En fait ça peut être
moins que la hauteur à cause de l’optimisation de la récursion terminale (dans
ce cas le majorant est un plus le max pour toutes les branches de l’arbre du
nombre de fois où dans la branche on est descendu à gauche), voir plus bas.
Avec une pile. On simule le parcours récursif (la pile rend explicite la pile
d’appel qui gère normalement la récursion). On empile les sommets à traiter
comme dans le parcours récursif sauf qu’on élimine la récursion terminale (on
n’empile jamais un fils droite sur son parent, on dépile le parent d’abord – en
mode optimisation, le compilateur va faire ça pour nous).
void parcours_infixe_pile(x) {
ab_t y;
pile_t p;
int descendre = 1;
p = nouvellePile() // p est une pile vide, prête à accueillir des noeuds
if (x) empiler(p, x);
while (!estVide(p)) {
y = sommet(p);
if (descendre) { /* Descendre toujours à gauche */
if (y->gauche) {
empiler(p, y->gauche);
} else { /* fin de la descente */
descendre = 0;
}
if (!descendre) { /* On remonte */
depiler(p); /* pour ce y, c’est fini */
afficher_element(y->e);
if (y->droite) { /* reprend la descente à droite */
empiler(y->droite);
descendre = 1;
}
}
}
}
166
a
b
c d
e f
Départ : La pile contient a, descendre vaut 1 on entre dans la boucle.
Premier tour : on met descendre à 0 car a n’a pas de fils gauche, puis on
dépile a, on l’affiche, on empile b et on remet descendre à 1.
Tour 2 : On empile c.
Tour 3 : On empile e.
Tour 4 : On met descendre à 0, on dépile e et on l’affiche.
Tour 5 : On dépile c et on l’affiche.
Tour 6 : On dépile b, on l’affiche, on empile d et on mets descendre à 1.
Tour 7 : On mets descendre à 0, on dépile d, on l’affiche, on empile f et on
remets descendre à 1.
Tour 8 : On mets descendre à 0, on dépile f , on l’affiche.
Fin la pile est vide on s’arrête.
167
int descente = 1;
y = x;
while (y) {
if (descente) {
if (y->gauche) { /* Cas 1: descente a gauche */
y = y->gauche;
} else { /* Cas 2: descente a droite */
afficher_element(y->e);
if (y->droite) {
y = y->droite;
} else {
descente = 0;
}
} else {
if (y->parent && (y == y->parent->gauche) ) { /* Cas 2 */
/* On remonte pour mieux redescendre à droite */
y = y->parent;
afficher_element(y->e);
if (y->droite) {
y = y->droite;
descente = 1;
}
} else { /* Cas 3 */
/* On remonte vraiment ! */
y = y->parent;
}
}
} // fin while
}
void parcours_infixe_espace_constant2(abr_t x) {
abr_t y;
if (x) {
y = minimum(x);
afficher_element(y->e);
while ( y = successeur(y) ) {
afficher_element(y->e);
}
}
}
168
Correction de l’exercice 67.
Pas de correction.
12
3 14
2 5 13 15
14
5 18
2 9 15 19
13
1. Figure 7.9.
2. rotation à gauche de centre 5, puis rotation à droite de centre 14.
3. Il faut montrer la préservation de la propriété d’arbre de recherche. On
se contente de montrer que si l’arbre à gauche de la figure est un arbre
binaire de recherche alors l’arbre à droite en est un,et réciproquement.
En effet, pour l’arbre qui contient l’un de ces deux arbres comme sous-
arbre, le fait de remplacer l’un par l’autre ne fait aucune différence : les
deux sous-arbres ont mêmes ensembles d’éléments. Pour chacun des
169
12
3 15
2 5
15
5 18
2 9 19
12
2 15
3 14
4. /* Rotations :
170
/ \ / \
b E <--rot. gauche de centre x--- C a
/ \ / \
C D D E
*/
y = x->gauche;
y = x->droite;
171
tmp = x->e;
x->e = y->e;
y->e = tmp;
Fonction Remonter(x)
y = Parent(x);
siy 6= NULL alors
/* y existe, x n’est pas la racine */
si x == Gauche(y) alors
/* x est fils gauche de y */
RotationDroite (y );
sinon
/* x est fils droit de y */
RotationGauche (y );
/* L’élément qui était dans le nœud x est désormais dans le
nœud y */
Remonter (y );
Et en C :
void remonter(abr_t x) {
y = x->parent;
if (y) { /* x n’est pas encore à la racine */
if (x == y->gauche) {
rotation_droite(y);
}
else {
rotation_gauche(y);
}
/* l’élément qui était contenu dans x est maintenant dans y */
172
remonter(y);
}
}
Pas de correction.
void parcours_infixe(abr_t x) {
if (x) {
parcours_infixe(x->gauche);
affiche_element(x->e);
parcours_infixe(x->droite);
}
}
Si on pouvait parcourir les éléments d’un tas en ordre trié en temps O(n),
comme on plante un tas en O(n), on aurait un tri par comparaison en O(n).
Impossible. Le parcours du tas en ordre trié est ainsi nécessairement en Ω(n log n).
Pas de correction.
173
Correction de l’exercice 73.
Pas de correction.
Hn (30) = 3
Hn (20) = 3
Hn (35) = 2
Hn (50) = 1
174
doivent être noirs (preuve facile par l’absurde). En conséquence, la hau-
teur noire de la racine vaut au moins h/2, donc
n ≥ 2h/2 − 1,
d’où
h ≤ 2 log(n + 1).
30
15 40
10 25 N 50
N N 20 N N N
N N
Figure 7.10 – Coloriage corrigé
175
– Le troisième arbre (c) est très joli avec de belles couleurs mais ce n’est
pas un ABR donc pas un rouge noir (oui je sais c’est vache).
– Le quatrième (d) a un nœud rouge dont un fils est rouge.
176
Table des matières
1 Introduction 3
1.1 La notion d’algorithme . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Structures de données 37
3.1 Structures de données abstraites : pile, file, file de priorité . . . . 38
3.2 Listes chaînées en C . . . . . . . . . . . . . . . . . . . . . . . . 41
4 Arborescences 48
4.1 Arbres binaires parfaits et quasi-parfaits . . . . . . . . . . . . . . 51
4.2 Tas et files de priorité . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3 Arbres binaires de recherche . . . . . . . . . . . . . . . . . . . . 64
5 Éléments de calculabilité 70
177
IV Exercices 77
6 Exercices 78
6.1 Exercices du premier chapitre . . . . . . . . . . . . . . . . . . . 79
6.2 Exercices du second chapitre . . . . . . . . . . . . . . . . . . . . 86
6.3 Exercices du troisième chapitre . . . . . . . . . . . . . . . . . . 99
6.4 Exercices du quatrième chapitre . . . . . . . . . . . . . . . . . . 106
178
Bibliographie
179
Table des matières
1 Introduction 3
1.1 La notion d’algorithme . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Algorithmes et programmes . . . . . . . . . . . . . . . . . 4
1.1.2 Histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 La notion d’invariant de boucle . . . . . . . . . . . . . . . 6
1.2.2 De l’optimisation des programmes . . . . . . . . . . . . . . 10
1.2.3 Complexité en temps et en espace . . . . . . . . . . . . . . 11
1.2.4 Pire cas, meilleur cas, moyenne . . . . . . . . . . . . . . . 11
1.2.5 Notation asymptotique . . . . . . . . . . . . . . . . . . . . 12
1.2.6 Optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . 15
180
2.5.3 Tri par base . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3 Structures de données 37
3.1 Structures de données abstraites : pile, file, file de priorité . . . . 38
3.1.1 Piles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1.2 Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.3 File de priorité . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2 Listes chaînées en C . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2.1 Opérations fondamentales . . . . . . . . . . . . . . . . . . 43
3.2.2 Réalisation des piles avec des listes chaînes . . . . . . . . 46
3.2.3 Réalisation des files avec des listes chaînes . . . . . . . . . 46
4 Arborescences 48
4.1 Arbres binaires parfaits et quasi-parfaits . . . . . . . . . . . . . . 51
4.2 Tas et files de priorité . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.1 Changement de priorité d’un élément dans un tas . . . . . 54
4.2.2 Ajout et retrait des éléments . . . . . . . . . . . . . . . . . 56
4.2.3 Formation d’un tas . . . . . . . . . . . . . . . . . . . . . . 57
4.2.4 Le tri par tas . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.3 Arbres binaires de recherche . . . . . . . . . . . . . . . . . . . . 64
4.3.1 Rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.3.2 Arbres rouge noir . . . . . . . . . . . . . . . . . . . . . . 67
5 Éléments de calculabilité 70
IV Exercices 77
6 Exercices 78
6.1 Exercices du premier chapitre . . . . . . . . . . . . . . . . . . . 79
6.1.1 Récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.1.2 Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.1.3 Notation asymptotique . . . . . . . . . . . . . . . . . . . . 83
6.2 Exercices du second chapitre . . . . . . . . . . . . . . . . . . . . 86
6.3 Exercices du troisième chapitre . . . . . . . . . . . . . . . . . . 99
6.4 Exercices du quatrième chapitre . . . . . . . . . . . . . . . . . . 106
181
7 Correction des exercices 118
7.1 Premier chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7.2 Deuxième chapitre . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.3 Troisième chapitre . . . . . . . . . . . . . . . . . . . . . . . . . 148
7.4 Quatrième chapitre . . . . . . . . . . . . . . . . . . . . . . . . . 159
182