Notes de cours d’algorithmique

Notes de cours d’algorithmique, tutoriel & guide de travaux pratiques en pdf.

Arbres binaires de recherche

Les ABR sont un type de donnees pour representer un dictionnaire c’est `a dire un ensemble de cles (ou un ensemble d’elements accessibles via des cl´es) totalement ordonnees, muni des operations “ajouter” (une cle), “rechercher”, “supprimer”.
Dans la suite on supposera que les cles sont des valeurs dans N mais ces cles peuvent etre prises dans n’importe quel ensemble totalement ordonne.

Definitions

Definition 4 Un arbre binaire (AB) est soit l’arbre vide, soit constitu´e d’une racine avec un couple ( i.e. une paire ordonnee) d’arbres binaires appel´es sous-arbre gauche et sous-arbre droit.
Afin de d´ecrire les algorithmes et d’´evaluer leur complexit´e, on distingue les noeuds ex-ternes correspondant aux arbres vides, et les noeuds internes correspondant aux noeuds ayant des sous-arbres.
Exemple 1 La figure 1 contient un exemple d’arbre binaire : les , correspondent aux noeuds internes et les aux noeuds externes.
Un arbre binaire etiquet´ est un AB o`u l’on associe a` chaque noeud interne un el´ement (appel´ une cl´e).
Les op´erations de base sur les AB sont :
– est−vide(arbre a) : bool´een : teste si a est vide ou non ;
– G(arbre a) : arbre : renvoie le sous-arbre gauche de a (si a est non vide) ;
– D(arbre a) : arbre : renvoie le sous-arbre droit de a (si a est non vide) ;
– val(arbre a) : cl´e : donne la cl´e associ´ee a` la racine de a.
Les constructeurs sont :
– ArbreVide() : arbre – cr´ee un arbre vide
– Arbre(cl´e x; arbre a1, a2) : arbre – cr´ee une racine contenant x et avec a1 et a2 comme sous arbre (g et d).
On peut aussi utiliser les fonctions suivantes pour modifier les champs d’un noeud interne :
– FixerVal(cl´e x; arbre a) : arbre – place x a` la racine de a (ok si a est l’arbre vide).
– FixerAG(arbre a, g) : arbre – remplace le sous-arbre gauche de a par g.
– FixerAD(arbre a, d) : arbre – remplace le sous-arbre droit de a par d.
. . . mais on pr´ef´erera ´ecrire directement : val(a) := x, G(a) := g et D(a) := d.
D´efinition 5 Un Arbre Binaire de Recherche A est un AB etiquet´ tel que tout noeud interne
s de A contient une cl´e x :
– sup´erieure (NB : ou ´egale si les cl´es ne sont pas toutes distinctes) a` toutes les cl´es contenues dans le sous-arbre gauche de s ;
– inf´erieure strictement a` toutes les cl´es contenues dans le sous-arbre droit de s.

Op´erations de base

Rechercher un el´ement.

L’algorithme de recherche d’un el´ement dans un ABR est donn´e ci-dessous (algorithme 1).
Fonction Rechercher(cl´e x, ABR a) : bool´een begin
si est−vide(a) alors
return Faux
sinon
si val(a) == x alors
return Vrai
sinon
si val(a) ≥ x alors
return Rechercher(x,G(a))
sinon
return Rechercher(x,D(a))
end

Ajouter un el´ement

On l’ajoute sur une feuille (i.e. un arbre vide). . . On remplace un arbre vide par un arbre contenant l’´el´ement a` ajouter et deux sous-arbres vides. Cette proc´edure est d´ecrite par l’al-gorithme 2.
Exemple 2 On applique, a` partir d’un arbre vide, la proc´edure Ajouter aux cl´es suivantes :
20, 15, 10, 35, 19, 13, 5, 3, 12, 7, 16, 40, 25, 38
Proc´edure Ajouter(cl´e x, ABR a)
begin
si est−vide(a) alors
a = Arbre(x, ArbreVide(), ArbreVide()) // remplace a par . . .
sinon
si x ≤ val(a) alors
Ajouter(x,G(a)) sinon
Ajouter(x,D(a))
end
Cela donne l’ABR de la figure 2.
NB : on aurait obtenu le mˆeme ABR avec, par exemple, la s´equence suivante : 20, 15, 10, 35, 40, 19, 13, 5, 3, 12, 7, 16, 25, 38
Cette remarque (deux s´equences diﬀ´erentes d’ajouts peuvent conduire au mˆeme ABR) sera importante lors de l’analyse de complexit´ en moyenne.
NB : si on suppose qu’une cl´e ne peut apparaˆıtre qu’au plus une fois dans un ABR, il faut ajouter l’hypoth`ese ”x n’est pas dans a” pour que l’algorithme soit correct.
Correction de l’algorithme. Lorsque l’on autorise plusieurs occurrences d’une mˆeme cl´e dans un ABR a, alors les cl´es contenues dans a ne constituent plus un ensemble mais un ensemble avec r´ep´etition appel´ un multi-ensemble. Un multi-ensemble E de cl´es est d´efini par une fonction mE de l’univers des cl´es (l’ensemble de toutes les cl´es possibles) dans
N : mE (x) repr´esente le nombre d’occurrences de x dans E. On dit que “E contient x” ou “x appartient `a E” (not´e x ∈ E) lorsque mE (x) ≥ 1, on note E + x l’ajout de x `a E (c’est `a dire le multi-ensemble E′ d´efini par mE′ telle que mE′ (x) = mE (x) + 1 et mE′ (y) = mE (y) pour tout y = x) et E − x la suppression de x de E (avec mE′ (x) = max(0, mE (x) − 1),. . . )
Etant donn´e un ABR a, on note S(a) le multi-ensemble des cl´es contenues dans a. On peut alors ´enoncer la correction des proc´edures Ajouter et Rechercher :

Proposition 1 (Correction)

Etant donn´e un ABR a contenant le multi-ensemble de cl´es S, et une cl´e x,
– l’ex´ecution de Ajouter(x, a) transforme a en un ABR contenant le multi-ensemble de cl´es S + x ;
– l’ex´ecution de Rechercher(x, a) retourne Vrai ssi x appartient a` S, et Faux sinon.
Preuve :
1. La preuve se fait par induction sur la taille de a. Si |a| = 0, l’arbre a est l’arbre vide : la proc´edure Ajouter transforme a en une feuille avec deux arbres vides. Si |a| = n + 1, alors selon la valeur associ´ee a` la racine de a, on appelle r´ecursivement la proc´edure Ajouter sur le sous-arbre gauche a1 (contenant les cl´es S1) ou le sous-arbre droit a2 (contenant les cl´es S2). Dans les deux cas, on applique l’hypoth`ese de r´ecurrence et on obtient que le nouveau sous-arbre est un ABR et contient l’ensemble Si + x, de plus l’arbre global v´erifie toujours la propri´et´ des ABR car x a et´ ajout´e du bon cot´e. . .
2. Mˆeme d´emarche que ci-dessus : Si |a| = 0, la r´eponse est Faux et c’est correct. Si |a| = n + 1, alors si la racine de a contient x, la r´eponse de l’algorithme est bonne, sinon la structure d’ABR impose que x ne peut ˆetre que dans le sous-arbre gauche ou le sous-arbre droit selon le r´esultat du test “x ≤ val(a)”, or l’hypoth`ese de r´ecurrence nous assure que l’appel r´ecursif sur le “bon” sous-arbre nous donne la bonne r´eponse.

Supprimer un el´ement.

Il s’agit a` pr´esent de supprimer une certaine cl´e x d’un ABR a. Pour cela, on va :
1. trouver sa place (ie son noeud interne) ;
2. le remplacer par le plus grand el´ement de son sous-arbre gauche ou par le plus petit el´ement de son sous-arbre droit. (Si le noeud a` supprimer a un sous-arbre vide, la transformation est encore plus simple).
Cette proc´edure est d´ecrite par les algorithmes 3 et 4.
On ´enonce la correction de la mani`ere suivante :

Proposition 2 (Correction)

Etant donn´e un ABR a contenant le multi-ensemble de cl´es S, et une cl´e x, l’ex´ecution de Supprimer(x, a) transforme a en un ABR contenant le multi-ensemble de cl´es S − x
Preuve : a` faire en exercice !

Algorithmes it´eratifs

La structure d’arbre binaire se prˆete particuli`erement bien aux algorithmes r´ecursifs. On peut n´eanmojns utiliser des algorithmes it´eratifs tr`es simples pour les op´erations de base.
Proc´edure Supprimer(cl´e x, ABR a)
begin
si ¬est−vide(a) alors
si x < val(a) alors
Supprimer(x,G(a))
sinon
si x > val(a) alors
Supprimer(x,D(a))
sinon
si est−vide(G(a)) alors
a := D(a) sinon
si est−vide(D(a)) alors a := G(a)
sinon
val(a) := Extraire-Max(G(a))
// voir algo. 4
end
Algorithme 3 : Supprimer un el´ement dans un ABR
Fonction Extraire-Max(ABR a) : cl´e
//On suppose que a est non vide !
begin
si est−vide(D(a)) alors
v := val(a) a := G(a)
return v
sinon
return Extraire-Max(D(a))
end
Algorithme 4 : Extraire le max d’un ABR non vide.
Proc´edure Ajouter(cl´e x, ABR a)
begin
r = a;
tant que ¬est−vide(r) faire
si x ≤ val(r) alors r := G(r);
sinon r := D(r)
r = Arbre(x, ArbreVide(), ArbreVide());
end
Algorithme 5 : Ajouter un el´ement dans un ABR (version it´erative)

Tri par ABR

Lorsque l’on parcourt un arbre binaire pour op´erer un certain traitement sur les noeuds, on distingue habituellement trois types de parcours : le parcours pr´efixe o`u on traite le Fonction Rechercher(cl´e x, ABR a) : bool´een begin
r = a;
tant que ¬est−vide(r) ∧ val(r)! = x faire
si x < val(r) alors r := G(r);
sinon r := D(r)
si est−vide(r) alors return Faux ;
sinon return Vrai
end
Algorithme 6 : Rechercher un el´ement dans un ABR (version it´erative).
noeud x d`es qu’on le rencontre (avant de traiter ses sous-arbres), le parcours infixe o`u l’on traite de noeud x juste apr`es le traitement de son sous-arbre gauche (et avant celui de son sous-arbre droit) et le parcours postfixe o`u l’on traite d’abord les sous-arbres avant le noeud x.
Pour aﬃcher les cl´es dans un ordre croissant, il suﬃt de consid´erer un parcours infixe : On consid`ere l’algorithme 7 de parcours d’un ABR avec aﬃchage de la valeur des noeuds internes lors du “second” passage.
Proc´edure Parcours(ABR a)
begin
si ¬est−vide(a) alors
[premier passage]
Parcours(G(a))
[second passage : Aﬃcher val(a)]
Parcours(D(a))
[troisi`eme passage]
end
Algorithme 7 : Parcours d’un ABR
Etant donn´ee une s´equence de nombres x1, . . . , xn a` trier, un algorithme possible consiste `a :
1. appeler Ajouter(a, xi) pour tout i, en commen¸cant avec a = l’arbre vide ;
2. appeler Parcours(a).

Analyse de complexit´

Une bonne r´ef´erence pour approfondir ces questions (notamment pour la complexit´ en moyenne) : “Introduction a` l’analyse des algorithmes”, R. Sedgewick, Ph. Flajolet, Interna-tional Thomson Publishing.
La complexit´ des op´erations sur les ABR sera mesur´ee en nombre de com-paraisons de cl´es.

D´efinitions

Soit a un ABR.
On note :
– Ni(a) l’ensemble des noeuds internes de a (et on a |Ni(a)| = |a|) ;
– Next(a) l’ensemble des noeuds externes (c.-a`-d. correspondant a` des arbres vides) de a ; et
– N(a) l’ensemble de tous les noeuds (internes ou externes) de a (on a bien sˆur N(a) =
Ni(a) ∪ Next(a)).
Nous avons la propri´et´ suivante sur le lien entre le nombre de cl´es et le nombre de feuilles dans a :
Propri´et´ 1 Pour tout ABR a, nous avons : |Next(a)| = |a| + 1.
Preuve : Par induction sur |a|. A faire en exercice !
On d´efinit aussi les notions suivantes :
def – la profondeur d’un noeud s de a : profa(s) = la longueur du chemin reliant la racine de a `a s.
(si s est la racine, sa profondeur est 0 ; si s est un fils de la racine, sa profondeur est 1, etc.)
def – la hauteur de a : h(a) = max {profa(s)}. s∈N(a)
Exemple 3 Si l’on consid`ere l’ABR de la figure 2, alors sa taille est 14, la profondeur du noeud contenant 10 est 2, celle du noeud contenant 35 est 1, et la hauteur de l’arbre est 5.
Notons que nous avons les deux propri´et´es suivantes :
Propri´et´ 2 a = 0 si est−vide(a)
• | | 1 + |G(a)| + |D(a)| sinon
• h(a) = 0 si est−vide(a)
1 + max(h(G(a)), h(D(a))) sinon
On ´evalue la complexit´ des op´erations Rechercher(x, a) et Ajouter(x, a). On va distin-guer le coˆut des recherches positives (lorsque la cl´e x est trouv´ee dans l’arbre a), et le coˆut des recherches n´egatives (lorsque la cl´e x n’appartient pas `a a).
On ´evalue la complexit´ des op´erations en nombre de comparaisons de cl´es en fonction de la taille de a (not´ee n).

