Algorithmique, structures de données

et complexité
ESI – SEMESTRE 3
ENSEIGNANT : DR COMPAORE A. JOELLE
 Organisation du cours

 Cours théorique : 30 h
 Travaux dirigés : 15 h
 Travaux pratiques : 15h
 Evaluation :
 Un projet en binôme (ou trinôme) à rendre à la fin du cours

 un examen écrit après la dernière séance du cours

 Objectifs du cours

A l’issue du cours l’étudiant doit

 Être apte à
 Définir l’algorithmique et ses principales activités
 Comprendre la notion de structure de données
 Concevoir des algorithmes
 Choisir les bonnes structures de données
 S’assurer de la correction de l’algorithme (méthode des invariants)
 Calculer la complexité (en temps) d’un algorithme et comparer deux
algorithmes sur la base de le leurs complexités respectives
 Programmer ou utiliser en Python
 Quelques algorithmes conçus
 les principales structures de données définies
 Plan du cours

 Chapitre I : Introduction
 Les activités de l’algorithmique
 La complexité d’un algorithme
 Structures de données
 Chapitre I : Introduction

 Algorithmes et algorithmique
 De la spécification des algorithmes
 Les activités de l’algorithmique
 La complexité d’un algorithme
 Structures de données
 Chapitre I : Introduction
