Algorithmique 1

Licence dinformatique (2`eme annee)

Universite dAix-Marseille
F. Denis, S. Grandcolas, Y. Vax`es
2012 - 2013
2
Chapitre 1
Introduction.
Ce cours constitue une introduction `a lalgorithmique. Il est destine aux
etudiants de deuxi`eme annee de la licence dinformatique de luniversite
dAix-Marseille, supposes avoir dej`a des bases solides en programmation.
1.1 Contenu du cours
Le premier chapitre est une introduction `a lanalyse des algorithmes et en
particulier, aux notions fondamentales de preuves et de complexite des algo-
rithmes. Le second chapitre est consacre aux structures de donnees lineaires
(tableaux, listes, piles, les et tables de hachage). Le troisi`eme chapitre est
dedie aux principaux algorithmes de tris et `a letude de leur complexite. Le
quatri`eme chapitre est consacre aux arbres binaires de recherche, aux tas et
aux arbres lexicographiques. Le cinqui`eme chapitre introduit la notion de
programmation dynamique qui sapplique dans certains cas aux methodes
de type diviser pour regner. Le sixi`eme et dernier chapitre est consacre aux
graphes qui interviennent dans la representation de nombreux probl`emes,
et pour lesquels un grand nombre dalgorithmes ont ete developpes, notam-
ment pour le calcul de plus courts chemins. Nous presenterons quelques
applications pratiques des graphes, entre autre dans le domaine du routage.
Ce cours est largement inspire de Introduction `a lalgorithmique de T.
Cormen, C. Leiserson et R. Rivest (editions DUNOD) qui est la reference
pour les cours algorithmique 1 et algorithmique 2 de la licence dinforma-
tique.
Ce support de cours correspond aux cours magistraux, qui sont completes
par des travaux diriges et des travaux pratiques. Les algorithmes sont donnes
en pseudo-code qui permet de sabstraire de details dimplementation (voir
3
4 CHAPITRE 1. INTRODUCTION.
section suivante) ou en C, langage utilise dans les travaux pratiques.
1.2 Description des algorithmes en pseudo-code
Un algorithme
1
est la description dun calcul eectue sur des donnees
discr`etes. On distingue les donnees fournies en entree de lalgorithme et
celles quil calcule en sortie.
Un algorithme est decrit par un pseudo-code susamment precis pour
pouvoir etre implemente dans tout langage de programmation, et en C en
particulier.
Conventions retenues pour le pseudo-code :
1. utilisation dindentations pour identier les blocs dinstructions ;
2. les tests usuels (=, <, >, , ) sont disponibles ainsi que les connec-
teurs logiques de base (ET, OU, NON)
2
;
3. les structures de controles conditionnelles usuelles (si ...alors ...
et si ...alors ...sinon ... sont disponibles ;
4. les structures iteratives usuelles tant que, pour, repeter ...jusqu`a)
sont disponibles ;
5. laffectation de variable est notee ;
6. il est possible de denir et dutiliser des fonctions et procedures ; les
passages de param`etres se font par valeur ; les appels recursifs sont
possibles.
1.3 Premiers exemples dalgorithmes
Lalgorithme 1 decrit une methode simple de tri, le tri par insertion, qui
consiste `a parcourir un tableau du second indice jusquau dernier et `a inserer
de facon ordonnee chaque element courant parmi les elements precedents.
Linsertion ordonnee dun element dans un tableau trie est realisee par lal-
gorithme 2. La division de lalgorithme de tri en deux rend sa comprehension,
et donc sa verication, plus simple. Remarquez que dans la condition darret
de la boucle de lalgorithme 2, T[i] nest pas evalue si i = 0 puisque dans ce
cas, la conjonction est fausse.
1. dapr`es le nom du mathematicien perse Al Khawarizmi (783-850).
2. on supposera que comme en C, levaluation de p ET q (resp. p OU q) commence par
p et sarrete si p est evalue ` a FAUX (resp. ` a VRAI).
1.3. PREMIERS EXEMPLES DALGORITHMES 5
Algorithme 1: TriInsertion
entree : T[1, n] est un tableau dentiers, n 1.
resultat : les elements de T sont ordonnes par ordre croissant.
debut
pour j = 2 `a n faire
InsertionOrdonnee(T[j],T[1, j-1])
npour
n
Algorithme 2: InsertionOrdonnee
entree : x est un entier ; T[1, n] est un tableau dentiers trie par
ordre croissant.
sortie : T[1, n + 1] contient les elements de T x ordonnes par
ordre croissant.
debut
i n
tant que i > 0 ET T[i] > x faire
T[i + 1] T[i]
i i 1
ntq
T[i + 1] x
n
Lalgorithme 3 decrit la recherche dun element x dans un tableau trie
T[m, n] : il commence par comparer x `a lelement qui se trouve au centre du
tableau puis, selon les cas, arrete la recherche ou la continue sur lune des
deux moitie de tableaux. On parle de recherche dichotomique. Cet algorithme
suit la methode divide and conquer, qui consiste `a diviser le probl`eme initial
en sous probl`emes de tailles inferieures, `a resoudre ces sous-probl`emes puis `a
combiner leurs solutions pour trouver la solution du probl`eme initial. Cest
un algorithme recursif puisquil comporte des appels `a lui-meme.
6 CHAPITRE 1. INTRODUCTION.
Fonction rechercheDichotomique(T, m, n, x)
entree : T[m, n] est un tableau dentiers trie par ordre croissant,
1 m n; x est un entier.
sortie : 0 si x , T et i si T[i] est la premi`ere occurrence de x dans
T[m, n].
debut
si m = n alors
si T[m] = x alors
retourner m
sinon
retourner 0
nsi
sinon
k
m+n
2
|
a
si T[k] < x alors
retourner rechercheDichotomique(T, k + 1, n, x)
sinon
retourner rechercheDichotomique(T, m, k, x)
nsi
nsi
n
a. Pour tout reel x, x (resp. x) designe la partie enti`ere superieure (resp. la partie
enti`ere inferieure) de x, cest-` a-dire le plus petit entier superieur ou egal ` a x (resp. le plus
grand entier inferieur ou egal ` a x).
Chapitre 2
Analyse des algorithmes
Analyser un algorithme consiste `a calculer les ressources qui seront necessaires
`a son execution. Mais avant de lanalyser, il faut dabord sassurer quil est
correct, cest-`a-dire quil calcule bien ce pourquoi il a ete ecrit.
2.1 Preuves de la correction dun algorithme
Comment sassurer quun algorithme calcule bien ce quil est cense calcu-
ler ? Comment sassurer quun algorithme termine quelle que soit les donnees
qui lui seront fournies en entree ? Les algorithmes sont susamment forma-
lises pour quon puisse prouver quils poss`edent les proprietes attendues de
correction ou de terminaison. Les preuves sont facilitees lorsque les algo-
rithmes sont bien ecrits, et en particulier sils sont decomposes en de nom-
breux sous algorithmes courts et bien species.
Ce sont bien evidemment les structures iteratives et les appels recursifs
qui necessitent le plus de travail.
2.1.1 Preuve dune structure iterative
Considerons le schema dalgorithme suivant :
7
8 CHAPITRE 2. ANALYSE DES ALGORITHMES
Algorithme 3: Structure iterative generique
resultat : R
debut
Initialisation
tant que Condition faire
Instructions
ntq
n
Un invariant de boucle est une propriete ou une formule logique,
qui est veriee apr`es la phase dinitialisation,
qui reste vraie apr`es lexecution dune iteration,
et qui, conjointement `a la condition darret, permet de montrer que le
resultat attendu est bien celui qui est calcule.
Exemple 1 Pour lalgorithme 2, qui ins`ere un element x dans un tableau
trie T[1, n], considerons la propriete I suivante :
la juxtaposition des tableaux T[1, i] et T[i +2, n+1]
1
est egale
au tableau initial et x est plus petit que tous les elements du
deuxi`eme tableau
2
.
1. La propriete est veriee apr`es linitialisation puisque T[1, i] est egal au
tableau initial (i = n), et que le second tableau T[i +2, n+1] est vide.
2. Si la propriete I est vraie au debut dune iteration, elle est vraie `a la n
de cette iteration puisque le dernier element T[i] du premier tableau
passe en tete du second (lordre nest pas modie), que lon a x < T[i]
et que lindice est modie en consequence.
Si la condition reste vraie, alors la propriete est donc veriee au debut
de literation suivante.
3. Si la condition est fausse, alors
soit i = 0, le premier tableau est vide, x est donc plus petit que tous
les elements du tableau initial, reportes dans le tableau T[2, n+1] et
il sut decrire T[1] = T[i +1] = x pour obtenir le resultat attendu;
soit i > 0 et x T[i] : x est donc que tous les elements du
tableau T[1, i] et < que tous les elements du tableau T[i + 2, n]. Il
sut decrire T[i + 1] = x pour obtenir le resultat attendu.
Pour prouver la correction dune boucle Pour, on peut remarquer que
Pour i=1 `a n
Instructions
1. si i + 2 > n + 1, T[i + 2, n + 1] designe un tableau vide.
2. propriete vraie si le deuxi`eme tableau est vide.
2.1. PREUVES DE LA CORRECTION DUN ALGORITHME 9
equivaut `a
i=1
Tant que i<= n
Instructions
i=i+1
et utiliser la technique precedente.
Exemple 2 Pour prouver la correction de lalgorithme 1 de tri par insertion,
on consid`ere linvariant de boucle suivant :
T[1, j 1] est trie .
1. Apr`es linitialisation, la propriete est vraie puisque j = 2 et que le
tableau T[1, j 1] ne contient quun seul element.
2. Supposons que T[1, j 1] soit trie au debut dune iteration. Apr`es
appel de lalgorithme insertionOrdonnee, le tableau T[1, j] est trie.
Apr`es lincrementation de j, le tableau T[1, j 1] est trie.
3. Si la condition devient fausse, cest que j = n + 1. Le tableau T[1, n]
est donc trie.
2.1.2 Preuve dun algorithme recursif
On prouve la correction dun algorithme recursif au moyen dun raison-
nement par recurrence.
Exemple 3 Pour prouver la correction de lalgorithme 3 (recherche dicho-
tomique), on eectue une recurrence sur le nombre N = nm+1 delements
du tableau.
si N = 1, alors m = n et on verie que lalgorithme est correct dans
ce cas ;
soit N 1. Supposons que le programme soit correct pour tout tableau
de longueur N et considerons un tableau T[m, n] de N+1 elements :
n m + 1 = N + 1. En particulier, m ,= n puisque N 1. Soit k =

m+n
2
|. On a m k < n. Donc, les longueurs des deux tableaux passes
en argument des appels recursifs verient : k m + 1 n m N
et n k n m N. Par hypoth`ese de recurrence, quelque soit le
resultat du test T[k] < x, lalgorithme donnera une reponse correcte.
2.1.3 Exercices
Prouvez la correction des algorithmes suivants :
10 CHAPITRE 2. ANALYSE DES ALGORITHMES
1. Recherche du plus grand element dun tableau (version iterative) :
Fonction MaxEltIter(T)
entree : T[1, n] est un tableau dentiers.
sortie : le plus grand element de T[1, n]
debut
Max T[1]
pour i = 2 `a n faire
si T[i] > Max alors
Max T[i]
nsi
npour
retourner Max
n
2. Recherche du plus grand element dun tableau (version recursive) :
Algorithme 4: MaxEltRec
entree : T[1, n] est un tableau dentiers.
sortie : le plus grand element de T[1, n]
debut
si n = 1 alors
retourner T[1]
sinon
retourner Max(T[n], MaxEltRec(T[1, n 1]))
nsi
n
3. Recherche conjointe du plus petit element et du plus grand element
dun tableau.
2.2. COMPLEXIT

E DES ALGORITHMES 11
Algorithme 5: MinMaxElt
entree : T[1, n] est un tableau dentiers.
sortie : le plus petit et le plus grand element de T[1, n]
debut
Min T[1], Max T[1]
pour j = 1 `a
n1
2
| faire
si T[2 j] < T[2 j + 1] alors
si T[2 j] < Min alors
Min T[2 j]
nsi
si T[2 j + 1] > Max alors
Max T[2 j + 1]
nsi
sinon
si T[2 j + 1] < Min alors
Min T[2 j + 1]
nsi
si T[2 j] > Max alors
Max T[2 j]
nsi
nsi
npour
si n est pair alors
si T[n] < Min alors
Min T[n]
nsi
si T[n] > Max alors
Max T[n]
nsi
nsi
retourner Min, Max
n
2.2 Complexite des algorithmes
En plus detre correct, cest-`a-dire deectuer le calcul attendu, on de-
mande `a un algorithme detre ecace, lecacite etant mesuree par le temps
que prend lexecution de lalgorithme ou plus generalement, par les quantites
de ressources necessaires `a son execution (espace memoire, bande passante,
12 CHAPITRE 2. ANALYSE DES ALGORITHMES
. . . ).
Le temps dexecution dun algorithme depend evidemment de la taille
des donnees fournies en entree, ne serait-ce que parce quil faut les lire avant
de les traiter. La taille dune donnee est mesuree par le nombre de bits
necessaires `a sa representation en machine. Cette mesure ne depend pas du
materiel sur lequel lalgorithme sera programme.
Mais comment mesurer le temps dexecution dun algorithme puisque
les temps de calcul de deux implementations du meme algorithme sur deux
machines dierentes peuvent etre tr`es dierents ? En fait, quelque soit la
machine sur laquelle un algorithme est implemente, le temps de calcul du
programme correspondant est egal au nombre doperations elementaires ef-
fectuees par lalgorithme, `a un facteur multiplicatif pr`es, et ce, quelle que
soit la taille des donnees dentree de lalgorithme. Par operations elementaires
on entend evaluations dexpressions, aectations, et plus generalement trai-
tements en temps constant ou independant de lalgorithme (entrees-sorties,. . . ).
Le detail de lexecution de ces operations au niveau du processeur par lin-
termediaire dinstructions machine donnerait des resultats identiques `a un
facteur constant pr`es.
Autrement dit, pour toute machine /, il existe des constantes m et M
telles que pour tout algorithme / et pour toute donnee d fournie en entree de
lalgorithme, si lon note T(d) le nombre doperations elementaires eectuees
par lalgorithme avec la donnee d en entree et T
M
(d) le temps de calcul du
programme implementant / avec la donnee d en entree,
mT(d) T
M
(d) MT(d).
Soit, en utilisant les notations de Landau (voir section 8.1),
T = (T
M
).
On peut donc denir la complexite en temps dun algorithme comme le
nombre doperations elementaires T(n) eectuees lors de son execution sur
des donnees de taille n. Il sagit donc dune fonction. On distingue
la complexite dans le pire des cas (worst case complexity) : T
pire
(n) =
le nombre doperations maximal calcule sur toutes les donnees de taille
n;
la complexite dans le meilleur des cas (best case complexity) : T
min
(n) =
le nombre doperations minimal calcule sur toutes les donnees de taille
n;
la complexite en moyenne (average case complexity) : T
moy
(n) = le
nombre doperations moyen calcule sur toutes les donnees de taille n,
en supposant quelles sont toutes equiprobables.
2.2. COMPLEXIT

E DES ALGORITHMES 13
Analyser un algorithme consiste `a evaluer la ou les fonctions de com-
plexite qui lui sont associees. En pratique, on cherche `a evaluer le comporte-
ment asymptotique de ces fonctions relativement `a la taille des entrees (voir
section 8.1). En considerant le temps dexecution, dans le pire des cas ou en
moyenne, on parle ainsi dalgorithmes
en temps constant : T(n) = (1),
logarithmiques : T(n) = (log n),
lineaires : T(n) = (n),
quadratiques : T(n) = (n
2
),
polynomiaux : T(n) = (n
k
) pour k N,
exponentiels : T(n) = (k
n
) pour k > 0.
Si un traitement elementaire prends un millioni`eme de seconde, le tableau
suivant decrit les temps dexecutions approximatifs de quelques classes de
probl`emes en fonction de leurs tailles
Taille n log
2
n n nlog
2
n n
2
2
n
10 0.003 ms 0.01 ms 0.03 ms 0.1 ms 1 ms
100 0.006 ms 0.1 ms 0.6 ms 10 ms 10
14
siecles
1000 0.01 ms 1 ms 10 ms 1 s
10
4
0.013 ms 10 ms 0.1 s 100 s
10
5
0.016 ms 100 ms 1.6 s 3 heures
10
6
0.02 ms 1 s 20 s 10 jours
Dun autre point de vue, le tableau ci-dessous donne la taille des probl`emes
que lon peut traiter en une seconde en fonction de la rapidite de la machine
utilisee (nTs est le nombre de traitements par secondes).
nTs 2
n
n
2
nlog
2
n n log
2
n
10
6
20 1000 63000 10
6
10
300000
10
7
23 3162 600000 10
7
10
3000000
10
9
30 31000 4.10
7
10
9
10
12
40 10
6
3.10
10
En pratique, un algorithme est constitue dinstructions agencees `a laide
de structures de controle que sont les sequence, les embranchements et les
boucles (nous verrons plus tard comment traiter le cas particulier des fonc-
tions recursives, mais de toutes facons toute fonction recursive secrit aussi
iterativement). Le co ut dune sequence de traitements est la somme des
14 CHAPITRE 2. ANALYSE DES ALGORITHMES
co uts de chaque traitement. Le co ut dune structure iterative est la somme
des co uts des traitements eectues lors des passages successifs dans la boucle.
Par exemple il arrive frequemment que lon eectue n fois une boucle avec
des co uts degressifs ((n), (n 1),. . . ,(1)). Dans ce cas
T(n) = n + (n 1) + (n 2) + . . . + 1 =
n

i=1
i =
n (n + 1)
2
Le co ut dun embranchement (si test alors traitement1 sinon traitement2)
est le co ut du plus couteux des deux traitements.
2.2.1 Exemples danalyse dalgorithmes
Lalgorithme dinsertion dun element dans un tableau trie Dans
le pire des cas, celui o` u lentier `a inserer est plus petit que tous les elements
du tableau, lalgorithme 2 requiert
2N + 2 aectations,
2N comparaisons dentiers,
N soustractions et 1 addition,
N evaluations dune expression booleenne
pour un tableau de N elements.
En supposant que les entiers ont une taille constante k, une donnee en
entree de taille n permet de representer n/k entiers, soit un tableau de
N = n/k 1| entiers. On remarque que N = (n). En supposant de plus
que chaque instruction elementaire sexecute en un temps constant, on en
deduit que T
pire
(n) = (n). Lalgorithme dinsertion ordonnee est lineaire
dans le pire des cas : `a des constantes additive et multiplicative pr`es, le
temps dexecution est egal au nombre delements du tableau.
On voit facilement que T
min
(n) = (1) : en eet, dans le meilleur des
cas, lelement `a inserer est plus grand que tous les elements du tableau et la
boucle nest pas executee.
Si lon suppose que lelement `a inserer et un element pris au hasard
dans le tableau suivent la meme loi de probabilite, son insertion necessitera
en moyenne N comparaisons. On aura donc, T
moy
(n) = (n), soit une
complexite moyenne du meme ordre que la complexite du pire des cas.
Lalgorithme de tri par insertion Dans le pire des cas, celui o` u le
tableau en entree est dej`a trie, mais par ordre decroissant, lalgorithme
necessite
2.2. COMPLEXIT

E DES ALGORITHMES 15
N1 comparaisons et aectations pour la condition de la boucle pour
N 1 appels `a lalgorithme dinsertion ordonnee, pour des tailles de
tableaux variant de 1 `a N 1.
A des constantes additive et multiplicative pr`es, le temps dexecution
dans le pire des cas de lalgorithme de tri par insertion est donc egal `a
(N 1) + 1 + 2 + . . . + (N 1) = N 1 +
N(N 1)
2
= (N
2
)
soit en appliquant la remarque sur legalite `a des constantes additive et
multiplicative pr`es de la taille des donnees et du nombre delements du
tableau,
T
pire
(n) = (n
2
).
On voit facilement que T
min
(n) = (n), cas o` u le tableau est dej`a or-
donne par ordre croissant.
Si tous les elements du tableau en entree sont tires selon la meme loi
de probabilites, on peut montrer que T
moy
(n) = (n
2
). Autrement dit, sil
peut arriver que le temps dexecution soit lineaire, il y a beaucoup plus de
chance quil soit quadratique en la taille des donnees en entree.
Lalgorithme de recherche dichotomique Si le tableau contient un
seul element, lalgorithme executera 2 comparaisons (co ut total : c
1
)
Si le tableau contient N > 1 elements, lalgorithme executera
3 operations arithmetiques, une aectation et une comparaison entre
2 entiers (co ut total : c
2
), et
un appel recursif sur un tableau possedant N/2| ou N/2| elements,
soit N/2| dans le pire des cas.
On en deduit que
T
pire
(N) = T
pire
(N/2|) + c
2
.
Conformement `a la remarque faite ci-dessus sur lequivalence entre la
taille dun tableau dentiers et sa longueur, on supposera que N est egal `a
la taille des donnees.
Cette equation est simple `a resoudre lorsque N est egal `a une puissance
de 2 :
T
pire
(2
k
) = T
pire
(2
k1
) + c
2
= T
pire
(2
k2
) + 2c
2
= . . . = c
1
+ kc
2
.
Dans le cas general, soit
N = a
k
2
k
+ . . . + a
1
2
1
+ a
0
16 CHAPITRE 2. ANALYSE DES ALGORITHMES
lecriture de N en base 2 : a
k
= 1 et 0 a
i
1 pour 0 i < k. On a
2
k
N < 2
k+1
et donc 2
k1
N/2| 2
k
.
On en deduit que
c
1
+ kc
2
T
pire
(N) c
1
+ (k + 1)c
2
.
En remarquant que k = (log
2
N), on en deduit que T
pire
(N) = (log
2
N).
La recherche dichotomique dun element dans un tableau trie se fait donc
en temps logarithmique.
Lanalyse dalgorithmes conduit souvent `a des equations recursives de la
forme
T(n) = a T(n/b) + f(n).
Le theor`eme 1 de la section 8.2 donne la solution de ces equations dans le cas
general. Dans lexemple precedent, on se trouve dans le cas (2) du theor`eme,
avec a = 1 et b = 2 : on retrouve que T
pire
(N) = (log
2
N).
Le tri par fusion
Algorithme 6: TriFusion
entree : T[1, n] est un tableau dentiers, n 1.
resultat : les elements de T sont ordonnes par ordre croissant.
debut
si n > 1 alors
T
1
= triFusion(T[1, n/2|])
T
2
= triFusion(T[n/2| + 1, n])
T = Fusion(T
1
, T
2
)
nsi
n
La recurrence est
T(n) = 1 + n + 2 T(n/2) + n
Dautre part T(0) = T(1) = 1.
Solution methode generale (voir le theor`eme 1 de la section 8.2).
On est dans le cas 2 puisque f(n) = 2 n + 1 et puisque a = b = 2 on a
log
b
a = 1 et f(n) = (n). Donc T(n) = (n lgn).
Solution en developpant la recurrence.
2.2. COMPLEXIT

E DES ALGORITHMES 17
T(n) = 2n + 1 + 2 T(n/2) = 2n + 1 + 2n + 2 + 4 T(n/4)
= 2n + 1 + 2n + 2 + 2n + 4 + 8 T(n/8) = . . .
On en deduit que puisque T(1) = 1, on a une suite de log
2
n| termes
puisquon divise n par 2 `a chaque fois, et donc
T(n) =
log
2
n
i=0
(2n + 2
i
) = 2n log
2
n +
log
2
n
i=0
2
i
que lon sait calculer
3
. Donc
T(n) = 2nlog
2
n+2
log
2
n+1
1 = 2nlog
2
n+2n = 2n(log
2
n+1) = O(nlog
2
n)
hauteur : log
2
n|
n
2x
n 2x
n 2x
n
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
1 1 1 ....
log
n
Figure 2.1 Arbre des appels recursifs pour lalgorithme de tri par fusion.
Solution intuitive. On remarque que lexecution de la procedure produit
le parcours dun arbre virtuel de profondeur log
2
n|, et qu`a chaque niveau
de larbre on eectue (n) traitements (2
p
noeuds `a chaque niveau, et des
suites de longueurs n/(2
p
) elements en chaque noeud). On pressent donc in-
tuitivement que le co ut est quelque chose de la forme nlog
2
n. Mais attention
il peut y avoir des termes de classe inferieure. On va donc partir sur une
forme compl`ete de T(n) avec des constantes
T(n) = a n log
2
n + b n + c
Nous essaierons ensuite de xer les constantes, dune part en developpant
lequation recursive en substituant `a T(n/2) la formule ci-dessus, mais aussi
en utilisant les cas pour lesquels on connait le resultat, cest-`a-dire quand n
est tr`es petit.
3. Quelques formules de sommation :
P
n
i=0
i =
n(n+1)
2
= O(n
2
) ;
P
n
i=0
x
i
=
x
n+1
1
x1
=
O(x
n
) si x = 1.
18 CHAPITRE 2. ANALYSE DES ALGORITHMES
Donc T(n/2) = a n/2 log
2
n a n/2 + b n/2 + c. En reprenant la
recurrence on obtient
T(n) = (2c + 1) + (b + 2 a) n + a n log
2
n
On en deduit (1) 2c + 1 = c donc c = 1, (2) b + 2 1 = b donc a = 2.
Puisque T(1) vaut 1, on en deduit que 2 n log
2
1 + b 1 = 1 et donc
b = 2. Donc
T(n) = 2 n log
2
n + 2 n 1 = O(n log
2
n)
2.2.2 Exercices
Exercice 1 Quelle est la classe de complexite de la fonction f(n) suivante
(demontrez-le)
f(n) = 2 n
3
+ 4 n
2
+ 2
3
Exercice 2 Quelle est la complexite de la fonction bidon suivante :
fonction bidon(n)
debut
pour i := 1 `a n n faire
u := i,
tant que (u > 1) faire
u := u/2,
n faire
n faire
n fonction
Exercice 3
1.

Ecrivez un algorithme qui prend en entree un tableau dentiers et
calcule les valeurs minimale et maximale quil contient.

Evaluez la
complexite de votre algorithme (mesuree en nombre de comparaisons
eectuees).
2.

Evaluez la complexite de lalgorithme 7 (meme mesure).
Exercice 4 Calculez la complexite de la fonction ProdMat(MAT A, MAT
B, MAT C, int n) qui calcule le produit des matrices carrees A et B de n
lignes et n colonnes.
Exercice 5 Calculer la complexite de la fonction exp(x, n) qui calcule x
n
`a partir de la formule suivante :
2.2. COMPLEXIT

E DES ALGORITHMES 19
x
n
= (x
2
)
n/2
si n est pair,
x
n
= x x
n1
si n est impair
En utilisant ce principe, quel est le co ut de lelevation dune matrice `a
la puissance n.
Exercice 6 : Calcul de lelement majoritaire dun tableau.
Etant donne un ensemble E de n elements, on veut savoir sil existe
un element majoritaire et quel est-il (un element majoritaire apparat plus
dune fois sur deux, i.e. si k est son nombre dapparitions, 2 k > n).
Methode nave Donnez une methode naive pour ce calcul. Quelle est sa
complexite ?
Methode 2 : diviser pour regner. On consid`ere maintenant lapproche
diviser pour regner suivante : pour calculer lelement majoritaire dans
lensemble E sil existe, on reparti les n elements de E dans deux
ensembles de memes tailles E
1
et E
2
, et on calcule (recursivement)
dans chacune de ces parties lelement majoritaire. Pour que e soit
majoritaire dans E il sut que e soit majoritaire dans E
1
et dans E
2
,
ou que e soit majoritaire dans E
1
et non dans E
2
(ou inversement),
mais quil apparaisse susamment dans E
2
.
Ecrivez une procedure de calcul correspondant `a cette idee. Quelle est
sa complexite ?
Une troisi`eme methode sera proposee au chapitre suivant.
20 CHAPITRE 2. ANALYSE DES ALGORITHMES
Chapitre 3
Structures lineaires
Les donnees que doivent traiter les programmes informatiques sont sou-
vent liees par des relations qui leur conf`erent une certaine structure : dans
certains jeux de cartes, on peut etre oblige de deposer des cartes au som-
met dun tas et navoir acc`es qu`a la derni`ere carte deposee : on parle de
structure de pile ; les processus envoyes `a une imprimante doivent etre geres
de mani`ere que le premier processus envoye soit le premier traite : on parle
de le dattente ; les positions sur un echiquier peuvent etre representes par
les noeuds dun arbre dont les successeurs sont toutes les positions attei-
gnables en un coup; les noeuds dun reseau de communication peuvent etre
representes par les sommets dungraphe, . . .
On a repertorie un certain nombre de structures de donnees qui re-
viennent dans la tr`es grande majorite des traitements informatique. Les
structures de donnees en informatique jouent un peu le role des struc-
tures abstraites en mathematiques, groupes, anneaux, corps, espaces vec-
toriels, . . . : elles sont susamment generales pour quil y ait avantage `a
les etudier independamment de toute application specique. On peut par
exemple etudier la question du tri dun tableau ou de la recherche dun
chemin dans un graphe sur des structures abstraites : les algorithmes qui
resolvent ces probl`emes dans le cas general pourront alors etre utilises dans
nimporte quelle situation specique.
Les langages de programmation proposent generalement des types simples,
quelques types plus complexes (tableaux, listes, etc) et des contructeurs de
types permettant dimplementer toutes les structures de donnees.
On parle de structure lineaire lorsque les donnees sont representees sequen-
tiellement : chaque element, sauf le dernier, poss`ede un successeur. On
etudiera en particulier les tableaux `a une dimension, les listes, les piles, les
21
22 CHAPITRE 3. STRUCTURES LIN

EAIRES
!
1
!
2
!
3
!
"
!
1
!
2
!
"
!
#
!
# +1
!
# +2
!
"
Insertion aprs les autres lments
Insertion dans un tableau tri
$
"%&
"
"%&
"!# recopies
$
Figure 3.1 Insertion dun element en n de tableau ou `a un indice donne.
les et les tables de hachage. Les matrices carrees, les arbres et les graphes
sont des structures non lineaires.
3.1 Tableaux
Un tableau (array) T est un ensemble delements accessibles par un indice
i [1 . . . n]. On suppose que le calcul du nombre delements dun tableau,
longueur(T) = n, lacc`es au i-`eme element T[i] et lajout dun element en
n de tableau peuvent etre realises en temps constant (O(1)). En revanche,
linsertion dun nouvel element `a un indice i donne necessite de deplacer
tous les elements suivants (temps lineaire dans le pire des cas). De meme
la recherche dun element dans un tableau non trie se fait en temps lineaire
dans le pire des cas. Nous avons vu precedemment que la recherche dun
element dans un tableau trie pouvait etre eectuee en temps logarithmique.
Implantation des tableaux en C
/* Definition */
#define NBMAX 1000 /* nombre maximum delements */
typedef int ELEMENT; /* les elements du tableau */
typedef ELEMENT TABLEAU[NBMAX];
3.2. LISTES CHA

IN

EES 23
/* Declaration */
TABLEAU t;
ou avec allocation dynamique de la memoire,
/* Definition */
typedef ELEMENT* TABLEAU;
/* Declaration */
TABLEAU t;
int nb_elts=50; /* nombre delements du tableau */
/* Allocation */
t=malloc(nb_elts*sizeof(ELEMENT));
3.2 Listes chanees
Une liste chanee (linked list) est une structure lineaire, composee de
maillons, chaque maillon comprenant un champ valeur qui permet de stocker
un element et un champ suivant qui pointe vers le maillon suivant ou est
egal `a NIL, sil sagit du dernier maillon de la liste. Une liste chainee L est
un objet qui est egal `a NIL si la liste est vide ou qui pointe vers un maillon,
le premier de la liste, si elle est non vide.
Implantation des listes chanees en C
/* Definition */
typedef int ELEMENT; /* par exemple */
typedef struct maillon *LISTE;
typedef struct maillon{
ELEMENT val;
LISTE suiv;
}MAILLON;
/* Declaration */
24 CHAPITRE 3. STRUCTURES LIN

EAIRES
i+2 i+1 i i!1
V V V V
prec p
prec !> suiv = CreerMaillon (x, prec !> suiv);
Cration et insertion d`un nouveau maillon avec la valeur x
x
Figure 3.2 Insertion dun element dans une liste `a une place donnee.
LISTE l;
/* Insertion dun element en t^ete dune liste */
LISTE CreerMaillon(ELEMENT elt, LISTE liste_initiale){
LISTE l;
l=malloc(sizeof(MAILLON));
l->val=elt;
l->suiv=liste_initiale;
return l;
}
On voit que linsertion dun element en tete de liste se fait en temps
constant.
Le traitement des listes chanees requiert de pouvoir :
inserer un element en queue de liste,
rechercher si un element est present dans la liste,
supprimer la premi`ere occurrence dun element,
inserer un element dans une liste ordonnee,
trier une liste,
vider une liste de ses elements.
Exercice 1
1. Quelle est la complexite dans le pire des cas des algorithmes precedents ?
2. Programmez-les en C.
3.2. LISTES CHA

IN

EES 25
liste
v1
v2 v3 bidon
Figure 3.3 Liste doublement chanee circulaire avec maillon vide.
Ameliorations de la structure de liste chanee Il nest pas possible
dacceder directement au maillon precedent le maillon courant dune liste
chanee. Cela complique notamment lecriture de lalgorithme de suppres-
sion dun maillon. Pour remedier `a ce defaut, on consid`ere des listes double-
ment chanees dans lesquels les maillons comprennent egalement un champ
precedent qui pointe vers le maillon precedent ou est egal `a NIL, sil sagit
du premier maillon de la liste.
Par ailleurs, les algorithmes de traitement des listes chanees sont alour-
dis par le fait quil faut traiter dieremment le premier maillon, qui na pas
de maillon precedent, des maillons suivants. Pour remedier `a cela, on intro-
duit un maillon vide, dont le champ val prend une valeur quelconque, et qui
constituera le premier maillon de la liste chanee.
Mais le meme probl`eme se pose alors pour le dernier maillon, qui nadmet
pas de maillon suivant. On suppose alors que le champ suivant du dernier
maillon pointe circulairement sur le maillon vide et que le champ precedent
du maillon vide pointe vers le dernier maillon.
On obtient ainsi la notion de liste doublement chanee circulaire avec
maillon vide (circular, doubly linked list, with a sentinel ).
Le tableau 3.5 compare la complexite de quelques operations elementaires
sur des tableaux et des listes chanees.
Exercice 2

Ecrire les algorithmes de traitement des listes doublement
chanees circulaires avec maillon vide.
Exercice 3 On represente un polynome `a coecients entiers par une liste
chainee dont les maillons poss`edent un champ coefficient et un champ
exposant ; on suppose de plus que les listes sont ordonnees par valeurs crois-
santes dexposant. Implantez cette structure de donnees en C et programmez
les fonctions suivantes :
26 CHAPITRE 3. STRUCTURES LIN

EAIRES
liste suppression de p
v1
v2 v3 bidon
Figure 3.4 Suppression dun maillon dans une liste doublement chanee
circulaire avec maillon vide.
Operation Tableau Tableau Liste Liste Liste Liste
trie ordonnee doublement ordonnee
chanee doublement
chanee
acc`es i-`eme element (1) (1) (n) (n) (n) (n)
insertion `a une (n) (n) (1) (1) (1) (1)
place donnee
recherche element (n) (log
2
n) (n) (n) (n) (n)
recherche succ. (1) (1) (1) (1) (1) (1)
recherche pred. (1) (1) (n) (n) (1) (1)
recherche maximum (n) (1) (n) (n) (n) (1)
recherche minimum (n) (1) (n) (1) (n) (1)
Figure 3.5 Comparatif tableaux / listes chanees.
3.3. PILES ET FILES 27
int degre(POLYNOME p)
void affiche(POLYNOME p)
POLYNOME somme(POLYNOME p1, POLYNOME p2)
POLYNOME multiplication scalaire(POLYNOME p, int a)
POLYNOME multiplication(POLYNOME p1, POLYNOME p2)
POLYNOME derivee(POLYNOME p)
float eval(POLYNOME p, float x)
3.3 Piles et les
Les piles (stack) et les les (queues) sont des structures lineaires qui
di`erent par la mani`ere dont les elements sont inseres et supprimes : dans
une pile, le dernier element entre est le premier sorti (Last In First Out :
LIFO) ; dans une le, le premier element entre est le premier sorti (First In
First Out : FIFO).
Trois fonctions (ou operations) susent `a faire fonctionner une pile :
la fonction booleenne pileVide ?(P) (StackEmpty(P)) qui retourne VRAI
si la pile P est vide et FAUX sinon,
la fonction empiler(P,x) (Push(P,x)) qui ins`ere un element x dans la
pile P,
la fonction depiler(P) (Pop(P)) qui retourne le dernier element insere
ou un message derreur si la pile est vide.
De meme, trois fonctions (ou operations) susent `a faire fonctionner une
le :
la fonction booleenne leVide ?(F) (QueueEmpty(F)) qui retourne VRAI
si la le F est vide et FAUX sinon,
la fonction enler(F,x) (EnQueue(F,x)) qui ins`ere un element x dans
la le F,
la fonction deler(F) (DeQueue(F)) qui retourne le premier element
insere ou un message derreur si la le est vide.
Toute implementation dune pile ou dune le necessite limplementation
des fonctions correspondantes.
Implementation dune pile par un tableau. Une pile peut etre representee
par les premiers elements dun tableau de taille xe et par un entier indi-
quant lindice du dernier element insere. La dimension du tableau etant xee,
il est necessaire dimplanter aussi une fonction booleenne PilePleine ? qui
28 CHAPITRE 3. STRUCTURES LIN

EAIRES
indiquera si la pile est pleine ou non. En C, cela peut se programmer de la
facon suivante :
/* Declarations */
#define TAILLE_MAX 1000 // Nombre maximal delements dans la pile
typedef int ELEMENT; /* pour une pile dentiers */
typedef struct {
ELEMENT elts[TAILLE_MAX];
int nbElts;} // nombre delements de la pile
PILE;
PILE p;
/* Initialisation */
[Link]=0;
/* retourne 1 si la pile p est vide, 0 sinon */
char pileVide(PILE p){
return ([Link]==0);
}
/* retourne 1 si la pile p est pleine, 0 sinon */
char pilePleine(PILE p){
return ([Link]==TAILLE_MAX);
}
/* empile lelement x sur la pile p, si celle-ci nest pas pleine */
void empiler(PILE *p, ELEMENT x){
assert(!pilePleine(*p));
p->elts[p->nbElts++]=x;
}
/* retourne lelement x au sommet de la pile p, si celle-ci nest pas vide */
ELEMENT depiler(PILE *p){
assert(!pileVide(*p));
return p->elts[--p->nbElts];
}
3.3. PILES ET FILES 29
Implementation dune le par un tableau. Une le peut etre representee
par les elements consecutifs dun tableau (circulaire) de taille xe et par
deux entiers indiquant lindice du premier element insere et le nombre to-
tal delements inseres. La dimension du tableau etant xee, il est necessaire
dimplanter une fonction booleenne FilePleine ? qui indiquera si la le est
pleine ou non. En C, cela peut se programmer de la facon suivante :
/* Declarations */
#define TAILLE_MAX 1000 // Nombre maximal delements dans la file
typedef int ELEMENT; /* pour une pile dentiers */
typedef struct {
ELEMENT elts[TAILLE_MAX];
int indPremierElt; // indice du premier element
int nbElts; // nombre delements
} FiLE;
FILE f;
/* Initialisation */
[Link]=[Link]=0;
/* retourne 1 si la file f est vide, 0 sinon */
char fileVide(FiLE f){
return ([Link]==0);
}
/* retourne 1 si la file f est pleine, 0 sinon */
char filePleine(FiLE f){
return ([Link]==TAILLE_MAX);
}
/* enfile lelement x dans la file f, si celle-ci nest pas pleine */
void enfiler(FiLE *f, ELEMENT x){
assert(!filePleine(*f));
f->elts[(f->indPremierElt+f->nbElts++) % TAILLE_MAX]=x;
}
/* retourne le premier element de la file f, si elle nest pas vide */
30 CHAPITRE 3. STRUCTURES LIN

EAIRES
ELEMENT defiler(FiLE *f){
assert(!fileVide(*f));
ELEMENT x=f->elts[f->indPremierElt];
f->nbElts--;
f->indPremierElt=(f->indPremierElt+1)%TAILLE_MAX;
return x;
}
Exercice 4 La notation post-xee des expressions arithmetiques, appelee
encore notation polonaise inversee, consiste `a ecrire les operandes avant les
operateurs. Lexpression ((3+(54)2) secrira par exemple 3 5 4 + 2 .
Aucune parenth`ese nest necessaire et levaluation dune telle expression se
fait simplement au moyen de lalgorithme suivant :
les termes sont parcourus de gauche `a droite ;
si le terme courant est un nombre, il est empile ;
si le terme courant est un operateur, les deux derniers nombres empiles
sont depiles, loperateur leur est applique et le resultat est empile ;
lorsque lexpression est totalement parcourue, la pile ne contient plus
quun seul element : le resultat de levaluation.
Ecrivez un programme qui evalue une expression `a partir de sa notation
post-xee (on supposera, pour simplier, que les operandes sont compris
entre 0 et 9).
Exercice 5 Quelles structures de listes chanees conviennent-elles le mieux
pour implementer un pile ? une liste ? Implementez ces structures en C, ainsi
que les fonctions correspondantes, au moyen de listes chanees.
Exercice 6 Calcul de lelement majoritaire (3`eme methode : les deux
premi`eres ont ete decrites dans des exercices de la section precedente).
Supposons que lon ait `a determiner sil existe une couleur majoritaire
parmi n balles colorees. On dispose dune etag`ere pour poser les balles les
unes `a cote des autres et dune corbeille pouvant contenir autant de balles
que necessaire. La methode se deroule en deux phases :
phase 1 : Prendre les balles les unes apr`es les autres en les mettant soit
sur letag`ere, si la derni`ere balle posee sur letag`ere est de couleur dierente,
soit dans la corbeille dans le cas contraire. Dans le premier cas on posera
ensuite sur letag`ere une balle prise au hasard dans la corbeille (sil y en a).
phase 2 : Soit C la couleur de la derni`ere balle posee sur letag`ere. On
jette les balles (pas dans la corbeille, dans la poubelle ! ) de letag`ere les unes
3.4. TABLES DE HACHAGE 31
apr`es les autres en commen cant par les derni`eres de la fa con suivante : (1)
si la balle `a jeter est de la couleur C et si elle a une voisine sur letag`ere, les
jeter toutes les deux, (2) si la derni`ere balle sur letag`ere nest pas de couleur
C, la jeter et jeter aussi une balle de la corbeille si elle nest pas vide, dans
le cas contraire on peut sarreter, il ny a pas delement majoritaire. Une
fois le processus termine, on regarde le contenu de la corbeille apr`es y avoir
mis eventuellement la deni`ere boule restant sur letag`ere : si la corbeille est
vide cest quil ny a pas de couleur majoritaire, sinon cest que la couleur
majoritaire est C.
1. Montrez qu`a tout moment de la phase 1, les balles de la corbeille, sil
y en a, sont toutes de la couleur de la derni`ere balle posee sur letag`ere.
En deduire qualors sil y a une couleur dominante cest cette couleur
la et que lalgorithme est donc correct.
2. Ecrivez lalgorithme en utilisant des piles. Quelle est la complexite
dans le pire des cas (en nombre de comparaisons de couleurs) ?
3.4 Tables de hachage
Les dictionnaires ou tableaux associatifs sont des structures de donnees
composees delements de la forme (cle,valeur) o` u chaque cle determine au
plus une valeur.
On peut par exemple considerer le dictionnaire compose du numero dun
etudiant inscrit `a luniversite dAix-Marseille et de son dossier, le diction-
naire compose dun numero de securite sociale et de lassure correspondant
ou du dictionnaire compose des mots du fran cais et de leur denition.
Les operations de base associees `a un dictionnaire sont : linsertion dun
nouvel element, la recherche dun element et la suppression dun element.
Lorsque les cles sont des entiers appartenant `a lintervalle [0 . . . n 1] (on
peut toujours se ramener `a ce cas) et lorsque n nest pas trop grand, les
dictionnaires peuvent etre implementes par des tableaux T `a adressage di-
rect dans lesquels les cles ne correspondant `a aucune valeur sont associees
conventionnellement `a une valeur NIL : en eet, inserer un element (c, x),
rechercher si element x de cle c est present ou supprimer lelement (c, x) se
fait en temps constant. Mais le cas le plus frequent est celui o` u le nombre
de valeurs renseignees est tr`es petit par rapport `a n : voir les exemples cites
precedemment.
32 CHAPITRE 3. STRUCTURES LIN

EAIRES
Si lon represente les n elements par une liste chanee, chaque operation
de base seectue en temps lineaire (par rapport `a n) : on souhaiterait pou-
voir les realiser en temps constant.
Les tables de hachage (hash tables) sont des structures de donnees qui
generalisent les tableaux au cas o` u lensemble U des cles possibles est gigan-
tesque par rapport au nombre de valeurs `a stocker. Lidee de base consiste
`a introduire une fonction de hachage
h : U [0 . . . m1]
telle que m soit de lordre du nombre de valeurs `a stocker et telle quen pra-
tique, le nombre de collisions, cest-`a-dire le nombre de cas o` u deux elements
distincts du dictionnaire (c, x) et (c

, x

) verient h(c) = h(c

) soit le plus
petit possible. Si lon pouvait assurer quil ny a pas de collisions, on pourrait
implementer le dictionnaire par un tableau T, chaque element (c, x) etant
represente par lelement T(h(c)). Mais il est en general impossible deviter
toute collision.
Deux questions doivent etre donc resolues :
1. comment gerer les collisions ?
2. comment denir une fonction de hachage minimisant le nombre de
collisions ?
3.4.1 Gestion des collisions par chanage externe
On appelle h(c) la position de lelement (c, x). Une collision correspond
donc `a deux elements du dictionnaire possedant la meme position. On choisit
de representer les elements ayant la meme position par une liste (simplement
ou doublement) chanee : T[i] pointe alors vers les elements dont la position
est i. Inserer, supprimer ou rechercher un element (c, x) est realise par les
operations correspondantes dans la liste chanee T(h(c)).
Le pire des cas est celui o` u tous les elements du dictionnaire occupent la
meme position! Dans ce cas, on est ramene au cas du stockage du diction-
naire dans une liste chanee et les operations de base seectuent en temps
lineaire. Mais si les cles se repartissent `a peu pr`es equitablement entre les
dierentes positions et si le nombre de position est de lordre du nombre
delement `a stocker, le nombre delements de chaque liste chanee est borne
par une constante et les operations de base peuvent donc etre realisees en
temps constant. Voir ci-dessous les algorithmes dinsertion et de recherche
dun element.
3.4. TABLES DE HACHAGE 33
0
1
2
3
4
5
table
e3 e7 e2
h(cl(e3)) = h(cl(e7)) = h(cl(2))
liste des objets
Figure 3.6 Gestion des collisions par chanage externe.
Algorithme 7: insertionTableHachage
entree : Table de Hachage T, element e de cle c
resultat : e est insere dans T
debut
Inserer e en tete de la liste chainee T(h(c)).
n
Fonction rechercheTableHachage(T,c)
entree : Table de Hachage T, cle c
sortie : un pointeur vers lelement de cle c ou NIL si lelement est
absent
debut
p = T[h(c)]
tant que p ,= NIL ET p ne pointe pas vers lelement de cle c
faire
p [Link]
ntq
retourner p
n
3.4.2 Gestion des collisions par adressage ouvert
La gestion des collisions par adressage ouvert consiste `a utiliser la table
de hachage elle-meme pour stocker les elements. Pour cela, on utilise une
34 CHAPITRE 3. STRUCTURES LIN

EAIRES
fonction de hachage modiee
h : U [0 . . . m1] [0 . . . m1]
telle que pour toute cle c, h(c, 0), . . . , h(c, m1) realise une permutation de
[0 . . . m1].
Pour inserer un nouvel un element e de cle c, on cherche le premier indice
i tel que T[h(c, i)] soit libre et on insere e dans T[h(c, i)] : toutes les cases
du tableau peuvent donc potentiellement recevoir tous les elements.
Pour savoir si un element de cle c est present dans T, on parcourt les
elements de la liste T[h(c, 0)], . . . , T[h(c, m1)] jusqu`a le trouver ou tomber
sur une case libre ou avoir parcouru toutes les cases du tableau.
En revanche, la suppression dun element est plus complexe car il ne
sut pas de vider la case qui le contient. En eet, supposons
que lelement de cle c soit stocke dans la case dindice h(c, i),
que lelement de cle c

ait ete stocke posterieurement `a lelement de

cle c dans la case dindice h(c

, i

),
quil existe un indice j < i

tel que h(c

, j) = h(c, i).
Si on lib`ere simplement la case T(h(c, i)), lelement de cle c

ne sera
plus trouve. Une solution consiste `a distinguer les cases libres des cases sup-
primees, dans lesquelles de nouvelles valeurs pourront etre inserees mais qui
ne devront pas etre considerees comme libres lors dune recherche delement.
Dapr`es louvrage de reference, la gestion des collisions par chanage externe
est plus souvent utilisee lorsquil doit y avoir des suppressions.
3.4.3 Fonctions de hachage
Une bonne fonction de hachage doit satisfaire la condition suivante :
les cles des elements du dictionnaire doivent se repartir (`a peu pr`es) uni-
formement entre les dierentes positions.
Des informations sur la distribution des cles peuvent permettre de denir
une fonction de hachage optimale. Cest par exemple le cas lorsquon sait que
les cles sont des nombres reels independamment et uniformement distribues
dans lintervalle [0, 1[, on peut utiliser la fonction h(c) = mc|.
En labsence dinformation, on cherche `a denir des fonctions de ha-
chage dependant le moins possible des donnees. On decrit ci-dessous deux
methodes courantes lorsque les cles sont des entiers, cas auquel on peut
toujours se ramener.
Methode par division On denit
h(c) = c mod m.
3.4. TABLES DE HACHAGE 35
La position de la cle c est son reste dans la division par m. Cest un methode
simple qui peut donner des resultats peu satisfaisants pour certaines valeurs
de m. Par exemple, si m = 2
p
est une puissance de 2, la position dune cle
ne depend que de ses p derniers bits ; si ceux-ci ne sont pas uniformement
repartis, la fonction de hachage correspondante ne sera pas uniforme non
plus.
En pratique, on recommande de choisir pour m un nombre premier pas
trop proche dune puissance de 2.
Methode par multiplication On denit
h(c) = mcA|
o` u A est un nombre reel tel que 0 < A < 1 et o` u x designe la partie
fractionnaire de x, cest-`a-dire x x|.
Cette methode est plus robuste que la precedente au choix des valeurs de
A et m. On choisit souvent m egal `a une puissance de 2 et Donald Knuth
1
sugg`ere de prendre A = (

5 1)/2 (cite dans louvrage de reference).

On peut toujours trouver des exemples qui mettent en defaut nimporte
quelle fonction de hachage, cest-`a-dire tels que presque toutes les cles se
retrouvent assignes une position unique. On peut remedier `a ce probl`eme
en introduisant des fonctions de hachage randomisees, mais ces techniques
depassent le niveau de ce cours.
Les techniques precedentes ne concernent que les methodes de hachage
par chanage externe. Si lon souhaite gerer les collisions par adressage
ouvert, on doit denir des fonctions de hachage `a deux arguments. Les
methodes le plus couramment utilisees sont :
le sondage lineaire (linear probing) : `a partir dune fonction de ha-
chage simple h : U [0 . . . m1], on denit la fonction h

: U[0 . . . m1]
[0 . . . m1] par
h

(c, i) = h(c) + i mod m.

On verie aisement que pour c xee, h

(c, i) parcourt toutes les valeurs de

[0 . . . m1] lors que i decrit [0 . . . m1].
Linconvenient principal de cette fonction est quelle a tendance `a creer
de longues suites consecutives de positions occupees, ce qui a pour eet de
ralentir le temps moyen de recherche dun element. Un moyen de remedier
`a cela est de considerer des increments qui ne soient pas constants.
1. Donald Knuth est lun des principaux pionniers en algorithmique et son livre The
art of computer programming reste une reference majeure.
36 CHAPITRE 3. STRUCTURES LIN

EAIRES
le sondage quadratique (quadratic probing) : `a partir dune fonction
de hachage simple h : U [0 . . . m 1], on denit la fonction h

: U
[0 . . . m1] [0 . . . m1] par
h

(c, i) = h(c) + ai + bi
2
mod m
o` u a et b sont des constantes auxiliaires. Voir dans un exercice ci-dessous un
exemple de choix de ces constantes lorsque m est une puissance de 2.
double hachage (double probing) : `a partir de deux fonctions de
hachage simples h
1
, h
2
: U [0 . . . m 1], on denit la fonction h

:
U [0 . . . m1] [0 . . . m1] par
h

(c, i) = h
1
(c) + ih
2
(c) mod m.
Pour que h

(c, i) realise une permutation de [0 . . . m1] pour toute position

h(c), il est necessaire que h
2
(c) soit premier avec m. Cest toujours le cas si
m est une puissance de 2 et si h
2
ne prend que des valeurs impaires, ou si
m est premier et si h
2
ne prend que des valeurs < m. On peut prendre par
exemple
h
1
(c) = c mod m et h
2
(c) = 1 + (c mod m1)
o` u m est premier.
La methode de double hachage est consideree comme lune des meilleures.
Exercice 7 On consid`ere lensemble des mots construits sur lalphabet
latin (26 lettres) et lon denit la fonction de hachage suivante :
h(c
0
c
1
. . . c
k
) = (c
0
+ 26c
1
+ . . . + 26
k
c
k
) mod m
o` u les lettres c
i
sont identiees `a leur numero 0 . . . 25 et o` u m est un
entier bien choisi.
1. Que se passe t-il si lon prend m = 26 ?
2. Montrez que si m = 25, tous les anagrammes ont la meme position.
3. Proposez une methode algorithmique pour calculer pratiquement la
position dun mot quelconque et programmez-la.
Exercice 8 Sondage quadratique. Montrez que si m = 2
p
, et si a = b = 1/2,
h(c) + ai + bi
2
mod m realise une permutation de [0 . . . m 1] quelle que
soit la valeur de h(c).
Exercice 9 Etudiez les valeurs prise par la fonction de double hachage
proposee ci-dessus pour m = 11.
Chapitre 4
Algorithmes de tris
Le tri dun ensemble dobjets consiste `a les ordonner en fonction de cles et
dune relation dordre denie sur cette cle. Le tri est une operation classique
et tr`es frequente. De nombreux algorithmes et methodes utilisent des tris.
Par exemple pour lalgorithme de Kruskal qui calcule un arbre couvrant de
poids minimum dans un graphe, une approche classique consiste, dans un
premier temps, `a trier les aretes du graphe en fonction de leurs poids. Autre
exemple, pour le probl`eme des elephants, trouver la plus longue sequence
delephants pris dans un ensemble donne, telle que les poids des elephants
dans la sequence soient croissants et que leurs Q.I. soient decroissants, une
approche classique consiste `a considerer une premi`ere suite contenant tous
les elephants ordonnes par poids croissants, une deuxi`eme suite avec les
elephants ordonnes par Q.I. decroissants, puis `a calculer la plus longue sous-
sequence commune `a ces deux suites. Trier un ensemble dobjets est aussi un
probl`eme simple, facile `a decrire, et qui se prete `a lutilisation de methodes
diverses et variees. Ceci explique linteret qui lui est porte et le fait quil est
souvent presente comme exemple pour les calculs de complexite.
Dans le cas general on sinteresse `a des tris en place, cest-`a-dire des tris
qui nutilisent pas despace memoire supplementaire pour stocker les objets,
et par comparaison, cest-`a-dire que le tri seectue en comparant les objets
entres eux. Un tri qui nest pas par comparaison necessite que les cles soient
peu nombreuses et connues `a lavance, et peuvent etre indexees facilement.
Un tri est stable sil preserve lordre dapparition des objets en cas degalite
des cles. Cette propriete est utile par exemple lorsquon trie successivement
sur plusieurs cles dierentes. Si lon veut ordonner les etudiants par rapport
`a leur nom puis `a leur moyenne generale, on veut que les etudiants qui ont
la meme moyenne apparaissent dans lordre lexicographique de leurs noms.
37
38 CHAPITRE 4. ALGORITHMES DE TRIS
Dans ce cours nous distinguerons les tris en O(n
2
) (tri `a bulle, tri par
insertion, tri par selection), les tris en O(n log n) (tris par fusion, tri par
tas et tri rapide, bien que ce dernier nait pas cette complexite dans le pire
des cas) et les autres (tris speciaux instables ou pas toujours applicables).
Il convient aussi de distinguer le co ut theorique et lecacite en pratique :
certains tris de meme complexite ont des performances tr`es dierentes dans
la pratique. Le tri le plus utilise et globalement le plus rapide est le tri rapide
(un bon nomquicksort) ; nous letudierons en TD.
En general les objets `a trier sont stockes dans des tableaux indexes, mais
ce nest pas toujours le cas. Lorsque les objets sont stockes dans des listes
chainees, on peut soit les recopier dans un tableau temporaire, soit utiliser
un tri adapte comme le tri par fusion.
4.1 Tri par selection, tri par insertion.
Le tri par selection consiste simplement `a selectionner lelement le plus
petit de la suite `a trier, `a lenlever, et `a repeter iterativement le processus
tant quil reste des elements dans la suite. Au fur et `a mesure les elements
enleves sont stockes dans une pile. Lorsque la suite `a trier est stockee dans
un tableau on sarrange pour representer la pile dans le meme tableau que
la suite : la pile est representee au debut du tableau, et chaque fois quun
element est enleve de la suite il est remplace par le premier element qui
apparat `a la suite de la pile, et prends sa place. Lorsque le processus sarrete
la pile contient tous les elements de la suite tries dans lordre croissant.
Le tri par insertion consiste `a inserer les elements de la suite les uns
apr`es les autres dans une suite triee initialement vide. Lorsque la suite est
stockee dans un tableau la suite triee en construction est stockee au debut
du tableau. Lorsque la suite est representee par une liste chainee on ins`ere
les maillons les uns apr`es les autres dans une nouvelle liste initialement vide.
i
partie trie
partie non trie
4.2. TRI PAR FUSION ET TRI RAPIDE 39
procedure TriParInsertion(E)
(InOut : E la suite (e
1
, . . . , e
n
))
debut
pour i := 2 jusqu`a n faire
j := i, v := e
i
,
tant que ((j > 1) et (v < e
j1
)) faire
e
j
:= e
j1
,
j := j 1,
n faire
e
j
:= v,
n faire
n procedure
Le tri eectue n 1 insertions. A la i`eme iteration, dans le pire des cas,
lalgorithme eectue i 1 recopies. Le co ut du tri est donc
n
i=2
(i 1) =
O(n
2
). Remarquons que dans le meilleur des cas le tri par insertion requiert
seulement O(n) traitements. Cest le cas lorsque lelement `a inserer reste `a
sa place, donc quand la suite est deja triee (lorsque la suite est stockee dans
une liste chainee cest la cas lorsque la liste est triee `a lenvers puisquon
ins`ere en tete de liste).
4.2 Tri par fusion et tri rapide
4.2.1 Tri par fusion
Le tri par fusion (merge sort en anglais) implemente une approche de
type diviser pour regner tr`es simple : la suite `a trier est tout dabord scindee
en deux suites de longueurs egales `a un element pr`es. Ces deux suite sont
ensuite triees separement avant detre fusionnees. Lecacite du tri par fu-
sion vient de lecacite de la fusion : le principe consiste `a parcourir simul-
tanement les deux suites triees dans lordre croissant de leur elements, en
extrayant chaque fois lelement le plus petit.
Le tri par fusion est bien adapte aux listes chainees : pour scinder la liste
il sut de la parcourir en liant les elements de rangs pairs dun cote et les
elements de rangs impairs de lautre. La fusion de deux listes chainees se fait
facilement. Inversement, si la suite `a trier est stockee dans un tableau il est
necessaire de faire appel `a un tableau annexe lors de la fusion, sous peine
davoir une complexite en O(n
2
).
40 CHAPITRE 4. ALGORITHMES DE TRIS
Fonction TriParFusion(S)
Data : S : la suite `a trier
begin
if [S[ 1 then
scinder la suite S en deux suites S
1
et S
2
de longueurs egales;
S
1
:= TriParFusion (S
1
);
S
2
:= TriParFusion (S
2
);
S := fusion (S
1
, S
2
);
return S;
Dans le cas general, on peut evaluer `a O(n) le co ut de la scission de la
suite S et `a O(n) le co ut de la fusion des suites S
1
et S
2
. Lequation recursive
du tri par fusion est donc
T(n) = 1 + O(n) + 2 T(n/2) + O(n)
On en deduit que le tri par fusion est en O(n log n). On le verie en
cumulant les nombres de comparaisons eectuees `a chaque niveau de larbre
qui represente lexecution de la fonction (voir gure ci-dessous) : chaque
noeud correspond `a un appel de la fonction, ses ls correspondent aux deux
appels recursifs, et son etiquette indique la longueur de la suite. La hauteur
de larbre est donc log
2
n et `a chaque niveau le cumul des traitements locaux
(scission et fusion) est O(n), do` u on deduit un co ut total de O(n) log
2
n =
O(n log n).
n
2x
n 2x
n 2x
n
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
1 1 1 ....
log
n
La fusion peut-etre eectuee en conservant lordre des elements de meme
valeur (le tri par fusion est stable), mais elle necessite lutilisation de ta-
bleaux auxiliaires (au moins dans ses implementations les plus courantes).
4.2. TRI PAR FUSION ET TRI RAPIDE 41
Exercice 1

Ecrivez lalgorithme de fusion.
4.2.2 Tri rapide
Le tri rapide est une methode de type diviser pour regner. Lidee de base
est la suivante : pour trier la suite S = (s
g
, . . . , s
d
) on la partitionne en deux
sous suites non vides S

= (s
g
, . . . , s
q
) et S

= (s
q
, . . . , s
d
) telles que les
elements les plus petits sont dans la premi`ere et les elements les plus grands
dans la seconde. En appliquant recursivement le tri sur les suites S

et S

la suite S est triee.

Il existe plusieurs methodes pour partitionner une suite. Le principe
general consiste `a utiliser un element particulier de la suite, le pivot, comme
valeur de partage. Il faut faire tr`es attention `a ne pas produire une suite vide
et lautre contenant tous les elements de la suite initiale, auquel cas le tri
risque de boucler indeniment. Une facon simple de contourner ce probl`eme
est disoler les elements de meme valeur que le pivot. Ces elements sont
simplement places entre les deux sous suites apr`es la partition, cest leur
place denitive.
Nous allons ecrire plusieurs versions de la partition, en utilisant des ta-
bleaux pour stocker les elements de la suite `a trier.
Question 1. Ecrivez une fonction partition en O(n) o` u n est le nombre
delements de la suite en vous inspirant de la methode dite du drapeau :
la partie du tableau o` u sont stockes les elements de la suite est segmentee
en quatre zones, contenant respectivement des elements de valeur inferieure
au pivot, des element de meme valeur que le pivot, des elements de valeur
superieure au pivot et enn les elements restant (qui nont pas encore ete
traites). Le partitionnement consiste simplement `a prendre un element de
la derni`ere zone et `a lajouter dans lune des trois premi`eres zones suivant
sa valeur, puis `a repeter cette operation tant quil reste des elements non
traites.
Question 2. Ecrivez une fonction recursive de tri rapide qui utilise la fonc-
tion de partition precedente.
Question 3 . En terme de complexite, quel est pire des cas pour le tri
rapide, et comment eviter ce cas avec une bonne probabilite.
Question 4. Il existe une fa con plus ecace pour partitionner la suite : le
principe general consiste `a parcourir la suite simultanement en partant de
42 CHAPITRE 4. ALGORITHMES DE TRIS
la gauche (et en allant vers la droite) et en partant de la droite (et en allant
vers la gauche), an de trouver `a gauche une valeur superieure `a la valeur du
pivot, et `a droite une valeur inferieure `a la valeur du pivot. Il sut ensuite
dechanger ces deux valeurs et de continuer le processus tant que les deux
indices ne se sont pas croises. Cette partition produit deux sous suites, lune
contenant des valeurs plus petites ou egales `a la valeur du pivot et lautre
contenant des valeurs plus grandes ou egales `a la valeur du pivot. Ecrivez une
fonction de partition qui suit ce schema et justiez la, cest `a dire demontrez
quelle se termine et que le resultat est le bon. En particulier il vous faut
demontrer quaucune des deux suites produites ne peut etre vide.
Ecrivez une nouvelle version du tri rapide qui integre cette partition.
Question 5. Ecrivez une fonction qui, etant donne un entier k et une suite
S, renvoie la valeur du k`eme plus petit element du tableau, cest `a dire de
lelement de rang k dans la suite triee. Cette fonction fera appel `a la fonction
partition. Dans quels cas cette methode est-elle meilleure que si on avait
tout dabord trie la suite.
4.3 Complexite optimale dun algorithme de tri
par comparaison
Larbre de decision dun tri par comparaison represente le comporte-
ment du tri dans toutes les congurations possibles. Les congurations cor-
respondent `a toutes les permutations des objets `a trier, en supposant quils
soient tous comparables et de cles dierentes. Sil y a n objets `a trier, il
y a donc n! congurations possibles. On retrouve toutes ces congurations
sur les feuilles de larbre, puisque deux permutations initiales distinctes ne
peuvent pas produire le meme comportement du tri : en eet, dans ce cas le
tri naurait pas fait son travail sur un des deux ordonnancements. Chaque
noeud de larbre correspond `a une comparaison entre deux elements et a
deux ls, correspondants aux deux ordres possibles entre ces deux elements.
4.3. COMPLEXIT

E OPTIMALE DUNALGORITHME DE TRI PAR COMPARAISON43

c b a
c b a
c b a
b c a c b a
b c a b c a c a b a c b
a c b
c b a
e1 > e2 e1 <= e2
e2 > e3
e2 <= e3
3 2 1
<= >
<= > <=
> <=
>
> <=
Sur la gure ci-dessus nous avons represente larbre de decision du tri
par insertion sur une suite de trois elements. A la racine de larbre le tri
compare tout dabord les deux premiers elements de la suite a et b, an
dinserer lelement b dans la suite triee constituee uniquement de lelement
a. Suivant leur ordre les deux elements sont permutes (ls droit) ou laisses
en place (ls gauche). Au niveau suivant lalgorithme compare les elements
de rang 2 et de rang 3 an dinserer lelement de rang 3 dans la suite triee
constituee des 2 premiers elements, et ainsi de suite. Remarquons que les
branches de larbre de decision du tri par insertion nont pas toutes la meme
longueur du fait que dans certains cas linsertion dun element est moins
couteuse, en particulier quand lelement est deja `a sa position.
Puisque le nombre de permutations de n elements est n!, larbre de
decision dun tri a donc n! feuilles. La hauteur dun arbre binaire de n!
feuilles est, dans le meilleur des cas, cest-`a-dire si larbre est parfaitement
equilibre (le nombre de noeuds est multiplie par deux chaque fois quon
descend dun niveau)
h = log(n!)
or, dapr`es la formule de Stirling,
log(n!) log

n
e

n
n log n n log e
et donc la hauteur minimale de larbre est de lordre de n log n.
44 CHAPITRE 4. ALGORITHMES DE TRIS
On en conclut quaucun tri par comparaison ne peut avoir une complexite
meilleure que O(n log n).
4.4 Tri par tas.
Un tas (heap en anglais) ou le de priorite (priority queue) est un arbre bi-
naire etiquete presque compl`etement equilibre : tous ses niveaux sont remplis
sauf peut-etre le dernier, qui est rempli `a partir de la gauche jusqu`a un cer-
tain noeud. On denit ensuite une propriete sur les tas : chaque noeud est
dans une relation dordre xee avec ses ls. En general on consid`ere des
tas dans lesquels chaque noeud a une valeur plus petite que celles de ses
ls. Pour le tri par tas on utilise des arbres maximiers (max-heap), cest-`a-
dire des tas dans lesquels chaque noeud porte une valeur plus grande que
celles de ses ls. La valeur la plus grande du tas se trouve donc `a la racine.
Les operations et les techniques presentees dans ce chapitre pour des arbres
maximiers sappliquent de la meme facon `a des tas bases sur lordre inverse.
Les operations essentielles sur les tas sont :
la construction du tas,
lextraction du maximum,
lajout dune nouvelle valeur,
la modication de la valeur dun noeud.
Habituellement les tas sont des arbres binaires representes dans des tableaux.
Les valeurs du tas sont stockees dans les premi`eres cases du tableau. Si le
tas est compose de n elements, ces derniers apparaissent donc aux indices
0, 1,. . . ,n1. La racine du tas gure dans la case dindice 0. La disposition
des elements du tas dans le tableau correspond `a un parcours de larbre par
niveau, en partant de la racine et de gauche `a droite.
4.4. TRI PAR TAS. 45
2
hauteur log n
7
1 5
11
3
8 4 2
7
13
10
0
2
3
1
4 5 6
9 8
Le ls gauche du noeud qui gure `a lindice i, sil existe, se trouve `a
lindice FilsG(i) = 2 i + 1, et son ls droit, sil existe, se trouve `a lindice
FilsD(i) = 2 i + 2. Inversement, le p`ere du noeud dindice i non nul se
trouve `a lindice
i1
2
|.
n1
5 1 4 8 2 0 5
2 1 3 4 5 7 8 9 10 11 0
6
fils droit
fils gauche
3 10 7 11 13
Cette disposition entrane que larbre est forcement equilibre (i.e. toutes
ses branches ont la meme longueur `a un element pr`es), et les plus longues
branches sont `a gauche. La hauteur dun tas, i.e. son nombre de niveaux,
contenant n elements est donc log
2
n| +1 (le nombre de fois que lon peut
diviser n par 2 avant dobtenir 1). Si le dernier noeud du tas se trouve `a
la position n 1, son p`ere se trouve `a la position
n
2
1|. Cest le dernier
noeud qui a au moins un ls. Les feuilles de larbre se trouvent donc entre la
position
n
2
et la position n 1 dans le tableau puisquil ny a pas de feuilles
avant le dernier p`ere.
Loperation Entasser est une operation de base sur les tas. Elle est utilisee
notamment pour la construction des tas ou encore pour lextraction de la
46 CHAPITRE 4. ALGORITHMES DE TRIS
valeur maximale. Elle consiste `a reconstruire le tas lorsque seule la racine
viole (eventuellement) la propriete de superiorite entre un noeud et ses ls,
en faisant descendre dans larbre lelement fautif par des echanges successifs.
14
1
2 8 4
1
2 8 4
9
7
5 10
14
13 1
2 8 4
7
5
9
10
13
7
5
13
9 10
14
Fonction Entasser(i,T,n)
entree : T est un tas ; le ls gauche et le ls droit du noeud dindice i
verient la propriete Max-heap ; ce nest pas forcement le
cas du noeud dindice i.
sortie : La propriete max-heap est veriee par le noeud dindice i.
debut
iMax i
si (FilsG(i) < n) ET (T[FilsG(i)] > T[iMax]) alors
iMax := FilsG(i)
si (FilsD(i) < n) ET (T[FilsD(i)] > T[iMax]) alors
iMax := FilsD(i)
si (iMax ,= i) alors
Echanger T[i] et T[iMax]
Entasser(iMax,T,n)
La fonction proc`ede de la fa con suivante : si lon na pas atteint une feuille ou
que la valeur du noeud courant dindice i viole la propriete de superiorite des
p`eres sur leurs ls, on echange cette valeur avec la plus grande des valeurs
des ls. De cette facon le noeud dindice i aura une valeur plus grande que
les valeurs de ses ls. On reit`ere loperation tant que la propriete de tas nest
pas retablie.
La fonction Entasser a un co ut en O(log
2
n) puisque, dans le pire des
cas, il faudra parcourir une branche enti`erement.
Extraction de la valeur maximale. La valeur maximale dun tas qui
verie la propriete Max-heap est `a la racine de larbre. Pour un tas de taille
4.4. TRI PAR TAS. 47
n stocke dans le tableau T cest la valeur T[0] si n est non nul. Lextraction
de la valeur maximale consiste ` a recopier en T[0] la derni`ere valeur du tas
T[n1], `a decrementer la taille du tas, puis `a appliquer loperation Entasser
`a la racine du tas, an que la nouvelle valeur de la racine prenne sa place.
fonction ExtraireLeMax(T, n)
max := T[0],
T[0] := T[n 1],
Entasser(0, T, n 1),
renvoyer max, T, n 1),
n fonction
Inserer une nouvelle valeur dans un tas consiste `a ajouter la valeur `a la
n du tas, en derni`ere position dans le tableau, puis `a la faire remonter dans
le tas en lechangeant avec son p`ere tant quelle ne se trouve pas `a la racine
et que la valeur de son p`ere lui est inferieure. Loperation dinsertion nest
pas utile pour le tri par tas.
Principe general du tri par tas. Supposons que lon ait `a trier une
suite de n valeurs stockee dans un tableau T. On commence par construire
un tas dans T avec les valeurs de la suite. Ensuite, tant que le tas nest pas
vide on rep`ete lextraction de la valeur maximale du tas. Chaque fois, la
valeur extraite est stockee dans le tableau immediatement apr`es les valeurs
du tas. Lorsque le processus se termine on a donc la suite des valeurs triee
dans le tableau T.
Construction du tas.
Les valeurs de la suite `a trier sont stockees dans le tableau T. La procedure
consiste `a parcourir les noeuds qui ont des ls et `a leur appliquer loperation
Entasser, en commen cant par les noeuds qui sont `a la plus grande profondeur
dans larbre. Il sut donc de parcourir les noeuds dans lordre decroissant
des indices et en partant du dernier noeud qui a des ls, le noeud din-
dice (n/2)| 1. Lordre dans lequel les noeuds sont traites garantit que les
sous-arbres sont des tas.
fonction ConstruireUnTas(T, n)
pour i := n/2 1 jusqu`a 0 faire
Entasser(i, T, n),
n fonction
48 CHAPITRE 4. ALGORITHMES DE TRIS
Complexite de la construction. De facon evident la complexite est au
plus O(n log n). En eet la hauteur du tas est log n et on eectue n/2 fois
loperation Entasser. En fait le co ut de la construction est O(n). La fonction
eectue un grand nombre dentassements sur des arbres de petites hauteur
(pour les noeuds les plus profonds), et tr`es peu dentassements sur la hauteur
du tas. Considerons pour simplier un tas complet, cest-`a-dire dans lequel
toutes les branches ont la meme longueur. On denombre
n
2
noeuds `a la hau-
teur 0 (les feuilles),
n
2
2
noeuds `a la hauteur 1,
n
2
3
noeuds `a la hauteur 2,. . . ,
On a donc
n
2
h+1
noeuds `a la hauteur h, pour chacun desquels on eectuera
au plus h echanges dans loperation Entasser. Le co ut de la construction du
tas est donc borne par
log n

h=1

n
2
h+1
| h n
log n

h=1
h
2
h
Puisque

i=0
i x
i
=
x
(1 x)
2
on a

h=0
h
2
h
=
1/2
(1 1/2)
2
= 2
et donc le nombre dechanges est borne par
n
log n

h=0
h
2
h
2 n = O(n)
Tri par tas.
On construit un tas. On utilise le fait que le premier element du tas est le
plus grand : autant de fois quil y a delements, on extrait le premier du tas et
on reconstruit le tas avec les elements restants. Enlever le premier element
consiste simplement `a lechanger avec le dernier du tas et `a decrementer
la taille du tas. On retablit la propriete de tas en appliquant loperation
Entasser sur ce premier element.
4.5. TRI PAR D

ENOMBREMENT, TRI PAR BASE. 49

fonction TriParTas(T, n)
ConstruireUnTas(T, n),
pour i := n 1 jusqu`a 1 faire
Echanger(T, 0, i),
Entasser(0, T, i),
n fonction
La construction du tas co ute O(n). On eectue ensuite n fois un echange et
loperation Entasser sur un tas de hauteur au plus logn. La complexite du
tri par tas est donc O(n log n).
4.5 Tri par denombrement, tri par base.
4.5.1 Tri par denombrement
Le tri par denombrement (counting sort) est un tri sans comparaisons
qui est stable, cest-`a-dire quil respecte lordre dapparition des elements
dont les cles sont egales. Un tri sans comparaison suppose que lon sait in-
dexer les element en fonction de leur cle. Par exemple, si les cles des elements
`a trier sont des valeurs enti`eres comprises entre 0 et 2, on pourra parcourir
les elements et les repartir en fonction de leur cle sans les comparer, juste
en utilisant les cles comme index. Le tri par denombrement utilise cette pro-
priete pour tout dabord recenser les elements pour chaque valeur possible
des cles. Ce comptage preliminaire permet de connatre, pour chaque cle c,
la position nale du premier element de cle c qui apparat dans la suite `a
trier. Sur lexemple ci-dessous on a recense dans le tableau T, 3 elements
avec la cle 0, 4 elements avec la cle 1 et 3 elements avec la cle 2. On en
deduit que le premier element avec la cle 0 devra etre place `a la position 0,
le premier element avec la cle 1 devra etre place `a la position 3, et le pre-
mier element avec la cle 2 devra etre place `a la position 7. Il sut ensuite
de parcourir une deuxi`eme fois les elements `a trier et de les placer au fur et
`a mesure dans un tableau annexe (le tableau R de la gure), en noubliant
pas, chaque fois quun element de cle c est place, dincrementer la position
de lobjet suivant de cle c. De cette fa con les elements qui ont la meme cles
apparaissent necessairement dans lordre de leur apparition dans le tableau
initial.
50 CHAPITRE 4. ALGORITHMES DE TRIS
T
4 9 3
placement de T[3] en R[2]
placement de T[2] en R[8]
4 9 2
placement de T[1] en R[1] 4 8 2
1 3 1 2 3 2 1 3 2 2
Nombres dapparitions
3 4 3
Indices des premiers placer
4 1 8
3 2 1
1 2 3 4 5 6 7 8 9 10
1 2 3
T
R 1 1 2 2 3 1 2 2 3 3
1 3 1 2 3 2 1 3 2 2
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
fonction TriParDenombrements(T, n)
In : T un tableau de n elements
Out : R le tableau trie des elements de T
debut
pour i := 1 `a k faire initialisations
Nb[i] := 0,
pour i := 1 `a n faire calcul des nombres dapparitions
Nb[T[i]] := Nb[T[i]] + 1,
Nb[k] := n Nb[k] + 1, calcul des indices du premier
pour i := k 1 `a 1 faire element de chaque categorie
Nb[i] := Nb[i + 1] Nb[i],
pour i := 1 `a n faire recopie des element originaux
R[Nb[T[i]]] := T[i], du tableau T dans R
Nb[T[i]] := Nb[T[i]] + 1,
renvoyer R
n procedure
La suite des objets `a trier est parcourue deux fois, et la table Nb conte-
nant le nombre doccurrences de chaque cle est parcourue une fois pour
linitialiser. La complexite nale est donc O(n+k) si les cles des elements `a
trier sont comprises entre 0 et k. Le tri par denombrement est dit lineaire
(modulo le fait que k doit etre comparable `a n).
4.5. TRI PAR D

ENOMBREMENT, TRI PAR BASE. 51

4.5.2 Tri par base.
Le tri par denombrement est dicilement applicable lorsque les valeurs
que peuvent prendre les cles sont tr`es nombreuses. Le principe du tri par
base (radix sort) consiste, dans ce type de cas, `a fractionner les cles, et `a
eectuer un tri par denombrement successivement sur chacun des fragments
des cles. Si on consid`ere les fragments dans le bon ordre (i.e. en commencant
par les fragments de poids le plus faible), apr`es la derni`ere passe, lordre des
elements respecte lordre lexicographique des fragments, et donc la suite est
triee.
Considerons lexemple suivant dans lequel les cles sont des nombres
entiers `a au plus trois chires. Le fractionnement consiste simplement `a
prendre chacun des chires de lecriture decimale des cles. La colonne de
gauche contient la suite des valeurs `a trier, la colonne suivante contient ces
memes valeurs apr`es les avoir trie par rapport au chire des unites,. . . Dans
la derni`ere colonne les valeurs sont eectivement triees. Du fait que le tri par
denombrement est stable, si des valeurs ont le meme chire des centaines,
alors elles apparaitront dans lordre croissant de leurs chires des dizaines,
et si certaines ont le meme chire des dizaines alors elles apparaitront dans
lordre croissant des chires des unites.
536 592 427 167
893 462 536 197
427 893 853 427
167 853 462 462
853 536 167 536
592 427 592 592
197 167 893 853
462 197 197 893
Supposons que lon ait n valeurs dont les cles sont fractionnees en c
fragments avec k valeurs possibles pour chaque fragment. Le co ut du tri
par base est alors O(c n + c k) puisque lon va eectuer c tris par
denombrement sur n elements avec des cles qui auront k valeurs possibles.
Si k = O(n) on peut dire que le tri par base est lineaire. Dans la pratique,
sur des entiers codes sur 4 octets que lon fragmente en 4, le tri par base est
moins rapide que le tri rapide (Quick Sort).
52 CHAPITRE 4. ALGORITHMES DE TRIS
4.6 Tri shell.
Cest une variante du tri par insertion. Le principe du tri shell est de
trier separement des sous-suites de la table formees par des elements pris de
h en h dans la table (on nommera cette operation h-ordonner).
Denition. La suite E = (e
1
, . . . , e
n
) est h-ordonnee si pour tout indice
i n h, e
i
e
i+h
.
Si h vaut 1 alors une suite h-ordonnee est triee.
Pour trier, Donald Shell le createur de ce tri, propose de h-ordonner la
suite pour une serie decroissante de valeurs de h. Lobjectif est davoir une
serie de valeurs qui permette de confronter tous les elements entres eux le
plus souvent et le plus tot possible. Dans la procedure ci-dessous la suite des
valeurs de h est : . . . , 1093, 364, 121, 40, 13, 4, 1.
La complexite de ce tri est O(n
2
). Avec la suite de valeurs de h precedente
on atteint O(n
3/2
) (admis). Cependant dans la pratique ce tri est tr`es per-
formant et facile `a implementer (conjectures O(n (logn)
2
) ou n
1,25
).
procedure TriShell(E)
(InOut : E la suite (e
1
, . . . , e
n
))
debut
h := 1,
tant que h n/9 faire
h := 3 h + 1,
n faire
tant que h > 0 faire
Tri par insertion pour h-ordonner E
pour i := h + 1 jusqu`a n faire
j := i, v := e
i
,
tant que ((j > h) et (v < e
jh
)) faire
e
j
:= e
jh
, j := j h,
n faire
e
j
:= v,
n faire
h := h/3,
n faire
n procedure
On notera que le tri utilise pour h-ordonner la suite est un tri par inser-
tion. La derni`ere fois que ce tri est applique (avec h qui vaut 1) on execute
donc simplement un tri par insertion. Les passes precedentes ont permis de
4.6. TRI SHELL. 53
mettre en place les elements de fa con `a ce que cette ultime execution du tri
par insertion soit tr`es peu couteuse.
54 CHAPITRE 4. ALGORITHMES DE TRIS
Chapitre 5
Arbres binaires de recherche,
arbres lexicographiques
Les arbres et les structures arborescentes sont tr`es utilises en informa-
tique. Dune part les informations sont souvent hierarchisees, et se presentent
donc naturellement sous une forme arborescente, et dautre part de nom-
breuses structures de donnees parmi les plus ecaces sont representees par
des arbres (les tas, les arbres binaires de recherches, les B-arbres, les forets,
. . . ).
5.1 Quelques exemples
Expressions arithmetiques. On represente souvent des expressions
arithmetiques avec des arbres etiquetes par des operateurs, des constantes
et des variables. La structure de larbre elimine les ambiguites qui peuvent
apparatre en fonction des priorites des operateurs et qui sont supprimees
en utilisant des parenth`eses.
55
56CHAPITRE 5. ARBRES BINAIRES DE RECHERCHE, ARBRES LEXICOGRAPHIQUES
2
75 /
y
t
x
+
z
(y/2 t) (75 + z)
Arbres syntaxiques. Un arbre syntaxique represente lanalyse dune
phrase `a partir dun ensemble de r`egles qui constitue la grammaire : une
phrase est composee dun groupe nominal suivi dun groupe verbal, un
groupe nominal peut-etre constitue dun article et dun nom commun,. . .
livre
groupe nominal
verbe complment
phrase
article nom commun
article nom commun
le chat lit
le
groupe verbal
Arbres genealogiques. Un arbre genealogique (descendant dans le
cas present) represente la descendance dune personne ou dun couple. Les
noeuds de larbre sont etiquetes par les membres de la famille et leurs
conjoints. Larborescence est construite `a partir des liens de parente (les
enfants du couple).
5.2. D

EFINITIONS ET TERMINOLOGIE 57
Lucie Matto
Paul
Victor
Naomi
Ginette
Georges
Lilly Tom
Lon Mlanie Tho
Arbre lexicographique. Un arbre lexicographique, ou arbre en parties
communes, ou dictionnaire, represente un ensemble de mots. Les prexes
communs `a plusieurs mots apparaissent une seule fois dans larbre, ce qui
se traduit par un gain despace memoire. De plus la recherche dun mot est
assez ecace, puisquil sut de parcourir une branche de larbre en partant
de la racine, en cherchant `a chaque niveau parmi les ls du noeud courant
la lettre du mot de rang correspondant.
e
e
l
t
r e
o
t
i
l s
m
a
e
i
p
i c
n e
.
male
mie
mite
pic
pile
pis
port
porte
main
5.2 Denitions et terminologie
Denition. Un arbre est un ensemble organise de noeuds dans lequel
chaque noeud a un p`ere et un seul, sauf un noeud que lon appelle la racine.
Si le noeud p est le p`ere du noeud f, nous dirons que f est un ls de p, et
si le noeud p na pas de ls nous dirons que cest une feuille. Chaque noeud
porte une etiquette ou valeur ou cle. On a lhabitude, lorsquon dessine un
58CHAPITRE 5. ARBRES BINAIRES DE RECHERCHE, ARBRES LEXICOGRAPHIQUES
arbre, de le representer avec la tete en bas, cest-`a-dire que la racine est tout
en haut, et les noeuds ls sont representes en-dessous du noeud p`ere.
racine
feuilles
Un noeud est deni par son etiquette et ses sous-arbres. On peut donc
representer un arbre par un n-uplet e, a
1
, . . . , a
k
) dans lesquel e est letiquette
portee par le noeud, et a
1
, . . . , a
k
sont ses sous-arbres. Par exemple larbre
correspondant `a lexpression arithmetique (y/2t)(75+z) sera represente
par
, , /, y), 2)), t)), +, 75), z)))
On distingue les arbres binaires des arbres generaux. Leur particula-
rite est que les ls sont singularises : chaque noeud a un ls gauche et un
ls droit. Lun comme lautre peut etre un arbre vide, que lon notera ).
Lecriture dun arbre sen trouve modiee, puisquun noeud a toujours deux
ls. En reprenant lexpression arithmetique precedente, larbre binaire qui
la represente secrit
, , /, y, ), )), 2, ), ))), t, ), ))), +, 75, ), )), z, ), ))))
On utilise pour les arbres une terminologie inspiree des liens de parente :
les descendants dun noeud p sont les noeuds qui apparaissent dans
ses sous-arbres,
un ancetre dun noeud p est soit son p`ere, soit un ancetre de son p`ere,
le chemin qui relie un noeud `a la racine est constitue de tous ses
ancetres (cest-` a-dire de son p`ere et des noeuds du chemin qui relie
son p`ere `a la racine),
un fr`ere dun noeud p est un ls du p`ere de p, et qui nest pas p.
5.2. D

EFINITIONS ET TERMINOLOGIE 59
hauteur=5
descendant
ancetre
niveaux
profondeur=2
noeud de degr 3
racine
frre
chemin la racine
Les noeuds dun arbre se repartissent par niveaux : le premier niveau
(par convention ce sera le niveau 0) contient la racine seulement, le deuxi`eme
niveau contient les deux ls de la racine,. . . , les noeuds du niveau k sont les
ls des noeuds du niveau k 1,. . . . La hauteur dun arbre est le nombre de
niveaux de ses noeuds. Cest donc aussi le nombre de noeuds qui jalonnent
la branche la plus longue. Attention, la denition de la hauteur varie en
fonction des auteurs. Pour certains la hauteur dun arbre contenant un seul
noeud est 0.
Arbres binaires : hauteur, nombre de noeuds et nombre de
feuilles.
Un arbre binaire est complet si toutes ses branches ont la meme longueur
et tous ses noeuds qui ne sont pas des feuilles ont deux ls. Soit A un arbre
binaire complet. Le nombre de noeuds de A au niveau 0 est 1, le nombre de
noeuds au niveau 1 est 2,. . . , et le nombre de noeuds au niveau p est donc
2
p
. En particulier le nombre de feuilles est donc 2
h1
si h est le nombre de
niveaux.
16
8
4
2
1
racine
n
o
m
b
r
e

d
e

n
o
e
u
d
s
60CHAPITRE 5. ARBRES BINAIRES DE RECHERCHE, ARBRES LEXICOGRAPHIQUES
Le nombre total de noeuds dun arbre binaire complet de h niveaux est
h1

i=0
2
i
= 2
h
1
On en deduit que la hauteur ht(A) (le nombre de niveaux) dun arbre
binaire A contenant n noeuds est au moins egale `a
log
2
n| + 1
Preuve. Si A est arbre de hauteur h et comportant n noeuds, pour tout
entier m, on a : h m1 n < 2
m1
. Par contraposee, on a : n 2
m1

h m. Le plus grand entier m veriant n 2

m1
est log
2
n| + 1. On a
donc h log
2
n| + 1.
La hauteur minimale log
2
n| + 1 est atteinte lorsque larbre est com-
plet. Pour etre ecaces, les algorithmes qui utilisent des arbres binaires font
en sorte que ceux ci soient equilibres (voir les tas ou les AVL-arbres par
exemple).
Les arbres en theorie des graphes. En theorie des graphes un arbre
est un graphe connexe et sans cycles, cest-`a-dire quentre deux sommets
quelconques du graphe il existe un chemin et un seul. On parle dans ce
cas darbre non plante, puisquil ny a pas de sommet particulier qui joue
le role de racine. Les sommets sont voisins les uns des autres, il ny a pas
de hierarchie qui permet de dire quun sommet est le p`ere (ou le ls) dun
autre sommet. On demontre quun graphe de n sommets qui a cette propriete
contient exactement n1 aretes, et que lajout dune nouvelle arete cree un
cycle, tandis que le retrait dune arete le rend non connexe.
5.3 Arbres binaires
En C on utilise en general des pointeurs pour representer les liens entre
un noeud et ses ls dans un arbre binaire. Il existe plusieurs facons de denir
le type ARBRE. Nous proposons la denition suivante, qui permet dimbriquer
dierents types les uns dans les autres (par exemple si on veut des arbres
dont les valeurs sont des listes chainees dont les valeurs sont elles-memes des
arbres,. . . ).
5.3. ARBRES BINAIRES 61
typedef struct noeud * ARBRE;
struct noeud
{
TYPE_VALEUR val;
ARBRE fg, fd;
};
Un arbre en C est donc designe par ladresse de sa racine. Il est facile
dacceder `a un noeud quelconque de larbre `a partir de la racine, en suivant
les liens explicites vers le ls droit ou le ls gauche.
14
7
12
91 67 82
11
1
a>fg>fd
67
1 7
14
11
82
12
91
a
a>fg
La construction dun arbre consiste, `a partir dun arbre vide, `a inserer
des nouveaux noeuds. La fonction suivante fait lallocation dun noeud et
linitialisation des champs de la structure. Il est recommande dutiliser cette
fonction chaque fois quun nouveau noeud doit etre cree.
ARBRE CreerNoeud(TYPE_VALEUR v, ARBRE fg, ARBRE fd)
{
ARBRE p;
p = malloc(sizeof(struct noeud));
assert(p != NULL);
p->val = v;
p->fg = fg;
p->fd = fd;
return p;
}
Arbres binaires : parcours. Le principe est simple : pour parcourir
larbre a, on parcourt recursivement son sous-arbre gauche, puis son sous-
arbre droit. Ainsi le sous-arbre gauche sera explore dans sa totalite avant de
commencer lexploration du sous-arbre droit.
62CHAPITRE 5. ARBRES BINAIRES DE RECHERCHE, ARBRES LEXICOGRAPHIQUES
void Parcours(ARBRE a)
{
if (a != NULL)
{
/* traitement avant */
Parcours (a->fg);
/* traitement entre */
Parcours (a->fd);
/* traitement apres */
}
}
Dans ce schema lexploration descend dabord visiter les noeuds les plus `a
gauche : on parle de parcours en profondeur dabord. On distingue le parcours
prexe, le parcours inxe et le parcours postxe. La dierence entre ces
parcours tient uniquement `a lordre dans lequel sont traites les noeuds du
sous-arbre gauche, le noeud courant, et les noeuds du sous-arbre droit.
Parcours prexe : la valeur du noeud courant est traitee avant les
valeurs gurant dans ses sous-arbres. Si le traitement consiste simplement `a
acher la valeur du noeud, le parcours prexe du larbre ci-dessous produi-
rait lachage 12 1 91 67 7 82 61.
void ParcoursPrefixe(ARBRE a)
{
if (a != NULL)
{
TraiterLaValeur (a->val);
ParcoursPrefixe (a->fg);
ParcoursPrefixe (a->fd);
}
}
7
1
2
3 4
5
6
12
67 91 82
61
1 7
Parcours inxe : la valeur du noeud courant est traitee apr`es les valeurs
gurant dans son sous-arbre gauche et avant les valeurs gurant dans son
sous-arbre droit.
5.4. ARBRES BINAIRES DE RECHERCHE. 63
void ParcoursInfixe(ARBRE a)
{
if (a != NULL)
{
ParcoursInfixe (a->fg);
TraiterLaValeur (a->val);
ParcoursInfixe (a->fd);
}
}
91 1 67 12 7 61 82
4
7
5
6
3
2
1
82
7 1
61
67 91
12
Parcours postxe : la valeur du noeud courant est traitee apr`es les
valeurs de ses sous-arbres.
7
2
91 67 1 61 82 7 12
3
1
4
5
6
82
7 1
61
67 91
12
5.4 Arbres binaires de recherche.
Un arbre binaire de recherche (ou ABR) est une structure de donnee qui
permet de representer un ensemble de valeurs si lon dispose dune relation
dordre sur ces valeurs. Les operations caracteristiques sur les arbres binaires
de recherche sont linsertion, la suppression, et la recherche dune valeur.
Ces operations sont peu co uteuses si larbre nest pas trop desequilibre.
Soit E un ensemble muni dune relation dordre, et a un arbre binaire
portant des valeurs de E. a est un arbre binaire de recherche si pour tout
noeud p de a, la valeur de p est plus grande que les valeurs gurant dans son
sous-arbre gauche et plus petite que les valeurs gurant dans son sous-arbre
droit.
64CHAPITRE 5. ARBRES BINAIRES DE RECHERCHE, ARBRES LEXICOGRAPHIQUES
valeurs comprises
valeurs infrieures 34
entre 22 et 29
p
plus petit plus grand que 66
dans le sous arbre p
52
51
8 16
26
27 67 69 94
88
35
29
23 28
32
30 21
50
66
70
97 55
34
7
68 36
37
80 44
71
56 81
22
17
9
25
Pour acceder `a la cle la plus petite (resp. la plus grande) dans un ABR
il sut de descendre sur le ls gauche (resp. sur le ls droit) autant que
possible. Le dernier noeud visite, qui na pas de ls gauche (resp. droit),
porte la valeur la plus petite (resp. la plus grande) de larbre.
Le parcours inxe de larbre produit la suite ordonnee des cles
7 8 9 16 17 21 22 23 25 26 27 28 29 30 32 34 35 36 37 44 50 51 52 55 56 66 ...
52
51 26
27 67 69 94
88
1
2 4
16
7
5
3
6
8
9
13
15
14
12
10
11
17
35 8 16
36 55 97 80 44
71
56 81
22
17
9
29
25
23 28
32
30 21
50
66
70 37
7
68
34
5.4. ARBRES BINAIRES DE RECHERCHE. 65
Recherche dune valeur. La recherche dune valeur dans un ABR
consiste `a parcourir une branche en partant de la racine, en descendant
chaque fois sur le ls gauche ou sur le ls droit suivant que la cle portee par
le noeud est plus grande ou plus petite que la valeur cherchee. La recherche
sarete d`es que la valeur est rencontree ou que lon a atteint lextremite dune
branche (le ls sur lequel il aurait fallu descendre nexiste pas).
recherche de la valeur 26
<27
<28
>25
<29
>22
<34
52
51
8 16
26
27 67 69 94
88
35
32
21
50
66
70
80 97 55
34
7
68 36
37 56
71
44
81
22
17
9
29
25
23 28 30
ARBRE recherche (TYPE_VALEUR x, ARBRE a)
{
while ((a != NULL) && (x != a->val))
if (x < a->val)
a = a->fg;
else
a = a->fd;
return a;
}
Insertion dune nouvelle valeur. Le principe est le meme que pour
la recherche. Un nouveau noeud est cree avec la nouvelle valeur et insere `a
lendroit o` u la recherche sest aretee.
66CHAPITRE 5. ARBRES BINAIRES DE RECHERCHE, ARBRES LEXICOGRAPHIQUES
8 16
26
27
29
23 28
32
30 21
7
22
17
9
25
8 16
26
27
29
23 28
32
30 21
31
7
22
17
9
25
Recherche du successeur dun noeud.

Etant donne un noeud p dun
arbre A, le successeur de p si il existe, est le noeud de A qui porte comme
valeur la plus petite des valeurs qui gurent dans A et qui sont plus grandes
que la valeur de p. Si p poss`ede un ls droit, son successeur est le noeud le
plus `a gauche dans son sous-arbre droit (on y acc`ede en descendant sur le ls
gauche autant que possible). Si p na pas de ls droit alors sont successeur est
le premier de ses ascendants tel que p apparat dans son sous-arbre gauche.
Si cet ascendant nexiste pas cest que p portait la valeur la plus grande dans
larbre. Remarquez quil est necessaire davoir pour chaque noeud un lien
vers son p`ere pour mener `a bien cette operation.
5.4. ARBRES BINAIRES DE RECHERCHE. 67
52 8 16
26
27 67 69 94
88 51
32 na pas de fils droit
son successeur est 34
premier ascendant de 32
pour lequel 32 est dans
le sousarbre gauche
66 a un fils droit
son successeur est 67
dernier fils gauche de
son sousarbre gauche
35
50
70 37
7
68
31
36
34
55 97 80 44
71
56 81
22
17
9
29
25
23 28
32
30 21
66
Suppression dun noeud. Loperation depend du nombre de ls du
noeud `a supprimer.
suppression de la valeur 51
67 94
88
35 67 69 94
88
35
51
52
36
37
68 68 36
37
55 97 80 44
71
56 81
50
66
70
66
70
55 97 80 44
71
56 81
50
52 69
Cas 1 : le noeud `a supprimer na pas de ls, cest une feuille. Il sut de
decrocher le noeud de larbre, cest-`a-dire de lenlever en modiant le lien
68CHAPITRE 5. ARBRES BINAIRES DE RECHERCHE, ARBRES LEXICOGRAPHIQUES
du p`ere, si il existe, vers ce ls. Si le p`ere nexiste pas larbre devient larbre
vide.
suppression de 55
67 69 94
88
35 67 69 94
88
35 52
52
37
50
66
70
68 68 36
37
97 80 44
71
56 81
50
66
70
36 55 97 80 44
71
56 81
51
51
Cas 2 : le noeud `a supprimer a un ls et un seul. Le noeud est decroche
de larbre en remplacant ce ls par son ls unique dans le noeud p`ere, si
il existe. Si le p`ere nexiste pas larbre est reduit au ls unique du noeud
supprime.
71
94
88
35 52
72
94 35 52
suppression de la valeur 76
88
73
72
50
37 56
44 80 97 55 55 97 80 44
56 81
50
66
70
76
68
70
66
81
36
73
37
36 68
51 51
71
Cas 3 : le noeud ` a supprimer p a deux ls. On va chercher le noeud q qui
porte la plus grande valeur qui gure dans son ls gauche (ou indieremment
le noeud de plus petite valeur qui gure dans son ls droit). Il sut ensuite
5.5. ARBRES G

EN

ERAUX OU N-AIRES 69
de substituer la valeur de q `a la valeur de p et de decrocher le noeud q.
Puisque le noeud q a la valeur la plus grande dans le ls gauche, il na
donc pas de ls droit, et peut etre decroche comme on la fait dans les cas
precedents.
5.5 Arbres generaux ou n-aires
Un arbre n-aire est un arbre dans lequel le nombre de ls dun noeud
nest pas limite. On les represente avec des pointeurs, en liant les ls dun
meme noeud entre eux, comme dans une liste chainee. Ainsi, `a partir dun
noeud quelconque, on acc`ede `a son ls aine (la liste de ses ls) et `a son fr`ere.
racine
frres
fils ain
. . . . .
a a a
2 k 1
On denit en C les arbres n-aires de la facon suivante :
typedef struct noeud * ARBRE;
struct noeud
{
TYPE_VALEUR val;
ARBRE fa, fr;
};
5.6 Exercices
Les arbres lexicographiques, ou arbres en parties communes, ou diction-
naires, sont un exemple darbres n-aires. Ils sont utilises pour representer
70CHAPITRE 5. ARBRES BINAIRES DE RECHERCHE, ARBRES LEXICOGRAPHIQUES
un ensemble de mots, en optimisant lespace memoire occupe. Le principe
consiste `a representer une seule fois les prexes communs `a plusieurs mots.
Pour eliminer toute ambiguite lorsquun mot est le prexe dun autre, on
signale les ns des mots `a laide dun caract`ere particulier (* dans la gure
ci-dessous, mais en C le caract`ere de n de chane 0 est tout `a fait
adapte).
*
X
* * *
L
A D
*
I
R
R U E
*
T
racine
*
Question 1. Ecrivez les fonctions dinsertion et de recherche dun mot
dans un arbre lexicographique.
Question 2. Ecrivez une fonction qui ache tous les mots representes
dans larbre.
Question 3. Ecrivez une fonction qui permet de supprimer un mot de
larbre.
Chapitre 6
Programmation dynamique
6.1 Programmation dynamique et probl`emes dop-
timisation
La programmation dynamique est une methodologie generale pour conce-
voir des algorithmes qui permettent de resoudre ecacement certains probl`emes
doptimisation. Un probl`eme doptimisation admet un grand nombre de so-
lutions. Chaque solution a une certaine valeur, et on veut identier une
solution dont la valeur est optimale (minimale ou maximale). Trouver un
plus court chemin pour aller dun point `a un autre dans un reseau de trans-
port est un probl`eme doptimisation
La conception dun algorithme de programmation dynamique se decompose
en quatre etapes.
1. Caracterisation de la structure dune solution optimale.
2. Denition recursive de la valeur de la solution optimale.
3. Calcul ascendant de la valeur de la solution optimale.
4. Construction de la solution optimale `a partir des informations obtenues
`a letape precedente.
Letape 4 peut etre omise si on a seulement besoin de la valeur de la solution
optimale et non de la solution elle meme.
Les sections suivantes decrivent lutilisation de la programmation dyna-
mique pour resoudre en temps polynomial trois probl`emes doptimisation :
le calcul dun parcours optimal dans un atelier de montage, le calcul dune
chane de mulplications matricielles avec un nombre minimum doperations
71
72 CHAPITRE 6. PROGRAMMATION DYNAMIQUE
scalaires, le calcul dun arbre binaire de recherche optimal. Ensuite, nous
mettrons en evidence deux caracteristiques que doit posseder un probl`eme
doptimisation pour que la programmation dynamique soit applicable.
6.2 Ordonnancement optimal dune chane de mon-
tage
Un constructeur automobile poss`ede un atelier avec deux chanes de
montage comportant chacune n postes de montages. Chaque vehicule doit
passer par les n postes dans lordre. Le constructeur cherche `a determiner
quels sont les postes ` a selectionner sur la chane 1 et sur la chane 2 pour
minimiser le delai de transit dune voiture `a travers latelier. Les donnees du
probl`eme doptimisation quil doit resoudre sont les suivantes. Pour i = 1, 2
et j = 1, . . . , n, on note S
i,j
le j`eme poste de la chane i, e
i
le temps dentree
dun vehicule sur la chane i, a
i,j
le temps de montage pour le poste j sur
la chane i, t
i,j
le temps de transfert dun vehicule de la chane i vers lautre
chane apr`es le poste S
i,j
et nallement x
i
le temps de sortie dun vehicule
de la chane i (voir Figure 6.1a).
Chaque solution de ce probl`eme doptimisation est denie par le sous-
ensemble de postes de la chane 1 utilises (les postes restant sont choisis
dans la chane 2). Il y a donc 2
n
solutions possibles, i.e. le nombre de sous-
ensembles dun ensemble `a n elements. Par consequent, lapproche nave
consistant `a considerer tous les chemins possibles est inecace. La program-
mation dynamique permet de resoudre ce probl`eme ecacement.
La premi`ere etape consiste `a identier des sous-probl`emes dont les solu-
tions optimales vont nous permettre de reconstituer une solution optimale
du probl`eme initial. Les sous-probl`emes `a considerer ici consistent `a calculer
un itineraire optimal jusquau poste S
i,j
pour i = 1, 2 et j = 1, . . . , n. Par
exemple, considerons un itineraire optimal jusquau poste S
1,j
. Si j = 1, il
ny a quun seul chemin possible. Pour j = 2, . . . , n, il y a deux possibilites.
Un itineraire optimal jusqu`a S
1,j
est ou bien, un itineraire optimal jusqu`a
S
1,j1
suivi du poste S
1,j
, ou bien, un itineraire optimal jusqu`a S
2,j1
suivi
dun changement de chane et du poste S
1,j
.
La deuxi`eme etape consiste `a denir la valeur optimale de mani`ere recursive
`a partir des valeurs des solutions optimales des sous-probl`emes. Soit f
i
[j] le
delai optimal jusqu`a S
i,j
et f

le delai optimal total. Pour traverser late-

lier, il faut atteindre ou bien S
1,n
ou bien S
2,n
et sortir de latelier. Par
6.2. ORDONNANCEMENT OPTIMAL DUNE CHA

INE DE MONTAGE73
(a)
j
(b)
9 17 19 32
29 29 22 15 13
1 2 1 1
2 2 1 l
2
[j]
l
1
[j] f
1
[j]
f
2
[j]
j 1 2 3 4 5 2 3 4 5
Entree
S
2,2
S
2,3
S
2,4 S
2,5
Sortie
S
1,5
S
1,4
S
1,3
S
1,1
S
1,2
23
1
f

= 32 l

= 2
3
6 8 2 4 9
8
4 7 7 3
S
2,1
5
2 1 5 3
2
3
3 2 1 2
Figure 6.1 Exemple dinstance du probl`eme dordonnacement optimal
dune chane de montage : (a) les donnees du probl`eme et (b) les tables de
programmation dynamique.
consequent, on a
f

= min(f
1
[n] + x
1
, f
2
[n] + x
2
).
Pour le poste 1 de chaque chane, il ny a quun itineraire possible :
f
1
[1] = e
1
+ a
1,1
f
2
[1] = e
2
+ a
2,1
Pour le poste j = 2, . . . , n de la chane 1, il y a deux possibilites :
f
1
[j] = min(f
1
[j 1] + a
1,j
, f
2
[j 1] + t
2,j1
+ a
1,j
), (6.1)
et symetriquement
f
2
[j] = min(f
2
[j 1] + a
2,j
, f
1
[j 1] + t
1,j1
+ a
2,j
). (6.2)
Les f
i
[j] sont les valeurs des solutions optimales des sous-probl`emes. Pour
pouvoir reconstruire les solutions optimales elles-memes, on denit l
i
[j] le
numero de la chane (1 ou 2) dont le poste j 1 est utilise par un chemin
74 CHAPITRE 6. PROGRAMMATION DYNAMIQUE
optimal jusquau poste S
i,j
pour j = 2, . . . , n, (l
i
[1] nest pas deni car aucun
poste ne vient avant le poste 1).
La troisi`eme etape consiste `a concevoir un algorithme qui calcule en
temps polynomial les valeurs f
i
[j] des solutions optimales et les informations
l
i
[j] necessaires `a la construction de ces solutions. Lalgorithme suivant fait
ce travail en O(n) en utilisant les formules recursives (6.1) et (6.2). Il revient
`a remplir les tables de la Figure 6.1b de la gauche vers la droite.
Plus-Rapide-Chemin(a, t, e, x, n)
1. f
1
[1] e
1
+ a
1,1
2. f
2
[1] e
2
+ a
2,1
3. pour j 2 `a n faire
4. si f
1
[j 1] f
2
[j 1] + t
2,j1
5. alors f
1
[j] f
1
[j 1] + a
1,j
6. l
1
[j] 1
7. sinon f
1
[j] f
2
[j 1] + t
2,j1
+ a
1,j
8. l
1
[j] 2
9. si f
2
[j 1] f
1
[j 1] + t
1,j1
10. alors f
2
[j] f
2
[j 1] + a
2,j
11. l
2
[j] 2
12. sinon f
2
[j] f
1
[j 1] + t
1,j1
+ a
2,j
13. l
2
[j] 1
14. si f
1
[n] + x
1
f
2
[n] + x
2
15. alors f

= f
1
[n] + x
1
16. l

= 1
17. sinon f

= f
2
[n] + x
2
18. l

= 2
Finalement, la quatri`eme et derni`ere etape consiste `a reconstruire une
solution optimale en utilisant les informations sauvegardees `a letape 3. La
procedure suivante ache les postes utilises par une solution optimale par
ordre decroissant de numero de poste.
Afficher-Postes(l, n)
1. i l

2. acher chane i, poste n

3. pour j n jusqu`a 2
4. faire i l
i
[j]
5. acher chane i, poste j 1
6.3. CHA

INE DE MULTIPLICATIONS MATRICIELLES 75

6.3 Chane de multiplications matricielles
On se donne une suite de n matrices A
1
, . . . , A
n
et on veut calculer le
produit
A
1
A
2
. . . A
n
(6.3)
Une fois que lon a parenthese cette expression de mani`ere `a supprimer lam-
bigute liee `a lordre dans lequel les multiplications doivent etre eectuees,
on peut evaluer lexpression (6.3) en utilisant comme routine lalgorithme
standard de multiplication de deux matrices.
On dit dun produit de matrices quil est compl`etement paranthese dans
les deux cas suivants :
cest une matrice isolee,
cest le produit de deux matrices compl`etement paranthesees.
Le produit de matrices est associatif par consequent quelquesoit le pa-
renthesage on obtient le meme resultat. Par exemple, si la chane de matrices
est A
1
, A
2
, A
3
, A
4
, le produit A
1
A
2
A
3
A
4
peut etre parenthese de 5 fa cons
dierentes :
(A
1
(A
2
(A
3
A
4
))),
(A
1
((A
2
A
3
)A
4
)),
((A
1
A
2
)(A
3
A
4
)),
((A
1
(A
2
A
3
))A
4
),
(((A
1
A
2
)A
3
)A
4
).
La facon dont on paranth`ese une telle chane de matrices peut avoir une
grande importance sur le nombre doperations necessaires pour eectuer le
produit.
Si A est une matrice p q et B une matrice q r, la matrice produit
est une matrice q r. La complexite du calcul du produit est domine par le
nombre de multiplications scalaires qui est egal `a pqr.
Pour illustrer les dierences de co uts obtenus en adoptant des parenthesages
dierents, considerons un produit de 3 matrices A
1
, A
2
, A
3
de dimensions
respectives 10 100, 100 5 et 5 50. Si on eectue les multiplications
dans lordre donne par le parenthesage ((A
1
A
2
)A
3
), le nombre doperations
necessaires est 101005 = 5000 pour obtenir le produit A
1
A
2
, qui est une
matrice 10 5, plus 10 5 50 = 2500 pour obtenir le produit ((A
1
A
2
)A
3
),
soit 7500 operations en tout. Si on adopte le parenthesage (A
1
(A
2
A
3
)), le
nombre doperations necessaires est 100550 = 25000 pour obtenir le pro-
76 CHAPITRE 6. PROGRAMMATION DYNAMIQUE
duit A
2
A
3
, qui est une matrice 10050, plus 1010050 = 50000 pour ob-
tenir le produit (A
1
(A
2
A
3
)), soit 75000 operations en tout. Par consequent,
calculer le produit en accord avec le premier parenthesage est 10 fois plus
rapide.
Notre probl`eme se formule de la fa con suivante : etant donne une suite
de n matrices A
1
, . . . , A
n
, avec p
i1
p
i
la dimension de la matrice A
i
, pour
i = 1, . . . , n, trouver le paranth`esage du produit A
1
A
2
. . . A
n
qui minimise
le nombre de multiplications scalaires `a eectuer.
Remarque : le nombre de parenthesages dierents est une fonction
exponentielle de n. Par consequent, la strategie qui consiste `a enumerer tous
les parenthesages est exclue pour de grandes valeurs de n.
6.3.1 Structure dun parenthesage optimal
La premi`ere etape dans une approche de type programmation dynamique
consiste `a identier la structure des solutions optimales.
Notons A
i..j
la matrice qui resulte de levaluation du produit A
i
A
i+1
. . . A
j
.
Un parenthesage optimal de A
1
. . . A
n
decoupe le produit entre les matrices
A
k
et A
k+1
pour un certain k compris entre 1 et n 1. Cest `a dire que
pour un certain k, on calcule dabord le produit A
1..k
et A
k+1..n
, ensuite on
multiplie ces produits pour obtenir le produit nal A
1..n
. Le co ut de ce pa-
renthesage est la somme des co uts du calcul de A
1..k
et A
k+1..n
et du produit
de ces deux matrices.
Remarquons que le parenthesage de A
1..k
doit etre lui-meme un pa-
renthesage optimal de A
1
. . . A
k
, de meme le parenthesage de A
k+1..n
doit
etre optimal. Par consequent, une solution optimal dun probl`eme de pa-
renthesage contient elle-meme des solutions optimales de sous-probl`emes de
parenthesage. La presence de sous-structures optimales dans une solution
optimale est lune des caracteristiques des probl`emes pour lesquels la pro-
grammation dynamique est applicable.
6.3.2 Une solution recursive
La seconde etape dans une approche de type programmation dynamique
consiste `a denir la valeur de la solution en fonction des solutions optimales
de sous-probl`emes. Dans notre cas, un sous-probl`eme consiste `a determiner le
6.3. CHA

INE DE MULTIPLICATIONS MATRICIELLES 77

co ut minimal dun parenthesage de A
i
. . . A
j
pour 1 i j n. Soit m[i, j]
le nombre minimum de multiplications scalaires necessaires pour obtenir le
produit A
i..j
. Le nombre minimum de multiplications scalaires necessaires
pour obtenir A
1..n
sera m[1, n].
On peut calculer m[i, j] recursivement de la facon suivante. Si i = j, la
chane de matrices se reduit `a une seule matrice A
i..i
= A
i
, aucune operation
nest necessaire, et donc m[i, i] = 0 pour i = 1, . . . , n. Pour calculer m[i, j]
quand i < j, on se sert de la structure des solutions optimales que nous avons
precedemment mise en evidence. Supposons que la solution optimale du
sous-probl`eme decoupe le produit A
i
. . . A
j
entre A
k
et A
k+1
avec i k < j.
Alors, m[i, j] est egal au nombre minimum de multiplications scalaires pour
obtenir A
i..k
et A
k+1..j
plus le nombre de multiplications necessaires pour ef-
fectuer le produit matriciel A
i..k
A
k+1..j
, cest `a dire p
i1
p
k
p
j
multiplications
scalaires, on obtient
m[i, j] = m[i, k] + m[k, j] + p
i1
p
k
p
j
.
Cette equation recursive suppose que nous connaissions la valeur de k,
ce qui nest pas le cas. Il y a seulement j i valeurs possibles pour k :
les valeurs i, i + 1, . . . , j 1. Puisque la solution optimale correspond `a
lune de ces valeurs, il sut de les essayer toutes et de garder la meilleure.
Par consequent, notre denition recursive pour le co ut minimum dun pa-
ranth`esage de A
i
. . . A
j
devient
m[i, j] =

0 si i = j,
min
ik<j
m[i, k] + m[k + 1, j] + p
i1
p
k
p
j
si i < j.
(6.4)
Les valeurs m[i, j] donnent les co uts des solutions optimales des sous-probl`emes.
Pour reconstituer une solution optimale a posteriori, nous allons stocker dans
s[i, j] une valeur de k qui minimise m[i, k] +m[k, j] +p
i1
p
k
p
j
, i.e. telle que
m[i, j] = m[i, k] + m[k, j] + p
i1
p
k
p
j
.
6.3.3 Calcul du co ut optimal
Au point o` u nous en sommes, on peut ecrire facilement un programme
recursif base sur la relation de recurrence (6.4) pour calculer le co ut de la
solution optimale. Cependant, cet algorithme na pas une meilleure com-
plexite quun algorithme enumeratif brutal.
78 CHAPITRE 6. PROGRAMMATION DYNAMIQUE
En fait, on peut remarquer quil existe relativement peu de sous-probl`emes :
un pour chaque choix de i et j qui satisfasse 1 i j n, cest `a dire `a peu
pr`es n
2
(en fait, n(n + 1)/2 + n exactement). Un algorithme recursif peut
rencontrer plusieurs fois chacun de ces sous-probl`emes dans larbre des ap-
pels recursifs. Cette propriete est la deuxi`eme caracteristique des probl`emes
pour lesquels la programmation dynamique est applicable.
Au lieu de calculer la solution de la recurrence (6.4) recursivement, nous
allons eectuer la troisi`eme etape la troisi`eme etape dune approche de type
programmation dynamique en calculant le co ut optimal de facon ascendante.
Lalgorithme suivant remplit la table en commen cant par resoudre le
probl`eme de parenthesage sur les chanes de matrices les plus courtes et
en continuant par ordre croissant de longueur de chanes. Lequation de
recurrence (6.4) montre que lon peut calculer le co ut optimal pour une
chane en connaissant les co uts optimaux pour les chanes de longueurs
inferieures.
Ordre-Chane-Matrices(p)
1. n longueur(p)
2. pour i 1 `a n
3. faire m[i, i] 0
4. pour l 2 `a n
5. faire pour i 1 `a n l + 1
6. j i + l 1
7. m[i, j]
8. pour k i `a j 1
9. faire q m[i, k] + m[k + 1, j] + p
i1
p
k
p
j
10. si q < m[i, j]
11. alors m[i, j] q
12. s[i, j] k
13. retourner m et s
Cet algorithme est en O(n
3
). En eet, il contient trois boucles imbriquees
dans lesquelles chaque index peut prendre au plus n valeurs. De plus, le
traitement est eectue `a linterieur de ces boucles se fait en temps constant.
Par consequent, cet algorithme est beaucoup plus ecace que la methode
exponentielle qui consiste `a examiner chaque parenthesage.
6.4. ARBRE BINAIRE DE RECHERCHE OPTIMAL 79
6.3.4 Construction dune solution optimale
Lalgorithme que nous avons decrit precedemment donne le nombre mi-
nimum de multiplications scalaires necessaires pour calculer la chane de
produits matriciels mais ne montre pas directement comment multiplier ces
matrices en utilisant ce nombre minimum de multiplications. La derni`ere
etape dans notre approche de type programmation dynamique consiste `a
reconstruire une solution optimale `a partir des informations que nous avons
sauvegardees `a letape precedente.
Nous allons utiliser une table s[ , ] pour determiner la meilleure facon
de multiplier les matrices. Chaque entree s[i, j] de cette table contient la
valeur k telle quun parenthesage optimal separe le produit A
i
A
i+1
. . . A
j
entre A
k
et A
k+1
. Par consequent, nous savons que la derni`ere multipli-
cation matricielle dans la solution optimale que nous voulons reconstruire
est A
1..s[1,n]
A
s[1,n]+1..n
. Les multiplications precedentes peuvent etre recons-
tituees recursivement de la meme fa con. La procedure suivante ache le pa-
renthesage optimal du produit matriciel A
i..j
etant donnee la table s[ , ] cal-
culee `a letape precedente et les indices i et j. Pour calculer le parenthesage
complet, le premier appel de cette procedure sera Affichage-Parenth esage-
Optimal(s, 1, n).
Affichage-Parenth esage-Optimal(s, i, j)
1. si i = j
2. alors Acher A
i

3. sinon Acher (
4. Affichage-Parenth esage-Optimal(s, i, s[i, j])
5. Affichage-Parenth esage-Optimal(s, s[i, j] + 1, j)
6. Acher )
6.4 Arbre binaire de recherche optimal
Le probl`eme doptimisation que nous allons considerer dans cette section
consiste etant donne un ensemble de clefs a
1
, a
2
, . . . , a
n
et p
1
, p
2
, . . . , p
n
les
frequences de recherche de ces clefs, `a calculer un arbre binaire de recherche
qui permettent de minimiser le temps de recherche de ces clefs. En remar-
quant que le temps necessaire pour rechercher une clef est proportionnel `a
sa profondeur dans larbre binaire de recherche, on deduit que larbre bi-
naire de recherche que nous souhaitons identier doit minimiser la quantite
80 CHAPITRE 6. PROGRAMMATION DYNAMIQUE
suivante
co ut(T) =
n

i=1
p
i
(prof
T
(a
i
) + 1)
o` u prof
T
(a
i
) est la profondeur de la clef a
i
dans larbre T.
clefs a
1
a
2
a
3
a
4
a
5
frequences 20 40 12 16 12
a
2
a
1
co ut(T
1
) = 60 + 36 + 80 + 32 + 12 = 220
T
1
12
40 2 = 80
20 3 = 60
12 3 = 36
16 2 = 32
20 2 = 40
T
2
40
16 2 = 32
co ut(T
2
) = 36 + 36 + 40 + 32 + 40 = 184
a
3
a
4
a
5
a
1
a
2
a
4
a
5
a
3
12 3 = 36 12 3 = 36
Figure 6.2 Un exemple dinstance du probl`eme de larbre binaire de
recherche optimal avec deux arbres et leurs co uts respectifs.
Pour commencer, nous allons mettre en evidence la presence de sous-
structures optimales dans un arbre binaire de recherche (ABR) optimal.
Pour cela, nous allons introduire les notations suivantes :
T
i,j
un ABR optimal pour les clefs a
i+1
, . . . , a
j
;
w
i,j
= p
i+1
+. . . +p
j
la somme des frequences des clefs de larbre T
i,j
;
r
i,j
la racine de larbre T
i,j
;
c
i,j
le co ut de larbre T
i,j
;
T
i,i
larbre vide (c
i,i
= 0).
Considerons un ABR optimal T
i,j
et notons k lentier compris entre i +1
et j tel que la racine r
i,j
de larbre T
i,j
soit a
k
. Le sous-arbre gauche de
la racine a
k
est constitue des clefs a
i+1
, . . . , a
k1
. De plus, ce sous-arbre T
doit necessairement etre un ABR optimal sur cet ensemble de clefs car sil
existait un meilleur ABR T

sur cet ensemble de clefs alors en remplacant T

par T

dans T
i,j
on obtiendrait un arbre meilleur que T
i,j
, ce qui contredirait
loptimalite de T
i,j
. Le meme raisonnement sapplique au sous-arbre droit
et montre que larbre optimal T
i,j
est constitue dune racine a
k
dont le ls
gauche est la racine dun ABR optimal T
i,k1
et le ls droit est la racine
dun ABR optimal T
k,j
(voir Figure 6.4).
6.4. ARBRE BINAIRE DE RECHERCHE OPTIMAL 81
T
i,k1 T
k,j
a
k
Figure 6.3 Sous-structures optimales dans un ABR optimal
Voyons maintenant comment donner une denition recursive du co ut
dun ABR optimal. Si a
k
est la racine de T
ij
, on a :
c
i,j
= (c
i,k1
+ w
i,k1
) + p
k
+ (c
k,j
+ w
k,j
)
= (w
i,k1
+ p
k
+ w
k,j
) + c
i,k1
+ c
k,j
= w
i,j
+ c
i,k1
+ c
k,j
La premi`ere ligne sexplique par le fait que lorsque lon place larbre
T
i,k1
sous la racine a
k
, la profondeur de chacun de ces noeuds augmente
de un, donc globalement le co ut c
i,k1
de ce sous-arbre augmente de la
somme des frequences des clefs quil contient, cest `a dire w
i,k1
. Idem pour
la contribution du sous-arbre droit T
k,j
qui augmente de w
k,j
. Finalement,
il reste `a compter la contribution de a
k
qui est egale `a p
k
. La deuxi`eme ligne
est juste une reecriture de la premi`ere et la troisi`eme utilise simplement la
denition de w
i,j
.
Pour nir, on remarque que la valeur de k `a utiliser est celle qui minimise
le co ut c
i,k1
+ c
k,j
, ce qui donne la denition recursive suivante :
c
i,j
= w
i,j
+ min
k{i+1,...,j}
(c
i,k1
+ c
k,j
)
Lalgorithme suivant consiste `a resoudre les sous-probl`emes sur des sous-
ensembles de clefs de longueurs l croissantes, en utilisant la formule recursive
ci-dessus :
ABR-Optimal(p, n)
1. Pour i 0 `a n faire
2. w
i,i
0
3. c
i,i
0
4. Pour l 1 `a n faire
82 CHAPITRE 6. PROGRAMMATION DYNAMIQUE
5. Pour i 0 `a n l faire
6. j i + l
7. w
i,j
w
i,j1
+ p
j
8. Soit m la valeur de k telle que c
i,k1
+ c
k,j
soit minimum
9. c
i,j
= w
i,j
+ c
i,m1
+ c
m,j
10. r
i,j
m
Lalgorithme precedent permet dobtenir le co ut dun ABR optimal et
sauvegarde les informations necessaires pour le contruire grace `a lalgorithme
suivant.
Const-ABR-opt(i, j)
1. p CreerNoeud(r
i,j
, NULL, NULL)
2. Si i < r
i,j
1 alors
3. pls-gauche = Const-ABR-opt(i, r
i,j
1)
4. Si r
i,j
< j alors
5. pls-droit = Const-ABR-opt(r
i,j
, j)
6.5 Applicabilite de la programmation dynamique
Dans cette section, nous presentons deux caracteristiques que doit avoir
un probl`eme doptimisation pour que la programmation dynamique soit ap-
plicable : la presence de sous-structures optimales et le recouvrement des
sous-probl`emes.
6.5.1 Sous-structures optimales
La premi`ere etape dans une approche de type programmation dyna-
mique consiste `a identier la structure des solutions optimales. On dit que
le probl`eme presente une sous-structure optimale si une solution optimale
contient des solutions optimales de sous-probl`emes.
Cetait le cas dans les trois probl`emes precedents. Par exemple, chaque
parenthesage optimal de A
1
. . . A
n
etait obtenu comme le produit du pa-
renthesage optimal de A
1
. . . A
k
et de A
k+1
. . . A
n
pour un certain k et que
chaque ABR optimal peut etre obtenu en attachant `a une racine bien choisie
deux ABR optimaux pour des sous-probl`emes.
6.5. APPLICABILIT

E DE LA PROGRAMMATION DYNAMIQUE 83
6.5.2 Recouvrement des sous-probl`emes
Pour que la programmation dynamique soit applicable, il faut egalement
que lespace des sous-probl`emes soit susament petit. Dans le sens o` u
un algorithme recursif qui resoudrait le probl`eme rencontrerait les memes
sous-probl`emes plusieurs fois, au lieu de generer toujours de nouveaux sous-
probl`emes. Pour que la programmation dynamique permette de concevoir
un algorithme polynomial, il faut bien s ur que le nombre de sous-probl`emes
`a considerer soit polynomial.
84 CHAPITRE 6. PROGRAMMATION DYNAMIQUE
Chapitre 7
Graphes
85
86 CHAPITRE 7. GRAPHES
Chapitre 8
Annexes mathematiques
8.1 Les notations de Landau pour la comparaison
asymptotique des fonctions
On sinteresse le plus souvent `a la mani`ere dont la complexite T(n) dun
algorithme crot en fonction de n, plutot quaux valeurs de T pour des
valeurs particuli`eres de n. Autrement dit, on sinteresse au comportement
asymptotique de la fonction T au voisinage de linni et lon souhaite le
comparer aux comportements de fonctions de references : n, nlog n, n
2
, e
n
,
etc. Les notations de Landau permettent dexprimer ces comparaisons de
mani`ere simple.
Soit f, g : N R o` u g joue le role de la fonction de reference et f celui
de la fonction quon souhaite lui comparer.
On ecrit
f(n) = O(g(n)) si C, n
0
n n
0
f(n) Cg(n).
La fonction g majore f, `a partir dune certaine valeur, et `a une constante
multiplicative pr`es.
On ecrit
f(n) = (g(n)) si C, n
0
n n
0
f(n) Cg(n).
La fonction g minore f, `a partir dune certaine valeur, et `a une constante
multiplicative pr`es.
On ecrit
f(n) = (g(n)) si C
1
, C
2
, n
0
n n
0
C
1
g(n) f(n) C
2
g(n).
1
2 CHAPITRE 8. ANNEXES MATH

EMATIQUES
n
n
T(n) = O(f(n))
x
0
c f(n)
Figure 8.1 La notation O(f(n)).
n
0
T(n)
2
x
1
x c f(n)
c f(n)
n
Figure 8.2 La notation (f(n)).
8.2. COMPORTEMENT ASYMPTOTIQUE DES FONCTIONS D

EFINIES PAR R

ECURRENCE3
La fonction g decrit la croissance de f, `a partir dune certaine valeur, et
`a une constante multiplicative pr`es. On peut remarquer que
f(n) = (g(n)) ssi f(n) = O(g(n)) et f(n) = (g(n)).
Enn, on ecrit
f(n) = o(g(n)) si > 0 n

n n

f(n) g(n).
Si g ne prend que des valeurs non nulles, cela signie que lim
n
f(n)
g(n)
=
0.
Exemple 4
1. 3n
2
+ 5n 1 = O(n
2
) ; en eet, 3n
2
+ 5n 1 = 3n
2
(1 +
5
3n

1
3n
2
) et
5
3n

1
3n
2
1 d`es que n 2 ; on peut donc prendre C = 6 et N = 2.
2. n + sinn = (n) ;
3. n(2 log n + log log n 1) = (nlog n) ;
4. nlog n = o(n
2
).
8.2 Comportement asymptotique des fonctions denies
par recurrence
La complexite des algorithmes recursifs est naturellement decrite par
des equations de recurrence. Par exemple, lalgorithme de recherche dicho-
tomique conduit `a lequation
T(n) = T(
n
2
|) + c,
lalgorithme de tri par fusion conduit `a lequation
T(n) = 2 T(
n
2
|) + n
Theor`eme 1 Soit T : N R deni par la formule
T(n) = aT(i(n/b)) + f(n)
o` u a 1, b > 1 et f : N R et o` u i(n/b) est egal `a n/b| o` u `a n/b|.
1. Sil existe > 0 pour lequel f(n) = O(n
log
b
a
), alors T(n) = (n
log
b
a
).
2. Si f(n) = O(n
log
b
a
), alors T(n) = (n
log
b
a
log
2
n).
3. Sil existe > 0 pour lequel f(n) = (n
log
b
a+
) et sil existe c < 1 tel
que af(n) cf(n) d`es que n est susamment grand, alors T(n) =
(f(n)).
Ce theor`eme est prouve dans le livre de reference.