Complexité dans le pire cas

Recherche positive. Etant donn´e un ABR a contenant n cl´es, alors dans le pire cas, une recherche positive d’une cl´e x peut n´ecessiter n comparaisons : n−1 comparaisons “n´egatives” et 1 derni`ere comparaison “positive”. Ce pire cas correspond au cas d’un arbre filiforme (o`u chaque noeud interne a au moins un fils qui est un arbre vide) de la forme d´ecrite `a la figure 3 (dans cet arbre, le pire cas est obtenu par la recherche de la cl´e 12).
Recherche n´egative. Le pire cas d’une recherche n´egative correspond aussi au cas d’ABR filiformes et son coˆut est alors de n comparaisons (n´egatives) : la cl´e x est compar´ee a` toutes les cl´es de a avant de conclure a` l’absence de x dans a. Dans le cas de l’ABR de la figure 3, un pire cas est obtenu, par exemple, avec la recherche de la cl´e 9.
Ajouter. Le pire cas pour la proc´edure Ajouter correspond aussi a` un ABR filiforme pour lequel l’ajout de la cl´e x n´ecessite de passer par tous les noeuds internes pour trouver la feuille o`u ins´erer x. Le coˆut est alors de n comparaisons (n´egatives). Dans le cas de l’ABR de la figure 3, on obtient un pire cas avec, par exemple, Ajouter(13,a).
Ces premiers r´esultats de complexit´ montrent que, dans le pire cas, un ABR n’est pas plus eﬃcace qu’un simple tableau ou qu’une liste (qui correspond d’une certaine mani`ere au cas des arbres filiformes).
La proc´edure Supprimer a aussi une complexit´ de n comparaisons dans le pire cas (tou-jours le cas des arbres filiformes).
La complexit´ de toutes ces op´erations sur les ABR est directement li´ee a` la hauteur de l’arbre sur lequel on applique l’op´eration (c’est a` dire sur la longueur d’un plus long chemin menant de la racine a` une feuille). Or cette hauteur, dans le pire cas, peut ˆetre lin´eaire (exactement n) dans la taille de l’arbre.

Complexité moyenne

Il s’agit maintenant d’´evaluer la complexit´ en moyenne d’une recherche positive, d’une recherche n´egative et de l’op´eration Ajouter. Pour cela, nous allons nous int´eresser a` un ABR “al´eatoire a` n cl´es” et mesurer le coˆut moyen de ces diﬀ´erentes op´erations sur cet arbre. Il faut pr´eciser plusieurs points :
Qu’est-ce qu’un arbre al´eatoire `a n cl´es ? On suppose qu’un ABR de taille n est obtenu par l’application de la fonction Ajouter sur une suite de n cl´es (distinctes) c’est l’ordre de ces cl´es dans cette suite qui fixe l’ordre des appels a` Ajouter et impose la forme de l’ABR. On supposera que toutes les n! permutations sur 1 n sont ´equiprobables. Il y a donc n! arbres a` consid´erer et chacun a la probabilit´e n1! .
Dans la suite, on note σn l’ensemble des n! permutations sur {1, . . . , n}. Et ´etant donn´ee
p une permutation de σnb, on notera a[p] l’ABR obtenu apr`es les op´erations Ajouter(p(1)), Ajouter(p(2)), . . . , Ajouter(p(n)) a` partir de l’arbre vide.
Notons que parmi ces n! arbres, il y a beaucoup de doublons : deux s´equences d’op´erations Ajouter peuvent conduire au mˆeme ABR : nous l’avions d´ej`a observ´ dans l’exemple 2, nous pouvons aussi le voir en consid´erons le cas avec n = 3 :
Exemple 4 L’ensemble σ3 contient les permutations {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2} et {3, 2, 1}. Ces 6 permutations donnent les 6 ABR de la figure 4. On voit que les permutations {2, 1, 3} et {2, 3, 1} donnent le mˆeme ABR.
Cette remarque est importante car ce que nous allons calculer est bien une moyenne sur les n! arbres et non sur l’ensemble (plus petit car sans doublon) des ABR a` n cl´es.
Comment ´evaluer le “coˆut moyen” des op´erations sur un arbre donn´e ? Etant donn´e un arbre a, le coˆut moyen d’une recherche positive est la somme des coˆuts de la recherche de chaque cl´e x pr´esente dans a multipli´es par la probabilit´e que la recherche porte sur x. On supposera que chaque cl´e est ´equiprobable, la probabilit´e est donc n1 . De plus, le coˆut de la recherche positive de x est profa(sx) + 1 o`u sx est le noeud interne contenant la cl´e
x : il y a d’abord profa(sx) tests n´egatifs avec les cl´es “au dessus” de x puis enfin un dernier
test positif sur x. Le coˆut moyen d’une recherche positive dans a, not´e CR+(a), est donc :
n profa(s).
s∈NI (a)
Si l’on d´efinit la longueur de cheminement interne (LCI) de a par :
def profa(s)
LCI(a) =
s∈NI(a)
alors on obtient que le coˆut moyen d’une recherche positive dans a est donc : CR+(a) = 1 + n1 LCI(a) Une recherche n´egative est une recherche qui s’arrˆete sur une des n + 1 feuilles (les arbres
vides) de a (ce nombre n + 1 vient de la propri´et´ 1). On va supposer que ces n + 1 cas sont ´equiprobables. On d´efinit la la longueur de cheminement externe (LCE) de a d´efini par :
def profa(s)
LCE(a) =
s∈NEXT (a)
Le coˆut moyen d’une recherche n´egative pour a, not´e CR−(a), va donc correspondre a` :
CR−(a) = n + 1 LCE(a)
Enfin pour ´evaluer le coˆut moyen d’une op´eration Ajouter, il faut se rappeler que chacune de ces op´erations commence par une recherche d’un arbre vide (une feuille de a) o`u on ins`ere la nouvelle cl´e. Le coˆut de cette op´eration est donc le mˆeme que celui des recherches n´egatives. L`a encore on supposera que les n+1 places o`u la nouvelle cl´e peut ˆetre ins´er´ee sont ´equiprobables,
le coˆut moyen d’une op´eration Ajouter, not´e CA(a), est donc n +1 1 LCE(a).
Enfin on peut aussi consid´erer le coˆut total de construction d’un ABR a, c’est-a`-dire la somme des coˆuts de toutes les op´erations Ajouter qui ont et´ r´ealis´ees pour le construire. Ce coˆut, not´e Ct(a) correspond a` la longueur de cheminement interne de a : en eﬀet, pour chaque cl´e x, son insertion a` demander de r´ealiser profs(sx) comparaisons. . . On a donc : Ct(a) = LCI(a).
De toutes ces remarques, il ressort que les valeurs LCI(a) et LCE(a) sont fondamentales pour ´evaluer la complexit´ en moyenne des op´erations sur les ABR. Elles interviennent dans toutes les mesures consid´er´ees. Et il s’agit a` pr´esent de les calculer pour un ABR al´eatoire a` n cl´es. Pour cela, nous allons d’abord montrer le lien entre LCE(a) et LCI(a).
On a la propri´et´ suivante :
Propri´et´ 3 Pour tout ABR non vide a, nous avons :
– LCI(a) = LCI(G(a)) + LCI(D(a)) + |a| − 1
– LCE(a) = LCE(G(a)) + LCE(D(a)) + |a| + 1
Preuve : On a bien LCI(a) = LCI(G(a)) + LCI(D(a)) + |a| − 1 car pour chaque noeud interne de a `a l’exception de la racine, il faut ajouter 1 `a sa profondeur dans le sous-arbre gauche ou droit pour retrouver sa hauteur dans a.
Le mˆeme raisonnement s’applique pour LCE(a) mais cette fois il faut ajouter 1 pour tous les
noeuds externes (il y en a |a| + 1). On en d´eduit :
Propri´et´ 4 Pour tout ABR a, on a : LCE(a) = LCI(a) + 2 | a|
Preuve : A faire en exercice !
Ce dernier r´esultat permet donc de d´eduire LCE de LCI et vice-versa. Il nous reste donc `a calculer l’une de ces deux quantit´es pour obtenir la complexit´e en moyenne de nos op´erations.
Pour cela, nous allons montrer deux m´ethodes diﬀ´erentes : la premi`ere va partir de la d´efinition de la longueur de cheminement externe d’un ABR al´eatoire (la moyenne pond´er´ee des LCE sur les n! ABR `a n cl´es), la seconde va proc´eder autrement en raisonnant directement sur le coˆut total des op´erations Ajouter r´ealis´ees pour le construire (qui, comme nous avons note precedemment, correspond `a la LCI).

A. Introduction
1 Rappel sur la complexite des algorithmes
1.1 Evaluer la complexite d’un algorithme
B. Arbres binaires de recherche
1 D´efinitions
2 Op´erations de base
2.1 Rechercher un element
2.2 Ajouter un element
2.3 Supprimer un element
2.4 Algorithmes iteratifs
3 Tri par ABR
4 Analyse de complexit´e
4.1 D´efinitions
4.2 Complexit´e dans le pire cas
4.3 Complexit´e moyenne
4.3.1 Premi`ere m´ethode
4.3.2 Seconde m´ethode
4.3.3 R´esolution de la r´ecurrence
4.3.4 Analyse de complexit´e
5 Arbres binaires de recherche ´equilibr´es
5.1 D´efinitions
5.2 Ajout dans un AVL
5.3 Suppression dans les AVL
C. Algorithmique dans les graphes
1 D´efinitions
1.1 Graphes orient´es
1.2 Graphes non-orient´es
1.3 Graphes valu´es
1.4 Repr´esentation des graphes
2 Parcours de graphes
3 Parcours en largeur
4 Parcours en profondeur
5 Recherche d’une extension lin´eaire
6 Recherche des composantes fortement connexes ⋆ ⋆
6.1 La d´efinition des coefficients r(−)
6.2 L’algorithme de calcul des coefficients r(−)
7 Arbres couvrants minimaux
7.1 Algorithme de Kruskal
7.2 Algorithme de Prim
8 Plus courts chemins
8.1 Algorithme de Dijkstra
8.2 Algorithme de Floyd-Warshall
References