Algorithmes et algorithmique

 Définition (algorithme)
 Outil de résolution
 d’un problème de calcul bien spécifié par un énoncé (donnant une
relation R souhaitée entre des entrées (E) et des sorties (S)
 qui décrit la procédure de réalisation de la relation R

 Exemple
 Énoncé problème : calcul du factoriel d’un nombre naturel x
 Entrée : x

 Sortie : y = x!

 Algorithme :
 si x <= 1 alors y  1

 sinon y  x * (x-1) * … * 2
 Chapitre I : Introduction
Algorithmes et algorithmique

 Définition (algorithme)
 Procédure de calcul bien définie
 Prenant des entrées (E) : valeurs
 Pour calculer des sorties (S) : valeurs
 Oui/non : algorithmes décisionnels

 Autres : algorithmes d’évaluation

 Cette procédure est générique : résout des instances de

problèmes, c.-à-d.
 cas particulier
 défini par les entrées (respectant les conditions de l’énoncé)
nécessaires au calcul
 Chapitre I : Introduction
Algorithmes et algorithmique

 Langage d’écriture des algorithmes

 en langage naturel
 Exemple pour factoriel : Étant donné un entier naturel
x, y sera égal à 1 si x est inférieur ou égal à un,
autrement y sera égal au produit de tous les nombres
allant de 2 à x
 sous forme graphique
 en pseudo code
 Chapitre I : Introduction
Algorithmes et algorithmique

 Langage d’écriture des algorithmes

 en langage naturel
 sous forme graphique
 Exemple pour factoriel …

 en pseudo code
 Chapitre I : Introduction
Algorithmes et algorithmique

 Langage d’écriture des algorithmes

 en langage naturel
 sous forme graphique

 en pseudo code
 Exemple pour factoriel …
 Les algorithmes en informatique
De la spécification du problème

 La spécification du problème (donnant en particulier

les conditions sur les entrées et les sorties) doit
également être précise et non ambigüe
 Exemple
 spécification du problème de tri d’une séquence de nombres
 Entrée : séquence de nombres Sq = a1, …, an
 Sortie : permutation  a’1, …, a’n des élts de Sq tq a’1  a’2  a’n
 Algorithme : décrit la manière d’effectuer la permutation
 tri par insertion (insertion sort)
 tri bulle (bubble sort)
 tri fusion (merge sort)
 tri par tas (heap sort)
 Les algorithmes en informatique
De la spécification du problème

 Elle peut s’écrire

 En langage naturel
 Avantages : facile à lire
 Inconvénients : ambiguïté, bruit et/ou le silence
 En langage semi-formel : généralement graphique
 Syntaxe bien définie
 Peut être basé sur le langage naturel
 par structuration (formulaire, canevas)
 Par annotation de graphique
 Par algorithme
 Avantages : plus de précision, facile à lire, existence d’outils
 Inconvénient : sémantique non formalisée

 Langage formel
 Les algorithmes en informatique
De la correction d’un algorithme

 Un algorithme est :
 (totalement) correct : pour chaque instance donnée :
 il se termine
 il produit la bonne sortie.

 partiellement correct :
 Il existe des instances sur lesquelles il ne termine pas
 Sur les autres instances, il termine et produit la bonne sortie

 Incorrect : tous les autres cas

 Les algorithmes en informatique
Quelques types de problèmes relevant des algorithmes

 Problème de tri d’éléments

 Problèmes de bioinformatique : détermination de
séquences particulières, identification des gènes, …
 Problèmes liés à Internet : recherche de routes
optimales, utilisation d’un moteur de recherche
 Problème de gestion de la confidentialité dans le
commerce électronique
…
 Les algorithmes en informatique
Problèmes difficiles (NP-complets)

 Algorithme efficace : habituellement qui résout le

problème en un temps déterminé.

 Problèmes NP-complets : problème

 pour lesquels on ne connaît pas de solution efficace sans avoir
la preuve qu’il n’en existe pas
 Ont la propriété suivante : l’existence d’un algorithme efficace
pour un implique l’existence d’un tel algorithme pour tous
 Solution : algorithme d’approximation…

 Exemple ?
 Les algorithmes en informatique
Importance des algorithmes

 Peuvent être vus comme une technologie

 plusieurs algorithmes pour le même problème

 La performance totale système

 Choix du matériel
 Choix des algorithmes

 Au cœur des autres technologies liées à l’ordinateur

 Conception du matériel

 Conception des interfaces graphiques

 Recherche des routes dans un réseau

 Les algorithmes en informatique
Activités de l’algorithmique

 Conception
 Spécifier le problème
 Se fixer un langage
 Ecrire la procédure de calcul dans ce langage
 S’assurer de la correction de l’algorithme

 Analyse
 Prédiction ressources requises : - de ressources = + efficace
 Temps de calcul
 Mémoire
 Bande passante
 Pertinente avec l’augmentation de la taille des problèmes
 Différence d’efficacité considérable
 Les algorithmes en informatique
Algorithmes considérés dans ce cours

 Manipulant des ensembles de données sans

préoccupation particulière pour l’organisation
interne de ces données
 Manière d’organiser les ensembles d’objets
 Objets = (possède une clé) essentiellement entier
 L’augmentation du temps de calcul liée à la taille des entrées
(en nombre d’objets)
 Les activités de l’algorithmique
Conception d’algorithme

conventions de pseudo code

 Variables : x : type
 Délimitation blocs : indentation
 Affectation : =
 Structures de contrôle
 conditionnelle : if, if-else

 boucles for , while, repeat-until

 Passage de paramètres : Par valeur

 Évaluation opérateurs « and » et « or » : court-circuitée
 Return : similaire au C
 Les activités de l’algorithmique
Conception d’algorithme

conventions de pseudo code

 Structures de données
 Objets avec attributs E
 Accès à l’attribut ch1 de E : E.ch1
 Variable objet = pointeur sur l’objet

 Tableau T
 Accès au nombre d’éléments : [Link]
 Accès à l’élément i de T : T[i]
 Matérialisation d’un sous-tableau de T : T [i .. j]
 Variable = pointeur sur le tableau
 Les activités de l’algorithmique
Conception d’algorithmes

Exemple d’algorithme
• Deux instructions
T de taille n contient des entiers de [0,n] o Boucle for
1 for i = n downto 1 o Traitement3
2 traitement1 • for : trois instructions
3 j = T[i]; o Traitement1
4 while j > i o Affectation j = T[i]
5 traitement2 o Boucle while
6 j=j–1 • while : deux instructions
7 traitement3 o Traitement2
o Affectation j = j+1
 Les activités de l’algorithmique
Conception d’algorithmes

Techniques de conception
 Diviser pour régner (divide-and-conquer)
 Selon les opérations à effectuer
 Selon la taille des données à traiter
 Trois actions
 Divide : diviser le problème en plusieurs sous-problèmes plus
petites instances du problème initial
 Conquer : résoudre les sous-problèmes récursivement si leur taille
est suffisamment grande
 Combine : combiner les solutions aux sous-problèmes pour obtenir
une solution au problème initial
 Temps de calcul caractérisé par la récurrence

 Programmation dynamique
 Algorithmes gloutons
 Les activités de l’algorithmique
Conception d’algorithmes

Techniques de conception
 Diviser pour régner
 Programmation dynamique
 Problème d’optimisation

 Plusieurs solutions optimales sont possibles

 Idée : ne pas résoudre plusieurs fois les mêmes sous-problèmes

 Algorithmes gloutons
 Problèmes d’optimisation

 Choix de la solution optimale à l’instant t (choix optimal local)

 Les activités de l’algorithmique
Conception d’algorithmes

Prouver la correction de l’algorithme conçu

(termine et produit le bon résultat)

Dans ce cours
 Classe d’algorithmes : avec boucles
 Vérification de la correction : par les invariants de
boucles
 Les activités de l’algorithmique
Conception d’algorithmes

Correction d’un algorithme : méthode de l’invariant

 Invariant : expression qui est toujours vraie dans une boucle
 Principe de la méthode
 Détermination de l’invariant inv
 Vérification des propriétés sur inv
 Initialisation : inv est vrai avant la première itération
 Maintenance : si inv est vrai avant l’itération i, il reste vrai avant
l’itération i+1
 Terminaison : si la boucle se termine, inv permet de montrer que le
résultat est celui attendu.
 Les activités de l’algorithmique
Analyse d’algorithmes

 Objectif : comparer des algorithmes sur la base des

ressources nécessaires
 Du temps de calcul : complexité en temps
 De l’espace mémoire : complexité en espace
 De la bande passante : en bande passante
 Les activités de l’algorithmique
Analyse d’algorithmes

 Options retenues (pour ce cours)

 Ressource : temps de calcul = nombre d’étapes ou d’instructions
élémentaires (dépend de la machine)
 Conventions (sur la machine)
 Modèle de calcul : Random Access Machine (RAM)
 Exécution séquentielle des instructions

 Un seul processeur

 Mémoire RAM (adressable en temps constant)

 Chaque ligne i de l’algorithme s’exécute à temps constant ci

➔ temps de calcul = somme (des temps de chaque ligne *
nombre d’exécutions de chaque ligne)
 Les activités de l’algorithmique
Analyse d’algorithmes

Détermination du temps de calcul

Exemple : T de taille n, contient des
coût X fois
entiers de [0,n]
c1 n+1
1 for i = n downto 1
c2 n
2 traitement1
c3 n
3 j = t[i];
c4
4 while j > i
c5
5 traitement2
c6
6 j=j–1
c7 1
7 traitement3
 Les activités de l’algorithmique
Analyse d’algorithmes

Détermination du temps de calcul

Exemple : T de taille n, contient des entiers coût X fois
de [0,n] c1
1 nb = 1; c2
2 for i = n downto 1 c3
3 nb = nb+3; c4
4 j = t[i]; c5
5 while j > i c6
6 nb = nb + 3; c7
7 j= j-1; c8
8 nb = nb + 3; C9
9 retourner (nb+1);
 Les activités de l’algorithmique
Analyse d’algorithmes

Meilleur, moyen et pire cas

 Étant donnée une entrée de taille n, T(n) peut dépendre
 De n
 De la nature de l’entrée

 Analyse en trois cas (considérant la particularités de l’entrée)

 Meilleur cas : plus petit temps de calcul possible
 Pire cas : plus grand temps de calcul possible
 Le plus calculé
 Garantit que ce temps ne peut être dépassé
 Cas se produit souvent
 Moyen cas : les temps de calcul intermédiaires
 Peu d’analyses en moyen cas
 Analyses avec les techniques probabilistes
 Cas difficile à caractériser
 Coïncide souvent avec le pire cas
 Les activités de l’algorithmique
Analyse d’algorithmes

Meilleur cas : tous les T[i] soient inférieurs ou égaux à i

T contient des entiers de [0,n]
1 for i = n downto 1
2 traitement1
3 j = t[i];
4 while j > i
5 traitement2
6 j=j–1
7 traitement3
 Les activités de l’algorithmique
Analyse d’algorithmes

Pire cas : tous les T[i] sont égaux à n.

T contient des entiers de [0,n]
1 for i = n downto 1
2 traitement1
3 j = t[i];
4 while j > i
5 traitement2
6 j=j–1
7 traitement3
 Les activités de l’algorithmique
Analyse d’algorithmes

Ordre de croissance T(n)

 Efficacité asymptotique : Etude de la manière dont croît le
temps de calcul avec l’augmentation de la taille de l’entrée (n).
 n est le seul paramètre connu
 Caractérisation du temps de calcul indépendamment de la
particularité des entrées
 Si un algorithme A1 est asymptotiquement plus efficace qu’un
algorithme A2, il constitue en général le meilleur choix (sauf
éventuellement sur des petites tailles)
 Les activités de l’algorithmique
Analyse d’algorithmes

 Exemple : On donne n = 100 n = 200 n = 106

 T(n)A1=10n+10000 T(n)A1 11 000 12 000 1,001.107
 T(n)A2 = n2 T(n)A2 10 000 40 000 1012

 T(n)A3 = 2n2+n T(n)A3 20 100 80 200 2,000001.1012

 Observations ?

 Abstraction
 constantes
 Termes de degrés inférieurs

 Coefficient du terme de plus haut degré

➔ T(n)A1= n, T(n)A2 = n2 , T(n)A3 = n2
 Les activités de l’algorithmique
Analyse d’algorithmes

Notations asymptotiques
 Soit g(n) une fonction de n :
 (g(n)) = {f(n) :  c1 > 0, c2 > 0 et n0 tels que
0  c1g(n)  f(n)  c2g(n) pour tout n  n0}

 O(g(n)) = {f(n) :  c > 0 et n0 tels que

0  f(n)  cg(n) pour tout n  n0}

 (g(n)) = {f(n) :  c > 0 et n0 tels que

0  cg(n)  f(n) pour tout n  n0}
 Les activités de l’algorithmique
Analyse d’algorithmes

Notations asymptotiques
 Soit g(n) une fonction de n :
 o(g(n)) = {f(n) :  c > 0,  n0 > 0 tels que
0  f(n) < cg(n) pour tout n  n0}

 (g(n)) = {f(n) :  c > 0,  n0 > 0 tels que

0  cg(n) < f(n) pour tout n  n0}
 Les activités de l’algorithmique
Analyse d’algorithmes

Notations asymptotiques
 f(n) = (g(n))  f(n)  (g(n))
 Dans une formule : fonction anonyme
 2n2+3n+1 = 2n2+ (n) ➔ 2n2+3n+1 = 2n2+ f(n) avec f = (n) (f 
(n))
 2n2+ (n) = (n2) : quelque soit f(n)  (n), il existe des fonctions
g(n)  (n2) tel que 2n2+ f(n) = g(n)
 Les activités de l’algorithmique
Analyse d’algorithmes

Notations asymptotique : exercices

 2n = O(n2) ?  2n = (n2) ?
 2n = (n2) ?
 2n2 = O(n2) ?  2n2 = (n2) ?
 2n2 = (n2) ?
 2n = o(n2) ?  n2/2 = (n) ?
 2n2 = o(n2) ?  n2/2= (n2) ?

Exercice : Montrer que

•1/2n2-3n=(n2)
•6n3  (n2)
 Les activités de l’algorithmique
Analyse d’algorithmes

Notations asymptotique : exemples

 2n = O(n2) ?  2n = (n2) ?  2n = (n2) ?
 2n2 = O(n2) ?  2n2 = (n2) ?  2n2 = (n2) ?
 2n = o(n2) ?  n2/2 = (n) ?
 2n2 = o(n2) ?  n2/2= (n2) ?

Exercice : Montrer que

• (1/2)n2-3n=(n2) : Trouvez c1, c2 et n0 tq c1n2  (1/2)n2 – 3n  c2n2  n
 n0
• 6n3  (n2)
 Les activités de l’algorithmique
Analyse d’algorithmes

Propriétés de la notation asymptotique

 Transitivité (Toutes les notations) :
f(n) = (g(n)) et g(n) = (h(n)) alors f(n) = (h(n))
 Réflexivité (, O, )
f(n) = O(f(n))
 Symétrie ()
f(n) = (g(n)) ssi g(n) = (f(n))
 Symétrie transposée(O et  ; o et )
f(n) = O(g(n)) ssi g(n) = (f(n))
 Les activités de l’algorithmique
Analyse d’algorithmes

Principales fonctions
 Polynômes :
 Constantes (O(1))
 Linéaires (O(n))
 Quadratiques et polynomiales (O(n2) et O(nk))
 Logarithmes (log n) : Notations
 lg n = log2n; ln n = loge n ; lgk n = (lg n)k ; lg lg n = lg (lg n)
 Pout tous a, b, c > 0
 logc(a b) = logc a + logc b ; logb(an) = n logba
 logb(a) = logc a / logc b ; logb(1/a) = - logb a
 logb(a) = 1/loga b ; alogb c = clogb a

 Exponentielle (puissances, xn)

 Les activités de l’algorithmique
Analyse d’algorithmes

Calcul de la complexité T contient des entiers de [0,n]

1 for i = n downto 1
2 traitement1
3 j = t[i];
4 while j > i
5 traitement2
6 j=j–1
7 traitement3

En pratique, possibilité remplacer ci par 1

• Meilleur cas : = 4n + 2 = O(n)

• Pire cas :

= (3/2)n2 + (9/2)n + 2 = O(n2)

 Les activités de l’algorithmique
Analyse d’algorithmes

Calcul de la complexité : quelques règles

 Pour chaque ligne
 Instructions à temps constant :
 O(1) (quelque soit ci)

 Conditionnelle :
 O(test_condition)+O(bloc_if)+O(bloc_else)

 Boucles :
 k*(O(test_condition)+O(corps_boucle)), avec k le nombre
d’itérations
 Combinaisons des complexités de toutes les lignes
 Les activités de l’algorithmique
Analyse d’algorithmes

Calcul de la complexité : opérations sur la notation O

 Addition
 O(f(n)) + O(g(n)) = O(f(n) + g(n))
 O(1)+O(1) = O(1)
 O(f(n)) + O(1) = O(f(n))

 Multiplication
 x*O(f(n)) = O(x*f(n))

 O(f(n)) * O(g(n)) = O(f(n)*g(n))

 Les activités de l’algorithmique
Analyse d’algorithmes

Calcul de la complexité : application

T contient des entiers de [0,n]
1 for i = n downto 1 (n+1) * O(1) = O(n)
2 traitement1 O(1)
3 j = t[i]; O(1)
4 while j > i n*O(1) = O(n)
5 traitement2 O(1)
6 j=j–1 O(1)
7 traitement3 O(1)

T(n) = O(n) * (O(1)+O(1)+(O(n)*(O(1)+O(1)))+O(1)

= O(n) * (O(1)+(O(n)*(O(1)))+O(1)
= O(n) * (O(1)+(O(n*1))+O(1) …. = O(n)*O(n) = O(n*n) = O(n2)
 Technique du divide-and-conquer
Récurrence

 Récurrence = équation (inéquation) décrivant une

fonction en termes des valeurs sur des entrées plus
petites. Exemple

 Caractérise le temps de calcul des algorithmes conçus

avec la technique du divide-and-conquer (division
selon n)
 3 méthodes de résolution
 La méthode de substitution
 La méthode de l’arbre de récursion
 La master méthode
 Résolution de la récurrence
La méthode de substitution

Deux étapes
 Deviner la forme de la solution
 Utiliser l’induction mathématique pour
 trouver les constantes
 Montrer que la solution marche
 Résolution de la récurrence
La méthode de substitution

Trouver une borne supérieure pour T(n) = 2T(n/2)+n

 Deviner la forme de la solution
T(n) = O(n lg n)
 Utiliser l’induction mathématique pour
 À prouver T(n) <= c n lg n
 On suppose que cette borne est respectée pour tous les m < n en
particulier pour m = n/2.
 T(n/2) <= c n/2 lg (n/2)
 T(n) <= 2 (c n/2 lg (n/2)) +n
 <= c n lg(n/2) + n
 = c n lg n – c n lg 2 + n
 = c n lg n - c n + n
 <= c n lg n
 Résolution de la récurrence
La méthode de l’arbre de recursion

Arbre de récursion = arbre dans lequel tout nœud

représente le temps de calcul d’un sous-problème
Trois étapes
 Construire l’arbre à partir de l’expression de T(n)
 Evaluer le temps de calcul de chaque niveau de l’arbre
 Additionner ces temps pour avoir le temps de calcul de tous les
niveaux
 Résolution de la récurrence
La méthode de l’arbre de recursion : exemple

Arbre de récursion pour

 On considère n = 2p
cn

 Arbre construit cn/2 cn/2)

 Temps par niveau : c n cn/4 cn/4 cn/4 cn/4

 Nombre de niveaux : lg n

...
c c c c c c
 Résolution de la récurrence
La master method

 Résolution (à l’aide du master thorem) de récurrence de la

forme T(n)=aT(n/b)+f(n) avec a >=1 et b>1

Master theorem :
Soient
 a >=1 et b > 1 des constantes;
 f(n) une fonction
 T(n) = aT(n/b)+f(n) avec n >=0
T(n) a les bornes asymptotiques suivantes
a)-
 Si f(n) = O(n(logb ) avec  constante > 0, alors T(n) = (nlogba)
a log a
 Si f(n) = (nlogb ), alors T(n) = (n b lg n)
a)+
 Si f(n) = (n logb ) avec  constante > 0 et si a f(n/b) <= c f(n) pour c
constante < 1 et n suffisamment grand, alors T(n) = (f(n))
 Résolution de la récurrence
La master method : exemples

 Application de la méthode
 Identifier le cas

 Écrire la réponse

 T(n) = 9 T(n/3) + n
Cas 1 ➔ T(n) = (n2)
 T(n) = T(2n/3) + 1
cas 2 ➔ T(n) = (lg n)
Les algorithmes de tri
 Algorithmes de tri
Généralités

 Permettent de trier un ensemble d’objets en fonction

de critères
 Problèmes de tri très courants en informatique
 Dans ce cours, tri d’entiers du plus petit au plus grand
 Rappel de spécification
 Entrée : séquence de nombres Sq = a1, …, an
 Sortie : permutation  a’1, …, a’n des élts de Sq tq a’1  a’2  a’n
 Tri par insertion(Insertion sort)
L’algorithme

 Tableau d’entiers A de 1 for j = 2 to [Link]

taille n ([Link] =n) 2 k = A[j]
3 i = j-1;
 Tri sur place
4 while i > 0 and A[i] > k
 Technique incrémentale 5 A[i+1] = A[i]
 Principe : 2 tas 6 i=i–1
7 A[i+1] = k
 Tas trié

 Tas non trié

 Le prochain élément du tas
non trié est inséré à la bonne
place dans le tas trié et ainsi
de suite
 Tri par insertion(Insertion sort)
Correction de l’algorithme

 Invariants de boucles
 Boucle for : A[1 .. j-1]
 contient les j-1 1ers éléments de A
 est trié

 Boucle while : j <= n and A[i +1] >= k

 Preuve informelle
 Initialisation : vrai (A[1] est trié ne contenant qu’un élément)
 Maintenance : On a A[1..j-1] trié et on insère A[j] dans A[1..j] avant
le 1er élément supérieur => A[1..j] contient les j premiers éléments
de A dans le bon ordre : invariant vrai avant l’itération j+1.
 Terminaison : j = n+1. A[1..n] est trié et contient tous les éléments
de A
 Tri par insertion(Insertion sort)
Le temps de calcul

1 for j = 2 to [Link] Coûts Nb exécutions

2 k = A[j] c1 n
3 i = j-1; c2 n-1
4 while i > 0 and A[i] > k c3 n-1
5 A[i+1] = A[i] c4
6 i=i–1
7 A[i+1] = k c5

c6
(Au mieux)
c7 n-1
(Au pire)
 Tri fusion (Merge sort)
Généralités

 Tableau d’entiers A de taille n

 Intéressant lorsque n = 2p
 Technique : divide-and-conquer
 Principe
 Diviser le tableau en 2 sous-tableaux de taille n/2

 Trier les deux sous-tableaux en utilisant le tri fusion

 Fusionner les deux sous-tableaux triés

 Tri fusion (Merge sort)
Les algorithmes
 Algorithme de fusion : etape COMBINE
 Algorithme étapes DIVIDE et CONQUER
MERGE(A, p, q, r)
MERGE-SORT(A,p,r)
1 n1 = q – p + 1
if p < r
2 n2 = r – q
q = (p + r)/2
3 let L[1..n1 + 1] and R[1..n2+1] be new arrays
MERGE-SORT(A, p, q)
4 for i = 1 to n1
MERGE-SORT(A, q+1, r)
5 L[i] = A[p+i-1]
MERGE (A, p, q, r)
6 for j = 1 to n2
7 R[j] = A[q+j]
8 L[n1+1] = 
9 R[n2+1] = 
10 i = 1
11 j = 1
12 for k = p to r
13 if L[i] <= R[j]
14 A[k] = L[i]
15 i=i+1
16 else
17 A[k] = R[j]
18 j=j+1
 Tri fusion (Merge sort)
Exemple d’application
Soit à trier le tableau A = 5,2,4,7,1,3,2,6

 MERGE-SORT(A,1,8)  MERGE-SORT(A, 5, 8)
 Division du tableau en A1 = 5,2,4,7 et A2 =  Division de A2 en A21 = 1,3 et A22 = 2,6
1,3,2,6  MERGE-SORT(A, 5, 6)
 MERGE-SORT(A, 1, 4)
 Division de A21 en A211 = 1 et A212 = 3
 Division de A1 en A11 = 5,2 et A12 = 4,7
 MERGE-SORT(A,5,5]
 MERGE-SORT(A, 1, 2)
 MERGE-SORT(A,6,6)
 Division de A11 en A111 = 5 et A112 = 2
 MERGE(A,5,5,6)
 MERGE-SORT(A,1,1]
 MERGE-SORT(A,7,8)
 MERGE-SORT(A,2,2)
 Division de A22 en A221 = 2 et A122 =
 MERGE(A,1,1,2) 6
 MERGE-SORT(A,3,4)  MERGE-SORT(A,7,7]
 Division de A12 en A121 = 4 et A122 = 7  MERGE-SORT(A,8,8)
 MERGE-SORT(A,3,3]  MERGE(A,7,7,8)
 MERGE-SORT(A,4,4)  MERGE(A,5,6,8)
 MERGE(A,3,3,4)  MERGE(A,1,4,8)
 MERGE(A,1,2,4)
 Tri fusion (Merge sort)
Correction de l’algorithme
 Algorithme de fusion : etape COMBINE
MERGE(A, p, q, r)  Invariant de boucle
1 n1 = q – p + 1
2 n2 = r – q  A[p..k-1] contient les k-p plus
3 let L[1..n1 + 1] and R[1..n2+1] be new arrays petits éléments de L et R dans
4 for i = 1 to n1
5 L[i] = A[p+i-1]
l’ordre trié ; Par ailleurs,
6 for j = 1 to n2  L[i] (respect R[j] est le plus petit
7 R[j] = A[q+j]
élément de L (respect R) non
8 L[n1+1] = 
9 R[n2+1] =  encore recopiés dans A
10 i = 1
11 j = 1
12 for k = p to r
13 if L[i] <= R[j]
14 A[k] = L[i]
15 i=i+1
16 else
17 A[k] = R[j]
18 j=j+1
 Tri fusion (Merge sort)
Temps de calcul

 On suppose T(n) le temps de calcul du tri fusion de n

entiers.
 Divide : D(n) = (1)
 Conquer : résolution de 2 sous-problèmes de taille n/2 ➔
contribution de 2T(n/2)
 Combine : C(n) = (n)
 Tri rapide (Quicksort)
Généralités

 Tableau d’entiers A de taille n

 Technique : Divide-and-conquer
 Principe
 Divide : partitionnement de A[p..r] en :
 A[p..q-1] : éléments <= A[q]
 A[q+1..r] : éléments >= A[q]

 Conquer : tri rapide des sous-tableaux

 Combine : rien à faire
 Tri rapide (Quicksort)
Les algorithmes
 Algorithme de partitionnement
 Algorithme QUICKSORT
PARTITION(A,p,r)
QUICKSORT(A,p,r)
1 x = A[r]
if p < r
2 i=p–1
q = PARTITION(A,p,r)
3 for j = p to r-1
QUICKSORT(A, p, q-1)
4 if A[j] <= x
QUICKSORT(A, q+1, r)
5 i=i+1
6 exchange A[i] with A[j]
7 exchange A[i+1] with A[r]
8 return i+1
 Tri rapide (Quicksort)
Exercices
 Quelle sera la valeur q retournée par la fonction PARTITION si tous les
éléments du tableau sont égaux

 Simuler le partitionnement du tableau 2, 8, 7, 1, 3, 5, 6, 4

 Tri par tas (Heapsort)
La structure de données (le tas = heap)

 Tableau assimilable à un arbre binaire presque complet

 Chaque nœud de l’arbre correspond à un élément du tableau
 Tous les niveaux complets sauf éventuellement le dernier rempli à
partir de la gauche
 Un tableau tas A
 a deux attributs
 [Link] : nombre d’éléments
 [Link]-size : nombre d’éléments du tas A[1..[Link]-size].
 A[1] est la racine de l’arbre
 Étant donné un indice i, on peut déterminer les indices de :
 Son père (PARENT(i) : return  i/2 )
 Son fils gauche (LEFT(i) : return 2i)
 Son fils droit (RIGHT(i) : return 2i + 1)
 Tri par tas (Heapsort)
La structure de données (le tas = heap)

 Notion de hauteur
 D’un nœud = nombre de nœuds sur le plus long chemin de ce
nœud à une feuille
 D’un tas = hauteur du nœud racine

 Deux types de tas selon propriété satisfaite par les

nœuds
 Max-heap : pour tout nœud i, A[parent(i)] >= A[i]
 Min-Heap : pour tout nœud i, A[parent(i)] <= A[i]
 Tri par tas (Heapsort)
La structure de données (le tas = heap)

 Principales opérations (Max-heap)

 MAX-HEAPIFY : permet de maintenir la propriété de max-heap

 BUILD-MAX-HEAP : produit un max-heap à partir d’un tableau

non ordonné
 HEAPSORT : trie un tableau tas
 Tri par tas (Heapsort)
La structure de données (le tas = heap) : exemple

 On considère le tableau (1ère ligne : indices)

1 2 3 4 5 6 7 8 9 10
16 14 10 8 7 9 3 2 4 1

16

14 10

8 7 3
9

2 4 1
 Tri par tas (Heapsort)
La structure de données (le tas = heap) : exercices

 Quels sont les nombres d’objets minimum et

maximum d’un tas de hauteur n?
 Un tableau trié est-il un min-heap ?
 Le tableau 23,17,14,6,13,10,1,5,7,12 est-il un max-
heap?
 Tri par tas (Heapsort)
Les opérations d’un tas : MAX-HEAPIFY(A,i)

MAX-HEAPIFY(A,i)
Son appel suppose
1 l = LEFT(i)
 Sous-arbres partant
2 r = RIGTH(i)
de LEFT(i) et
3 if l <= [Link]-size and A[l] > A[i]
RIGTH(i) sont des
max-heap 4 largest = l
5 else
 A[i] viole la
propriété de max- 6 largest = i
heap 7 if r <= [Link]-size and A[r] > A[largest]
8 largest = r
9 if largest  i
10 exchange A[i] with A[largest]
11 MAX-HEAPIFY (A, largest)
 Tri par tas (Heapsort)
Application de MAX-HEAPIFY

Appel de MAX-HEAPIFY sur le nœud d’indice 2.

16 16

4 14 10
10

4 7 9 3
14 7 9 3

2 8 1
2 8 1

16

14 10

8 7 9 3

2 4 1
 Tri par tas (Heapsort)
Les opérations d’un tas : BUILD-MAX-HEAP(A)

BUILD-MAX-HEAP(A)
Son appel permet
1 [Link]-size = [Link]
 De convertir un
2 for i = [Link]/2 downto 1
tableau en un max-
3 MAX-HEAPIFY(A,i)
heap

Exemple d’application avec les tableaux

23,17,14,6,13,10,1,5,7,12
4,1,3,2,16,9,10,14,8,7
 Tri par tas (Heapsort)
Les opérations d’un tas : HEAPSORT(A)

HEAPSORT(A)
Son appel permet 1 BUILD-MAX-HEAP(A)
 De trier un tableau 2 for i = [Link] downto 2
représentant un tas 3 exchange A[1] with A[i]
4 [Link]-size = [Link]-size - 1
5 MAX-HEAPIFY(A,1)

Exemple d’application avec les tableaux

23,17,14,6,13,10,1,5,7,12
4,1,3,2,16,9,10,14,8,7
 Tri par tas (Heapsort)
Application fondée sur les tas : les files de priorité

 Files de priorités : structure de données permettant de

maintenir un ensemble S d’éléments chacun étant assorti
d’une valeur appelée clé.
 Deux sortes
 max-priority queue : plus prioritaires = plus grande valeur de clé
 min-priority queue : plus prioritaires = plus petite valeur de clé
 Opérations sur les max-priority queue
 INSERT(S, x) : insertion d’un élément à clé x dans S (S  {x})
 MAXIMUM (S) : retourne l’élément de S ayant la plus grande clé
 EXTRACT-MAX(S) : supprime de S et retourne l’élément prioritaire
 INCREASE-KEY(S, x, k) : Associe à x la clé k qui doit être supérieure à
l’ancienne clé de x
 Tri par tas (Heapsort)
Les files de priorité : exercices

 Ecrire les algorithmes des quatre opérations

applicables aux max-priority queues
Structures de données
 Structures de données (SD)
Généralités

 Organisation de données en vue de faciliter leurs accès

et leurs modifications
 Correspond à l’implémentation d’un type abstrait de
données
 Les SD déjà implémentées :
 Tableaux
 Chaînages
 Enregistrements (structures)
sont utilisées pour implémenter les autres SD
 Structures de données (SD)
Généralités

 Résolution d’un problème : différentes SD possibles

diversement efficaces➔ importance du choix de la SD :
 Réduction de la complexité des algorithmes
 Plus grande fiabilité
 Exemple : complexité des opérations selon les cas :

SD Opération Insertion Recherche Suppression

d’un objet d’un objet d’un objet
Tableau non trié associé à sa taille
n et à son nombre d’éléments p
Tableau trié associé à sa taille n et
à son nombre d’éléments p
 Structures de données (SD)
Généralités

 Résolution d’un problème : différentes SD possibles

diversement efficaces➔ importance du choix de la SD :
 Réduction de la complexité des algorithmes
 Plus grande fiabilité
 Exemple : complexité des opérations selon les cas :

SD Opération Insertion Recherche Suppression

d’un objet d’un objet d’un objet
Tableau non trié associé à sa taille O(1) O(p) O(1)
n et à son nombre d’éléments p
Tableau trié associé à sa taille n et O(p) O(lg(p)) O(p)
à son nombre d’éléments p
 Structures de données (SD)
Type abstrait de données

 Description formelle d’un ensemble d’objets muni

d’opérations applicables à cet ensemble. Elle donne
et à leur comportement
 Elle donne
 lenom et les propriétés du type
 Le profil et le comportement (qu’est-ce qui est fait) de chaque
opération (éventuellement les conditions d’application)
 Elle ne s’intéresse pas à comment c’est fait
 Elle reporte les choix d’implémentation
 Elle est précise, rigoureuse et générique
 Structures de données (SD)
Type abstrait de données

 Définition : Un Type abstrait de données est la donnée

 D’une signature :
 Le nom du type et (éventuellement les autres types utilisés)
 Les profils des différentes opérations (ensembles de départ et
ensembles d’arrivée) :
 Les opérations sans ensemble de départ = les constantes du type

 Deux types d’opérations :

• les générateurs (constructeurs (générateurs de base) et les autres : ont
comme résultat le type cible (décrit)
• les sélecteurs (ou observateurs) : ont au moins un ensemble de départ
qui est du type cible, le résultat étant d’autre type

 D’un ensemble d’axiomes

 Structures de données (SD)
Spécification (algébrique) des SD

 Définition : Une Spécification algébrique est la donnée :

 D’une signature

 D’un ensemble d’axiomes : équations

 En lien avec la signature : définies sur les symboles des opérateurs et
des variables typées de la signature
 décrivant les propriétés (comportements) des opérations les unes par
rapport aux autres
 Parfois assorties de préconditions sur leur exécutions
 Structures de données (SD)
Spécification (algébrique) des SD

 Définition : Une Spécification algébrique est la donnée :

 D’une signature
 D’un ensemble d’axiomes : équations
 Pour définir les axiomes (dans un souci de complétude et de
consistance), il est conseillé :
 D’identifier les constructeurs et exprimer les relations entre eux
 Définir les autres opérateurs par rapport aux constructeurs
 D’ imposer certaines propriétés et définir des opérations par
rapport à celles qui sont déjà définies
 Éléments de syntaxe
Axiomes
Déclaration des variables
Préconditions
Liste des axiomes
 Structures de données (SD)
Ensembles dynamiques d’objets

 Dans ce cours, les SD concernent la représentation d’un

ensemble S dynamique d’objets x. Une clé est associée à
chaque objet
 Deux catégories d’opérations
 Requêtes (observateurs) : retournent informations sur S
 SEARCH(S, k)
 MINIMUM(S)
 MAXIMUM(S)
 SUCCESSOR(S,x)
 PREDECESSOR(S,x)
…
 Transformateurs (et les constructeurs) : Modifient (ou créent) S
 CREATE
 INSERT(S,x)
 DELETE(S,x)
…
 Structures de données (SD)
Spécification (algébrique) des SD : exemples
spéc NAT0 utilise BOOL0
sorte Nat

spéc BOOL0 opérations

0 : → Nat
sorte Bool succ : Nat → Nat
opérations _+_ : Nat Nat → Nat
vrai, faux : → Bool _==_ : Nat Nat → Bool
_ : Bool → Bool _<_ : Nat Nat → Bool
__ , __ : Bool Bool → Bool axiomes m, n, p : Nat
axiomes a, b, c : Bool (n1) 0 + n = n
(b1) vrai = faux (n2) succ(m)+n = succ(m+n)
(b2)   a = a (n3) m + n = n + m
(b3) a  vrai = a (n4) (m + n) + p = n + (m + p)
(b4) a  faux = faux (n5) 0 == 0 = vrai
(b5) (a  b)  c = a  (b  c) (n6) 0 == succ(n) = faux
(b6) a  b = b  a (n7) succ(n) == 0 = faux
(b7) (a  b) = ( a  b) (n8) succ(m) == succ(n) = m==n
fspéc …
fspéc
 Structures de données (SD)
SD linéaires

 Ensembles
 Piles
 Files
 Listes chaînées
 Ensembles
Généralités

 Regroupement d’objets
 de même type
 Chaque objet est unique

 Principales opérations
 Créer_ens() ( )
 Ajouter_elt(E, e) (i)
 Retirer_elt (E, e) (s)
 Est_vide (E)

 Appartient (E, e) ()

 Card(E)
 Union(E, E) (U)
 Intersection (E, E) (∩)
 Ensembles
Spécification : 100 éléments au maximum

spéc ENS0 axiomes E : Ens; x, y : Elements

étend NAT0 (e0) i(i(E, x),y) = i(i(E,y),x)

sorte Ens (e1) x   = faux

opérations (e2) x  i(E , y) = x == y  x  E

 : → Ens (e3) est-vide( ) = vrai
i, s : Ens Elt → Ens (e4) est-vide(i(E,x)) = faux
__ : Elt Ens → Bool
(e5) card () = 0
Est-vide : Ens → Bool
card : Ens → Nat (e6) card (i(E,x)) = card(E) + 1
préconditions E : Ens; x : Elements (e7) s(i(E,x),y) = si x == y alors e sinon i(s(E,y),x)
pré i (E, x) =  (x  E)  card(E) < (e8) min (i(,x)) = x
100 (e9) min(i(i(E, x),y)) = si min(i(E,x))< y alors min(i(E,x))
pré s (E, x) = (x  E) sinon y
pré min (E) =  est-vide(E) fspéc
 Ensembles
implémentation

 Possibilité d’utiliser un tableau associé à un entier n

représentant le nombre d’éléments
 Écrire et analyser les algorithmes correspondant
cette option.
 PILES
Généralités

 Ensemble d’objets à gestion LIFO (Last-In, First Out) :

Eléments entrant et sortant par le haut
 Principales opérations
 Pile_vide() : (()) crée une pile vide
 Est_vide(P) : (STACK_EMPTY) réponse à « P est-elle vide ? »
 Sommet (P) : (TOP) retourne l’élément au sommet de P
 Empiler(P, x) = (PUSH) INSERT : Insertion de x dans S
 Depiler(S) = (POP) DELETE : Extrait et retourne l’élément au
sommet de S
 PILES
Spécification

spéc PILE0 axiomes P : Pile; x : Elt

étend BOOL0 (p1) Est_vide(Pile_vide() ) = vrai

sorte Pile (p2) Est_vide(Empiler(x, P)) = faux

opérations (p3) Sommet (Empiler(x, P)) = x

Pile_vide : → Pile (p4) Depiler(Empiler(x, P)) = (P,x)
Est_vide : Pile → Bool fspéc
Sommet : Pile → Elt
Empiler : Elt, Pile → Pile
Depiler : Pile → (Pile,Elt)
préconditions P : Pile;
pré Sommet (P) = Est_vide(P)
pré Depiler (P) = Est_vide(P)
 PILES
Implémentation

• La propriété de base d’une pile est son sommet. (top)

• L’implémentation peut consister en un tableau associé à un
entier top représentant le sommet.
• Soit S la pile
STACK-EMPTY(S) POP(S)
1 if [Link]=0 1 if STACK-EMPTY(S)
2 return true 2 Error
3 return false 3 else
4 x = S[[Link]]
5 [Link]=[Link]-1
PUSH(S, x)
6 Return x
1 [Link] = [Link] + 1
2 S[[Link]]=x Exercice : Écrire l’algorithme pour TOP(S)
 FILES
Généralités

 Ensemble d’objets à gestion FIFO (First-In, First Out) :

Eléments entrant par la queue et sortant par la tête
 Principales opérations
 File_vide() : (()) crée une file vide
 Est_vide(F) : (QUEUE_EMPTY) réponse à « F est-elle vide ? »
 Tete(F) : (HEAD) Premier élément de F
 Taille(F) : Nombre d’éléments de F
 Queue(F): Dernier élément de F
 enfiler(F, x) = (ENQUEUE) INSERT : Insertion de x dans F
 defiler(F) = (DEQUEUE) DELETE : Extraction d’un élém de F
 FILES
Spécification

spéc FILE0 axiomes F : File; x , y : Elements

étend NAT0 (f1) Est_vide(File_vide()) = vrai

sorte File (f2) Est_vide(enfiler(x, F)) = faux

opérations
File_vide : → File (f3) Tete (Enfiler(x, File_vide()) = x
Est_vide : File → Bool (f4) Tete(Enfiler(x, F)) = Tete(F)
Tete : File → Elt
Taille : File → Nat
Queue : File → Elt (f5) Taille(File_vide()) = 0
Enfiler : Elt, File → File (f6) Taille(Enfiler(x,F)) = Taille(F)+1
Defiler : File → File
(f7) Taille(Defiler(x,F)) = Taille(F)-1
préconditions F : File;
pré Tete (F) = Est_vide(F)
(f8) defiler(enfiler(x, ())) = File_vide()
pré Reste (F) = Est_vide(F)
(f9) defiler(enfiler(x, F)) = enfiler(x, Defiler(F))
pré Defiler (F) = Est_vide(F)
fspéc
 FILES
Implémentation

• Propriétés de base
• head : tête
• tail : nombre d’éléments
• Q : File; x : Element

ENQUEUE(Q,x) DEQUEUE(Q)
1 Q[[Link]] = x 1 x = Q[[Link]]
2 if [Link] == [Link] 2 if [Link] == [Link]
3 [Link] = 1 3 [Link] = 1
4 else
4 else
5 [Link] = [Link] + 1
5 [Link] = [Link]+1
6 Return x
 LISTES CHAINEES
 Le type abstrait « liste » : type de données consistant en
une
 Organisation linéaire d’objets de même type, chaque objet donnant
l’adresse du suivant (éventuellement du précédent)
 Ordre objets déterminé
 Chaque objet peut avoir une clé (int k) et d’autres propriétés
 Quelques opérations (L:liste, x:objet,k:key)
 SEARCH(L, k) : premier élément de L ayant la clé k
 INSERT(L,x) : insertion d’un élément dans L
 En tete
 En queue
 A un endroit précis (liste triée)
 DELETE(L,x) : suppression d’un élément de L
 MINIMUM/MAXIMUM (L)
 LISTES CHAINEES
 Différents types chaînages
 Simple chaînage : liste simplement chaînée :
 chaque objet de la liste contient en plus de la clé et des autres
attributs un pointeur vers l’objet suivant
 Le dernier objet pointe sur NULL

[Link]
5 /

[Link]
9 4 8 5 /

[Link]
9 4 5 /

[Link]
9 4 /

[Link]
4 /
 LISTES CHAINEES
 Différents types chaînages
 Double chaînage : liste doublement chaînée :
 chaque objet de la liste contient (en plus de la clé et des
autres attributs un pointeur vers l’objet suivant et un
pointeur vers l’objet précédent
 Le premier objet a NULL comme précédent
 Le dernier objet a NULL comme suivant

[Link]
/ 5 /

[Link]
/ 9 4 8 5 /

[Link]
/ 9 4 5 /

[Link] / 9 4 /

[Link] / 4 /
 LISTES CHAINEES
 Plus sur les chaînages
 Quelque soit le chaînage utilisé,
 On conserve toujours la tête de liste
 On peut rendre la liste circulaire
 Simple chaînage, le dernier a comme suivant le premier

 Double chaînage : le premier a comme précédent le dernier et le

dernier a comme suivant le premier

[Link]
/ 9 4 8 5 /

[Link] / 4 /
 LISTES CHAINEES
Les algorithmes

LIST-SEARCH(L,k)
1 x = [Link]
2 while x  NIL and [Link]  k
3 x = [Link] LIST-DELETE(L,x)
4 return x 1 if [Link]  NIL
2 [Link] = [Link]
LIST-INSERT(L, x) 3 else
1 [Link] = [Link]
2 if ([Link]  NIL)
4 [Link] = [Link]
3 [Link] = x 5 if [Link]  NIL
4 [Link] = x 6 [Link] = [Link]
5 [Link] = NIL
 LISTES CHAINEES
Les algorithmes : exercices

 Ecrire les autres algorithmes pour la liste doublement

chaînée.
 Ecrire tous les algorithmes pour la liste simplement chaînée.
 Représenter une liste en l’absence de pointeurs et
d’enregistrements. Ecrire les algorithmes correspondant à
cette représentation
 Les arbres
Généralités

 Organisation arborescente des données (hiérarchie)

 Chaque nœud représente un objet
 Un nœud
 a un père (sauf la racine)

 a des fils (sauf les feuilles).

 Deux classes
 Arbres n-aires : au maximum n fils (n>1)

 Arbres sans limitation du nombre de fils

 Arbres
Profondeur et hauteur

 La profondeur d’un nœud c’est le nombre d’arcs entre la

racine et ce nœud
 La hauteur d’un arbre c’est la profondeur de la feuille la plus
éloignée (le nombre d’arcs séparant la racine de la feuille la
plus éloignée)
6
La profondeur de 2 est 1 et celle de 8 est 2
La hauteur de l’arbre est 4
12 4
2

7 8

9 5
 Les arbres
Arbres particuliers

 Arbres dégénérés :
 Arbres presque complets :
 Arbres parfaits :
 Arbres complets :
 Les arbres
Représentation

 Avec des pointeurs

 Arbres n-aires : chaque nœud a un pointeur
 Sur son père
 Sur chacun de ses fils

 Autres arbres : chaque nœud a un pointeur

 Sur son père
 Sur son premier fils
 Sur son frère direct

 Représenter un arbre binaire et un arbre quelconque

 Arbres de recherche
Arbre de recherche

 Il s’agit d’un arbre conçu pour améliorer la complexité des

algorithmes de recherche d’un élément dans un ensemble

 Avec les structures linéaires, on a généralement une

complexité de l’ordre de O(n)
 Les arbres binaires de recherche (BST)
Généralités

 Arbre binaire
 Attributs d’un nœud : key, Left, right, parent (p)
 Satisfait la propriété de recherche dans un arbre : soit A un
BST et x un nœud de A;
 si y est un nœud dans le sous arbre gauche de x, alors [Link] <= [Link]
 si y est un nœud dans le sous arbre droit de x, alors [Link] >= [Link]
2
6
5

5 7
7

2 6 8
5 8

5
 Les arbres binaires de recherche (BST)
Les parcours

 Trois types de parcours. Pour un nœud x donné

 In-orde : fils, x, fils : permet de trier les objet de l’arbre suivant
la clé
 Pré-ordre : x, fils, fils

 Post-ordre : fils, fils, x

 Ecrire les algorithmes des différents parcours

 Les arbres binaires de recherche (BST)
Exercices

 Donner un BST de hauteur 2, puis 3, puis 6 pour

l’ensemble suivant {1, 5, 4, 10, 16, 17, 21}
 Proposer un algorithme non récursif pour le parcours
in-ordre
 Les arbres binaires de recherche
Algorithmes

Pour tous les algorithmes, x est un noeud de l’arbre

TREE-MINIMUM(x)
TREE-SEARCH(x, k) 1 while [Link]  NIL
1 if x == NIL or k == [Link] 2 x = [Link]
2 return x 3 return x
3 if k < [Link]
4 return TREE-SEARCH([Link], k)
5 else
6 return TREE-SEARCH([Link],k) TREE-MAXIMUM(x)
1 while [Link]  NIL
2 x = [Link]
3 return x
 Les arbres binaires de recherche
Algorithmes

SUCCESSOR et PREDESSOR : successeur et le prédécesseur dans l’ordre de la clé.

TREE-MINIMUM(x)
TREE-SUCCESSOR(x) 1 while [Link]  NIL
1 if [Link]  NIL 2 x = [Link]
2 return (TREE-MINIMUM([Link])) 3 return x
3 y = [Link]
4 while y  NIL and x == [Link]
5 x=y
6 y = [Link]
7 return y

Ecrire la procédure PREDECESSOR

 Les arbres binaires de recherche
Algorithmes

INSERT et DELETE : insertion et suppression d’élément dans un BST.

TREE-INSERT(T,z)
1 y = NIL
2 x = [Link]
3 while x  NIL
4 y= x
5 if [Link] < [Link]
6 x = [Link]
7 else
8 x = [Link]
9 z.p = y
10 if y == NIL
11 [Link] = z
12 else
13 if [Link] < [Link]
14 [Link] = z
15 else
16 [Link] = z
 Les arbres binaires de recherche
Algorithmes

INSERT et DELETE : insertion et suppression d’élément dans un BST.

TREE-DELETE(T,z)
1 if [Link] == NIL
TRANSPLANT(T,u,v)
2 TRANSPLANT(T, z, [Link])
1 if u.p == NIL
3 else
2 [Link] = v
4 if [Link] == NIL
3 else
5 TRANSPLANT(T, z, [Link])
4 if u == [Link]
6 else
5 [Link] = v
8 y = TREE-MINIMUM([Link])
6 else
9 if y.p  z
8 [Link] = v
10 TRANSPLANT(T, y, [Link])
9 if v  NIL
11 [Link] = [Link]
11 v.p = u.p
12 [Link].p = y
13 TRANSPLANT(T, z, y)
TREE-MINIMUM(x) 14 [Link] = [Link]
1 while [Link]  NIL 15 [Link].p = y

2 x = [Link]
3 return x
 Les arbres équilibrés
Généralités

 Plus l’ABR est dégénéré, plus le temps de recherche

d’un élément augmente.
 Par exemple la recherche du nœud 5 nécessite deux opérations
dans le premier arbre et 4 dans le second

 Un arbre équilibré est un arbre qui maintient une

profondeur équilibrée entre ses branches
2
6
4

4 7
7

2 6 8
5 8

5
 Les arbres équilibrés AVL
Généralités

 Définition : Un arbre AVL est un ABR équilibré au sens des

hauteurs : pour chaque nœud n, la différence de hauteur
entre son sous-arbre gauche et son sous-arbre droit est au
plus de 1

 Pour maintenir cet équilibre, des opérations de ré-

équilibrage peuvent être nécessaires après une insertion ou
une suppression
 Les arbres équilibrés AVL
Opération équilibrage

 Rotation gauche et rotation droite

y x
RIGHT-ROTATE(T,y)

x  
y
LEFT-ROTATE(T,x)


 
 Les arbres équilibrés AVL
Opération équilibrage

 Rotation simple après insertion successives

 Les arbres équilibrés AVL
Opération équilibrage

 Double rotation : x est le nœud en cause.

 Cas1 : hauteur(fg(x))-hauteur(fd(x)) = 2
hauteur(fg(fg(x)))-hauteur(fd(fg(x))) = -1
Rotation gauche(fg(x)) + rotation droite(x)
Exemple : après insertion de g
 Les arbres équilibrés AVL
Opération équilibrage

 Double rotation : x est le nœud en cause.

 Cas2 : hauteur(fg(x))-hauteur(fd(x)) = -2 et
hauteur(fg(fd(x)))-hauteur(fd(fd(x))) = 1
Rotation droite(fd(x)) + rotation gauche(x)
Exemple : après insertion de g
d

b i

c f k + g
a

e h j l

b i

f k
a c

e h j l

g
 Les arbres bicolores (Red-Black trees)
Généralités

 Arbre binaire de recherche

 Équilibré (balanced) par rapport à la hauteur
 Attributs d’un nœud : key, left, right, parent (p), color.
 Gestion des effets de bord : nœud sentinelle noir
 parent de la racine

 fils manquants des nœuds

 Les arbres bicolores (Red-Black trees)
Généralités

 Satisfait les propriétés de bicoloration

 Tout nœud est noir ou rouge

 La racine de l’arbre est noir

 Toute feuille (NIL) est noir

 Si un nœud est rouge, ses deux fils sont noirs

 Pour chaque nœud x, les chemins de x aux feuilles contiennent le

même nombre de nœuds noirs (hauteur black-height de x - sans
compter x -)
 Les arbres bicolores (Red-Black trees)
Généralités

 Opérations
 Toutes les opérations des BST

 INSERT et DELETE modifient l’arbre

 Recoloration nécessaire
 Modification de la structure des pointeurs

 Rotation qui permet de modifier la structure des pointeurs

 LEFT-ROTATE
 RIGHT-ROTATE
 Les arbres bicolores (Red-Black trees)
Représentation

26

41
17

14 21 30 47

10 16 19 23 28 38

20 35 39
7 12 15

On peut représenter les liens engageant [Link] : arbre complet

 Les arbres bicolores (Red-Black trees)
Algorithmes : Rotation
LEFT-ROTATE (RIGHT-ROTATE) appelé sur les nœuds ayant un fils droit (gauche)

LEFT-ROTATE(T,x)
1 y = [Link]
2 [Link] = [Link]
3 if [Link]  [Link]
4 [Link].p = x
5 y.p = x.p
6 if x.p == [Link]
7 [Link] = y y
x
RIGHT-ROTATE(T,y)
8 else
9 if x==[Link] x
 
y
10 [Link] = y LEFT-ROTATE(T,x)

11 else  


12 [Link] = y
13 [Link] = x
14 x.p = y
 Les arbres bicolores (Red-Black trees)
Algorithmes : Recoloration après insertion
RB-INSERT-FIXUP(T,z)
1 while [Link] == RED Objectif : conserver le caractère équilibré et
2 if z.p == [Link] les propriétés de bicoloration
3 y = [Link]
4 if [Link] == RED
Insertion du nœud 4
5 [Link] = BLACK
11
6 [Link] = BLACK
2 14
7 [Link] = RED
7 15
8 z = z.p.p 1
5 8
9 else
z
10 if z==[Link] 4

11 z=z.p
12 LEFT-ROTATE(T,z)
13 [Link] = BLACK
14 [Link] = RED 11
2 14
15 RIGHT-ROTATE(T,z.p.p)
z7
16 else 1
15

17 (idem au ‘if’ avec inversion de left et 5 8

right) 4
18 [Link] = BLACK
 Les arbres bicolores (Red-Black trees)
Exercices

 Poursuivre la simulation de l’exécution de RB-

INSERT-FIXUP sur l’arbre donné en exemple
 Dessiner un BST complet de hauteur 3 à partir de clés
{1,2…, 15}. Ajouter les feuilles NIL et colorer les
nœuds de sorte à avoir un Red-Black-Tree avec un
black-height de 3
 Dessiner le Red-Black-Tree issu de l’insertion de la clé
36 dans l’arbre donné en exemple (page 93)
 Graphes
Définitions

 Un graphe G = (V, E) est la donnée d’un couple (V, E)

 V est un ensemble de sommets

 E est une relation binaire sur V dont les éléments sont :

 Des arcs : graphe orienté
 Des arêtes : graphe non orienté

 Graphe orienté simple : aucun arc (u, v) avec u = v

 Le sommet v est adjacent au sommet u si (u,v)E
 Graphes
Définitions

 Chemin de longueur k, de u à u’, dans un graphe G =

(V, E) = séquence  v0, …., vk  de sommets telle que
 u = v0
 u’ = vk
 (vi-1, vi)  E
 Chemin simple : tous ses sommets sont distincts
 Longueur d’un chemin : le nombre d’arcs (arêtes)
 Sous-chemin de p =  v0, …., vk  = sous-séquence
contigüe des sommets de p
 Graphes
Définitions

 Graphe orienté
 Cycle : chemin  v0, …., vk  dans un graphe orienté tel que v0 = vk

 Cycle simple :  v1, …., vk  sont distincts

 Graphe sans cycle = graphe acyclique

 Deux chemins p =  v0, …., vk -1, vk  et p’ =  v’0, …., v’k -1, v’k 
forment le même cycle s’il existe j tel que v’i = v(i+j)mod k pour i =
0, …, k-1
 Graphe fortement connecté : étant donnée une paire de
sommets, l’un est atteignable à partir de l’autre et vice versa
 Graphes
Définitions

 Graphe non orienté

 Cycle : chemin  v0, …., vk  tel que k > 0, v0 = vk et toutes les
arêtes sont différentes
 Cycle simple :  v1, …., vk  sont distincts

 Graphe sans cycle = graphe acyclique

 Un graphe connexe : graphe tel que chaque sommet est

atteignable à partir de tous les autres sommets.
 Composante connexe = classe d’équivalences des sommets par
rapport à leur atteignabilité
 Graphes
Représentations

 Graphes : deux représentations standards

 Listes d’adjacences
 Tableau adj de |V| entrées dont chaque entrée adj[u]
 correspond à un sommet
 contient la liste des sommets adjacents à u
 Matrices d’adjacences
 Les sommets sont numérotés de 1 à |V|
 Matrice carrée A = (aij) de dimension | V | tq
 aij = 1 si (i, j)  E
 aij = 0 sinon

 Attributs sommets et arcs (arêtes) : utilisation du « . »

 Pour les sommets : u.a avec u un sommet
 Pour les arcs (arêtes) : (u, v).a avec (u, v) un arc (arête)
 Graphes
Algorithmes classiques

 Parcours
 Recherche
 Des plus courts chemins

 Des composantes connexes

 Algorithmes de parcours
En largeur d’abord

 Paramètres : un graphe G et un sommet s

 explore systématiquement les sommets de G
 Découvrir les sommets atteignables à partir de s, et pour chaque
sommet atteignable, calcule le plus court chemin
 Produire un arbre de parcours en largeur d’abord avec comme
racine s
 Utilise les attributs
 couleur (color) : WHITE, GRAY, BLACK

 distance (d)

 prédécesseur ()
 Algorithmes de parcours
En largeur d’abord : algorithme

BFS (G, s)
1 for each vertex u  G – {s}
2 [Link] = WHITE
3 u.d = 
4 u. = nil
6 [Link] = GRAY
7 s.  = NIL
7’ s.d = 0
8 Q=
9 ENQUEUE(Q,s)
10 while Q  
11 u = DEQUEUE(Q)
12 for each v  [Link][u]
13 if [Link] = WHITE
14 [Link] = GRAY
15 v.d=u.d+1
16 v. = u
17 ENQUEUE(Q, v)
18 [Link] = BLACK
 Algorithmes de parcours
En profondeur d’abord

 Paramètres : un graphe G
 explore tous les arcs (arêtes) de G en partant du sommet le
plus récemment découvert v avant d’explorer les arcs
partant du sommet à partir duquel v a été découvert
 Produit une forêt d’arbres issus de G
 Utilise les attributs
 couleur (color) : white, gray, black
 Instants
 De première découverte de v (d)
 De fin s’exploration de la liste d’adjacence de v (f)
 prédécesseur ()
 Algorithmes de parcours
En profondeur d’abord : algorithme

DFS (G) DFS-VISIT (G, u)

1 for each vertex u  G.V 1 time = time +1
2 [Link] = WHITE 2 u.d = time
3 u. = nil 3 [Link] = GRAY
4 time = 0 4 for each v  [Link][u]
5 for each vertex u  G.V 5 if [Link] = WHITE
6 if [Link] = WHITE 6 v. = u
7 DFS-VISIT (G,u) 7 DFS-VISIT(G,v)
8 [Link] = BLACK
9 time = time + 1
10 u.f = time
 Algorithmes de recherche dans un graphe
En profondeur d’abord : application : Tri topologique

 Entrée : Graphe G = (V, E) orienté sans cycle

 Problème à résoudre : Etablir un ordre entre tous les
sommets de G tel que si (u,v)  E, u apparaisse avant v
dans l’ordre établi
 Permet d’établir des précédences entre plusieurs
événements
 Algorithmes de recherche dans un graphe
En profondeur d’abord : application : Tri topologique

 Exemple
 Soit le graphe G = (V, E) suivant concernant la manière dont M.
B procède à son habillement chaque matin
 V = {ceinture, chaussettes, chaussures, chemise, cravate, gilet
montre, pantalon, sous-vêtement}
 E = {(ceinture, gilet), (chaussettes, chaussures), (chemise,
ceinture), (chemise, cravate), (cravate, gilet), (pantalon,
ceinture), (pantalon, chaussures), (sous-vêtements, chaussures),
(sous-vêtements, pantalons)
 Algorithmes de recherche dans un graphe
En profondeur d’abord : application : Tri topologique

 Algorithme ?
 Algorithmes de recherche dans un graphe
Profondeur d’abord : Composante fortement connectée

 Entrée : Graphe G = (V, E) orienté

 Problème à résoudre : Décomposer G en ses
composantes fortement connectées
 Utilise le transposé de G, GT = (V, ET) avec ET = {(v,u)
tels que (u, v)  E}
 Algorithmes de recherche dans un graphe
Profondeur d’abord : Composante fortement connectée

 Algorithme
 STRONGLY-CONNECTED-COMPONENTS(G)
1 DFS(G)
2 DETERMINER GT
3 DFS (GT) en considérant les sommets u dans l’ordre
décroissant de u.f
4 Afficher les nœuds de chaque arbre de la forêt comme les
différentes composantes fortement connectées
 Recherche de Plus courts chemins (PCC)
Généralités

 Entrée : Graphe orienté et étiqueté G = (V, E) auquel

est associé une fonction d’étiquetage w = E → R
associant aux éléments de E des poids

 Poids d’un chemin p = v0, v1, …, vk :

w(p) = w(v0 v1) + … + w(vk-1, vk)

 Poids du plus court chemin de u à v :

(u,v) = min (w(p) : p = u, …, v) ou  si pas de chemin
 Recherche de Plus courts chemins (PCC)
Généralités

 Problèmes à résoudre : on cherche un des chemins les

plus courts :
 Une source donnée
 Une destination donnée
 Une source et une destination données
 Toutes les sources et toutes les destinations
 PCC avec une source donné
Sous-structure optimale

 Lemme : Les sous-chemins d’un PCC sont des PCC

Soit un graphe orienté G = (V, E) avec w : E→R une fonction d’
étiquetage des arcs,
si p = v0, v1, …, vk : est un PCC de vo à vk, and pij = vi, …, vj un
sous-chemin de p (0<=i<=j<=k), alors pij est un PCC de vi à vj
 PCC avec une source donné
Cycles, poids négatifs

 Pour un chemin de s à v contenant un cycle de poids

négatif (v,d) = -

 Un chemin de s à v contenant un cycle ne peut être un

PCC ➔ longueur maximale d’un chemin est |V|-1
 PCC avec une source donné
Représentation des PCC

 Pour un chemin, on s’intéresse au

 Au poids

 Aux sommets le composant ➔ maintien pour chaque sommet de

son prédécesseur ()
 Les algorithmes présentés
 construisent le sous-graphe G = (V , E) des prédécesseurs avec
 V = {v V : v.  NIL}{s}
 E = {(v., v)  E : v  V - {s}}

 Utilisent la technique de « relaxation » : pour chaque sommet v

V on maintient l’attribut v.d
 PCC avec une source donné
Algorithmes

Algorithme de BELLMAN-FORD
INITIALISE-SINGLE-SOURCE(G,s)
BELLMAN-FORD(G,w,s)
1 for each vertex v  G.
1 INITIALISE-SINGLE-SOURCE(G,s)
2 v.d = 
2 for i = 1 to |G.V| -1
3 v. = NIL
3 for each edge (u,v)  G.E
4 s.d = 0
4 RELAX (u, v, w)
5 for each edge (u,v)  G.E
6 if v.d > u.d + w(u,v)
7 return false
8 return true RELAX(u, v, w)
1 if v.d > u.d + w(u,v)
2 v.d = u.d + w(u,v)
3 v. = u
 PCC avec une source donné
Algorithmes

Source donnée dans un graphe acyclique

Algorithme
DAG-SHORTEST-PATHS(G,w,s)
1 TRI TOPOLOGIQUE SOMMETS
2 INITIALISE-SINGLE-SOURCE(G,s)
3 for each vertex u (ordre topologique)
4 for each vertex v  [Link][u]
5 RELAX (u, v, w)

Théorème : si un graphe G = (V, E) acyclique a comme sommet source s alors a la fin

de l’exécution de la procédure DAG-SHORTEST-PATHS, v.d = (s, v) for tout v de
V, et le sous-graphe des prédécesseurs est un arbre de PCC.
 PCC avec une source donné
Algorithmes
Algorithme de DIJKSTRA
DIJKSTRA(G,w,s)
1 INITIALISE-SINGLE-SOURCE(G,s)
2 S=
3 Q = G.V
4 While Q  
5 u = EXTRACT-MIN(Q)
6 S = S  {u}
7 for each vertex v  [Link][u]
8 RELAX(u, v, w)

Théorème : L’algorithme de DIJKSTRA exécuté sur

 un graphe orienté G = (V, E) étiqueté par les poids des arcs avec la fonction non
négative w
 Une source s, termine avec u.d = (s, u) pour tout sommet v de V
 TABLES DE HACHAGE
Généralités

 Structures de données permettant une

implémentation efficace des dictionnaires dans
lesquels les opérations autorisées (souhaitées) sont :
− Insérer un élément
− Rechercher un élément
− Supprimer un élément

 Généralisation de la notion de tableau ordinaire

(dans lequel l’indice de rangement d’un objet est
calculé à partir de la clé de l’objet.)

 Objectif : améliorer les temps moyens des

opérations
 TABLES DE HACHAGE
Généralités

 Plusieurs clés (objets) pouvant donner le même indice, on

peut avoir des situations de « collision » qui doivent être
gérées
 Définition (Univers des clés) : Ensemble des clés possibles.
Les clés des objets (clés réelles) sont prises dans cet univers

 Deux types de tables de hachage

− Tables à adressage direct (Univers raisonnablement petit, sans

doublons au niveau des clés utilisées)

− Tables de hachage avec fonction de hachage (Univers très grand)

 TABLES DE HACHAGE
Tables à adressage direct

 Applicable lorsque

− l’Univers des clés est raisonnablement petit (m clés), pour

qu’il soit possible d’allouer un tableau possédant une position
unique pour chaque clé
− Les clés sont des entiers compris entre 1 et m
 Mise en œuvre
− Définition d’un tableau de taille le nombre de clés de
l’Univers
− l’indice i du tableau contient :
⚫ un pointeur vers l’objet de clé i si un tel objet existe
⚫ Nil sinon
 TABLES DE HACHAGE
(Vraies) tables de hachage

 Applicable lorsque l’Univers des clés U est grand

− pour qu’il soit difficile (ou impossible) de gérer une

table d’une telle taille
− Et l’ensemble K des clés réelles peut être beaucoup plus
petit que U de telle sorte qu’il est plus coûteux (en
espace) d’utiliser une table à adressage direct
 Mise en œuvre
− Définition d’un tableau de taille m < n la taille de
l’Univers U
− l’objet de clé k est haché dans l’alvéole (l’entrée) h(k) du
tableau, h étant une fonction dite de hachage qui associe
à chaque élément de U un nombre compris entre 0 et m-
1
 TABLES DE HACHAGE
(Vraies) tables de hachage

 Collisions et leur gestion

− Lorsque plusieurs clés sont hachées vers la même
alvéole, on parle de collision.
− La gestion des collisions
⚫ consiste à assurer le stockage en toute sécurité de tous les
objets hachant vers la même alvéole.
⚫ Technique : par chaînage : consiste à placer dans une
liste chaînée tous les objets hachés vers une même alvéole
et à stocker dans cette alvéole un pointeur sur la tête de
cette liste.
 TABLES DE HACHAGE
(Vraies) tables de hachage

 Les fonctions de hachage

− Influencent directement le temps d’exécution des
opérations de dictionnaire.
− Une bonne fonction de hachage doit être conçue de
sorte à permettre une association globalement
uniforme des objets aux m alvéoles.
− La connaissance de la distribution des clés peut
aider à créer une fonction efficace
 TABLES DE HACHAGE
(Vraies) tables de hachage
 Exemples de fonctions de hachage (h)

− Méthode de la division : h(k) = k mod m

− Méthode de la multiplication : deux étapes
⚫ Multiplication de k par une constante A avec 0<A<1. On obtient
kA
⚫ h(k) sera égale à la partie entière de la multiplication de la partie
décimale de kA par m : h(k) = E(m(kA – E(kA))) avec E(x) =
partie entière de x

− Hachage universel : sélectionner la fonction de hachage au

hasard à partir d’une classe de fonctions conçue
auparavant.
 TABLES DE HACHAGE
(Vraies) tables de hachage

 Hachages pour éviter les collisions

− Adressage ouvert
⚫ Pas de pointeurs : les éléments sont conservés
dans la table de hachage elle-même
⚫ La fonction de hachage prend un second argument
qui est un nombre compris entre 0 et m-1
⚫ Pour chaque objet à caser, on prendra la première
alvéole vide obtenue avec h(k,i) i allant de 0 à m-1.
Si aucune alvéole n’est vide, l’objet n’est pas rangé
 TABLES DE HACHAGE
(Vraies) tables de hachage
 Hachages pour éviter les collisions

− hachage parfait

⚫ Un hachage est parfait si le nombre d’accès mémoire requis pour faire

une recherche est dans le pire cas O(1)

⚫ L’idée pour y parvenir est d’utiliser un hachage à deux niveaux,

chaque niveau utilisant un hachage universel : pour une clé k
donnée :

− Une première fonction de hachage h1 va la hacher vers une alvéole i de la

première table de hachage dont chaque alvéole contient un pointeur sur
une deuxième table de hachage Si.

− Une deuxième fonction de hachage h2 va hacher k vers une alvéole de Si

 TABLES DE HACHAGE
Tables à adressage direct

 Exercice : écrire les algorithmes correspondant aux

opérations de dictionnaire dans le cas où on a affaire à

− une table à adressage direct.

− Un adressage ouvert