Algorithmes et structures de données

avancées

Mastère Infotronique

Dr. Nour Brinis

nour.brinis@ensi-uma.tn

1/80
 Plan du cours

• Structures de données élémentaires

• Complexité

• La récursivité et le paradigme « diviser pour régner »

• Algorithmes de tri

• Programmation dynamique

• Algorithmes gloutons

• NP-complétude

• Heuristiques: algorithmes d’approximation

2/80
 Chapitre 1

Structures de données élémentaires

3/80
 Structures de données élémentaires
• Il existe plusieurs manières de représenter la notion
d’ensemble
• Il n’y a pas une représentation « meilleure » que les
autres dans l’absolu
– La meilleure représentation sera celle qui permettra de
concevoir l’algorithme de moindre complexité
• Chaque élément de ces ensembles pourra comporter
plusieurs champs
– Les champs peuvent être consultés des lors qu’on
possède une référence sur cet élément une référence
4/80
 Structures de données élémentaires

• Les ensembles dynamiques supportent toute une série

d’opérations
• Etant donné une liste s:
– Recherche(s,k): étant donné un ensemble s et une clé k, le résultat
de cette requête est un pointeur sur un élément de s de clé k, s’il en
existe un, sinon retourne NIL
– Insertion(s,x): insère dans l’ensemble s, l’élément pointé par x
– Suppression(s,x): supprime de l’ensemble s, l’élément pointé par
x

5/80
Structures de données élémentaires

• Liste chainée

• Piles

• Files

• Arbres

• Tables de hachage

6/80
Listes chainées

7/80
 Listes chainées
◼ Une liste chaînée est une structure de données dont les
éléments sont arrangés linéairement
◼ l'ordre linéaire étant donné par des pointeurs sur les

éléments

◼ Un élément d'une liste chaînée est un enregistrement

contenant
◼ un champ clé,

◼ un champ successeur consistant en un pointeur sur

l'élément suivant dans la liste
Si le champ successeur d'un élément vaut NIL,
l'élément est le dernier élément de la liste, appelé
également queue de la liste

8/80
 Listes chainées
◼ Un pointeur TETE(L) est associé à une liste chaînée L
◼ il pointe sur le premier élément de la liste

◼ Si une liste chaînée L est telle que TETE(L)=NIL alors la

liste est vide

9/80
 Listes chaînées
Liste: Sa représentation réelle en mémoire

10/80
Listes chainées

11/80
 Listes chainées
◼ Une liste chaînée peut prendre plusieurs formes
◼ Liste doublement chainée: en plus du champ successeur,

chaque élément contient un champ prédécesseur (pointeur

sur l’élément précèdent dans la liste)
◼ Si le champ prédécesseur vaut NIL, cet élément n’a pas

de prédécesseur ➔ il est donc le premier élément ou la

tête de la liste
◼ Le dernier élément d’une liste doublement chainée est

pointé par un pointeur Queue(L)

◼ Une liste qui n’est pas doublement chainée est dite

simplement chainée
12/80
Listes chainées

13/80
 Listes chainées
◼ Liste triée ou non triée: suivant que l’ordre linéaire des
éléments de la liste correspond ou non à l’ordre linéaire
des clés de ces éléments

◼ Liste circulaire: si le champ prédécesseur de la tête de la

liste pointe sur la queue, et si le champ successeur de la
queue pointe sur la tête➔ la liste est donc vue comme un
anneau

14/80
 Listes chainées
Algorithmes de manipulation des listes chaînées

◼ L la liste chainée
◼ TETE(L) pointeur sur le premier élément de la liste
◼ QUEUE(L) pointeur sur le dernier élément de la liste

◼ Si p est un pointeur sur un élément de la liste L:

◼ cle(p) retourne l’ élément pointé par p

◼ Successeur(p) retourne un pointeur sur l’élément

suivant

15/80
28/80
 Listes chainées

Déclaration d’une liste simplement chainée:

Types
Cellule = Struct
cle : Entier
successeur : ^Cellule
FinStruct
Variables
tete : ^Cellule

16/80
 Listes chainées
◼ Recherche: RECHERCHE-LISTE(L,k) retourne un pointeur
sur le premier élément de L de clé k, si cet élément existe, sinon
retourne NIL

RECHERCHE-LISTE(L,k){
pTETE(L);
tant que(p!=NIL et clé(p)!=k)
Psuccesseur(p);
retourner p;
}

Cet algorithme manipule aussi bien les listes simplement que

doublement chainées

17/80
 Listes chainées

◼ Insertion: INSERTION-LISTE(L,X) ajoute, en tête de la liste

L, l’élément pointé par X

INSERTION-LISTE(L,X){
successeur(x)TETE(L);
TETE(L) ) x;
}

18/80
 Listes chainées
◼ Suppression: SUPPRESSION-LISTE(L,X) supprime de la
liste L son élément pointé par X
SUPPRESSION-LISTE(L,X){
Si x=TETE(L) alors TETE(L) ) successeur(x)
sinon{
y  TETE(L);
tant que successeur(y)!=x faire
y  successeur(y);
fin tant que
successeur(y)  successeur(x);
}
}

◼ Si on souhaite supprimer un élément dont on ne connait que

la clé K, il suffit de récupérer un pointeur sur cet élément par
un simple appel à RECHERCHE-LISTE(L,k)
19/80
Piles

20/80
 Piles

Définition
◼ Une pile est une structure de données mettant en
œuvre le principe « dernier entré premier sorti »

◼ LIFO : Last In First Out

21/80
 Piles
Applications

• Dans un navigateur web, une pile sert à mémoriser les pages

Web visitées. L'adresse de chaque nouvelle page visitée est
empilée et l'utilisateur dépile l'adresse de la page précédente en
cliquant le bouton « Afficher la page précédente ».
• L'évaluation des expressions mathématiques en notation post-
fixée (ou polonaise inverse) utilise une pile.
• La fonction « Annuler la frappe » (en anglais « Undo ») d'un
traitement de texte mémorise les modifications apportées au texte
dans une pile.
• Un algorithme de recherche en profondeur utilise une pile pour
mémoriser les nœuds visités.
22/80
 Piles

• Une pile P peut être implémentée par un tableau

• La seule difficulté dans cette implémentation est la

gestion des débordements de pile
• Dépiler sur une pile vide
• Empiler sur un tableau codant la pile qui est déjà plein

• Ce problème n’apparait pas quand on implémente les

piles au moyen d’une structure de données dont la taille
n’est pas fixée à priori (comme une liste chainée)

23/80
 Piles

• Implémentation d’une pile au moyen d’un tableau:

• On note:
• sommet(P) l’indice du tableau contenant la tête de la pile initialisé à
-1 ➔ pile vide
• longeur(P) taille de la pile
• PILE-VIDE(P) retourne vrai si pile vide sinon retourne faux
• EMPILER(P,x) empile l’élement x dans la pile
• DEPILER(P) dépile l’élement x de la pile

24/80
 Piles

• Implémentation d’une pile au moyen d’un tableau:

PILE-VIDE(P){
Si sommet(P)==-1
alors retourner VRAI
sinon retourner FAUX
}

25/80
 Piles

EMPILER(P,x){
Si sommet(P)==longueur(P)-1
alors erreur (débordement positif)
sinon { sommet(P)sommet(P)+1
P[sommet(P)]x
}
}
DEPILER(P){
Si PILE-VIDE(P)
alors erreur (débordement négatif )
sinon { sommet(P)sommet(P)-1
retourner P[sommet(P)+1]
}
}

26/80
 Piles

• Implémentation d’une pile au moyen d’un liste:

on mémorise des informations qui devront être traitées dans
l’ordre inverse de leur entrée.

Types
Pile = ^Cellule
Cellule = Struct
Elem : Entier
Suiv : Pile
FinStruct
Variables
P : Pile

27/80
Procédure Empiler(x :entier, P :Pile)
Variables
Q : Pile
Début
Allouer(Q)
Q^.Elem  x
Q^.Suiv  P
P Q
Fin

Procédure Dépiler(x :entier, P :Pile)

Variables
Q : Pile
Début
Si NON(Pile_Vide(P)) alors
x  P^.Elem
QP
P  P^.Suiv
Libérer(Q)
Sinon
Ecrire(« Impossible la pile est vide »)
Fin
Files

29/80
 Files

Définition (file) :
◼ Une file est une structure de données mettant en œuvre le
principe « premier entré premier sorti »
◼ FIFO : First In First Out
◼ Une file se comporte comme une file d’attente de la vie
courante

30/80
 Files
Applications

• En général, on utilise des files pour mémoriser temporairement des transactions qui
doivent attendre pour être traitées.
• Les serveurs d'impression, qui doivent traiter les requêtes dans l'ordre dans lequel
elles arrivent, et les insèrent dans une file d'attente (ou une queue).
• Certains moteurs multitâches, dans un système d'exploitation, qui doivent accorder du
temps- machine à chaque tâche, sans en privilégier aucune.
• Un algorithme de parcours en largeur utilise une file pour mémoriser les nœuds visités.

31/80
 Files

• Une file F peut être implémentée par un tableau

• La même difficulté que l’implémentation des piles par

des tableaux: la gestion des débordements de file
• Suppression sur une file vide
• Insertion dans une file pleine

• Ce problème n’apparait pas quand on implémente les

files au moyen d’une structure de données de taille
dynamique

32/80
 Files

• Une file F peut être implémentée par un tableau

circulaire
• F est caractérisée par :
◼ Un pointeur tete(F) qui pointe vers la tête de la

file (l’élément le plus anciennement inséré)

◼ Un pointeur queue(F) qui pointe vers la première

place libre, où se fera la prochaine insertion

éventuelle d’un élément

33/80
 Files

◼ n la taille du tableau implémentant la file F

◼ Initialement : tete(F) = -1
queue(F) = 0

34/80
 Files
FILE-VIDE(F){
si tete(F)==-1 alors
retourner VRAI
sinon
retourner FAUX
}

INSERTION(F,x){
si (queue(F) (modulo n) ==tete(F))
alors erreur (débordement positif)
sinon{
F[queue(F)]=x
Si tete(F)=-1alors
Tete(F)=queue(F)
queue(F)=(queue(F)+1) (modulo n)
}
35/80
}
 Files

SUPPRESSION(F){
si FILE-VIDE(F)
alors erreur (débordement négatif)
sinon {
X = F[tete(F)];
tete(F)=(tete(F)+1) modulo n;
Si tete(F) = queue(F)
tete(F) = -1
retourner X;
}
}

36/80
Exemple

37/80
 Files

• Implémentation d’une file au moyen d’une liste:

Une File est une liste chainée dont les contraintes d’accès sont définies
comme suit :
• On ne peut ajouter un élément qu’en dernier rang de la liste.
• On ne peut supprimer que le premier élément.

Types
File : ^cellule
Cellule = Struct
Elem : Entier
Suiv : File
FinStruct
Variables F : File

38/80
 Procédure Initialiser(F :File)
Début
F.Tête Nil
F.Queue Nil
Fin

Procédure Ajouter(x :entier, F :File) Procédure Extraire(x :entier, F :File)

Variables Variables
P : Liste P : Liste
Début Début
Allouer(P) Si (F.Tête=Nil) alors
P^.Elem x Ecrire(« Impossible la pile est
P^.Suiv Nil vide »)
Si(F.Queue ≠ Nil)alors Sinon
F.Queue^.SuivP P F.Tête
Sinon x F.Tête^.Elem
F.TêteP F.Tête  F.Tête^.Suiv
FinSi Libérer(P)
F.Queue  P FinSi
Fin Fin

39/80
Arbres

40/80
 Arbres

• Un arbre est une structure de données

organisées de façon hiérarchique, à partir d’un
nœud distingué appelé racine
• Un arbre est un ensemble de Nœuds, reliés par
des Arêtes. Entre deux nœuds, il existe toujours
un seul chemin. noeuds

arêtes 41/80
 Arbres

• Chaque arbre a une racine. Une fois la racine définie, tous

les nœuds admettent un niveau.
• Les arbres ont des noeuds internes et des feuilles (nœuds
externes). Chaque noeud (à l’exception de la racine) a
un parent et admet zéro ou plusieurs fils.
racine
niveau 0
niveau 1 nœuds internes

niveau 2
parent
et
niveau 3
fils
feuilles 42/80
48/80
 Arbres

◼ Nœuds avec fils : nœuds internes

◼ Sous-arbre de racine x: l'arbre composé des
descendants de x, enraciné en x
◼ Degré d'un nœud : nombre de fils
◼ Profondeur d'un nœud = longueur du chemin entre la racine et ce
nœud
◼ Hauteur d'un arbre = profondeur maximale de ses nœuds

43/80
 Arbre binaire
◼ Arbre binaire: structure de donnée qui peut être définie
récursivement de la façon suivante:
◼ Soit vide

◼ Soit composée de:

◼ une racine portant une étiquette clé;

◼ une paire d’arbres binaires

◼ le sous-arbre gauche (arbre binaire) ;

◼ le sous-arbre droit (arbre binaire),

44/80
 Arbres binaires

• Un Arbre Binaire est un arbre où chaque nœud

admet au plus 2 fils.

45/80
 Arbres binaires

• Nœuds d’un arbre contiennent des clés (mots, nombres,

etc)
14

10 16

8 12 15 18

7 9 11 13

46/80
 Arbre binaire de recherche

• Un arbre binaire de recherche (ABR): structure de donnée

qui permet de représenter un ensemble de valeurs si l’on
dispose d’une relation d’ordre sur ces valeurs.

47/80
 Arbre binaire de recherche

• ABR est un arbre avec la propriété suivante :

Clé(filsGauche) ≤ Clé(parent) < Clé(filsDroit)

◼ Un arbre binaire de recherche est un arbre binaire tel que

pour tout nœud x :
◼ Tous les nœuds y du sous-arbre gauche de x vérifient

clé(y)≤clé(x)

◼ Tous les nœuds y du sous-arbre droit de x vérifient

clé(y)>clé(x)

48/80
 Arbre binaire de recherche
Exemple

49/80
 Arbre binaire de recherche
• Pour accéder à la clé la plus petite dans un ABR il suffit de descendre sur le
fils gauche autant que possible ➔ le dernier nœud visité, qui n’a pas de
fils gauche, porte la valeur la plus petite de l’arbre.

50/80
 Arbre binaire de recherche
• Pour accéder à la clé la plus grande dans un ABR il suffit de descendre sur
le fils droit autant que possible ➔ le dernier nœud visité, qui n’a pas de
fils droit, porte la valeur la plus grande de l’arbre.

51/80
 Arbre binaire de recherche

• Les opérations caractéristiques sur les arbres binaires de

recherche sont
– Parcours de l’arbre (infixe, prefixe, postfixe)
– Recherche d’une valeur;
– Insertion,
– Suppression,
– Minimum
– Maximum

52/80
Arbres Binaires: représentation par
pointeurs

Types
Arbre = ^Noeud
Noeud = Struct
clé : Entier
sa-gauche : Arbre
sa-droit : Arbre
FinStruct
Variables
Racine : Arbre

53 53/80
59/80
 Parcours infixe
Parcours Infixe d’un arbre est décrit réursivement :

• Visiter le sous-arbre gauche en Infixe

• Visiter la racine
• Visiter le sous-arbre droit en Infixe

54 54/80
59/80
 ABR: parcours infixe

Exemple:

Infixe visites :
14
(8)
(10)
10 16 (11)
(14)
(15)
8 11 15 18 (16)
(18)

55 59/80
55/80
 ABR: parcours infixe
Parcours infixe d’un arbre binaire de recherche permet l'affichage des
clés des nœuds par ordre croissant
Infixe(A) {
Si A≠NIL
{
Infixe(sa-gauche(A));
Afficher(cle(A));
Infixe(sa-droit(A));
}
}

62/80
56/80
 ABR : Rechercher un élément

Soit un ABR :

G D

Problème: rechercher un noeud avec une clé x ?

63 63/80
57/80
 ABR : Rechercher un élément

rechercher(racine, x) Exemple:
comparer x à la clé de la racine:
14
- si x == clé retourner A
- si x < clé => chercher dans G
10 16
- si x > clé => chercher dans D
8 11 15
chercher de la même manière
dans G ou D

x=8 (oui) x=17 (non)

58/80 64
 ABR : Rechercher un élément
• Recherche d'un élément : rechercher(A,k)
◼ retourne le pointeur sur un nœud dont la clé est k,

si un tel nœud existe

◼ sinon elle retourne le pointeur NIL

rechercher(A,k){
si (A==NIL ou cle(A)==k)
retourner A
sinon si (k≤cle(A))
rechercher(sa-gauche(A),k)
sinon
rechercher(sa-droit(A),k)
59/80
65/80
}
 ABR : Insertion d’un élément

• On veut insérer un élément de clé k dans un ABR

• Idee : comme avec la fonction rechercher(A,k), on trouve la
place pour v (enfant gauche ou droit manquant)

66/80
60/80
 ABR : Insertion d’un élément

Exemple: ajouter C A B L M (dans l’ordre!)

1) Ajouter C 2) ajouter A 3) ajouter B C

C
C A
A
B

4) Ajouter L C 5) Ajouter M
C

A L
A L

B
B M 61/80 67
 ABR : Insertion d’un élément

L’ABR est-il unique pour une séquence de lettres

AB C LM ?
NON! différentes séquences donnent différents
ABR

Ajout de : A B C L M Ajout de : C A B L M

A
C
B

A L
C

L B M

M 62/80
68/80
 ABR : Insertion d’un élément
◼ la fonction insertion(A,k) insère un nœud de clé k dans l'arbre dont
la racine est pointée par A
Insertion(A,k){
Creer_nœud(z); cle(z)=k; sa-gauche(z)=NIL; sa-droit(z)=NIL;
x=A; père_de_x=NIL;
tant que (x≠NIL){
pere_de_x=x;
si (k≤cle(x)) x=sa-gauche(x)
sinon x=sa-droit(x)
}
si (A==NIL) A=z
sinon si (k≤cle(pere_de_x)) sa-gauche(pere_de_x)=z
sinon sa-droit(pere_de_x)=z
}
63/80
69/80
 ABR : Minimum
• Minimum(A) :
◼ la fonction minimum(A) retourne le pointeur NIL

si l’arbre dont la racine est pointée par A est vide

◼ sinon, elle retourne le pointeur sur un nœud
contenant la clé minimale de l’arbre
minimum(A){
si (A==NIL) retourner A
sinon{
x=A;
tant que (sa-gauche(x)≠NIL)
x=sa-gauche(x);
retourner x;
}
} 64/80
 ABR : Maximum
• Maximum(A) :
◼ la fonction maximum(A) retourne le pointeur NIL

si l’arbre dont la racine est pointée par A est vide

◼ sinon, elle retourne le pointeur sur un nœud
contenant la clé maximale de l’arbre
maximum(A){
si (A==NIL) retourner A
sinon{
x=A;
tant que (sa-droit(x)≠NIL)
x=sa-droit(x);
retourner x;
}
} 65/80
Tables de hachage

66/80
 Tables de hachage
• Définitions
• Une table de hachage (hash table en anglais) est une structure de donnée
permettant d'associer une valeur à une clé.

• Il s'agit d'un tableau ne comportant pas d'ordre (un tableau est indexé par
des entiers). L'accès à un élément se fait en transformant la clé en une
valeur de hachage (ou simplement hachage) par l'intermédiaire d'une
fonction de hachage.

• Le hachage est un nombre qui permet la localisation des éléments dans le

tableau, typiquement le hachage est l'indice de l'élément dans le tableau.

• Une case dans le tableau est appelée alvéole.

67/80
Tables de hachage

68/80
 Tables de hachage

Différentes opérations peuvent être effectuées sur une table de

hachage :
- création d'une table de hachage ;
- insertion d'un nouveau couple (clé, valeur) ;
- suppression d'un élément ;
- recherche de la valeur associée à une clé (dans l'exemple de l'annuaire,
retrouver le numéro de téléphone d'une personne) ;
- destruction d'une table de hachage (pour libérer la mémoire occupée).

69/80
 Tables de hachage

Les tables de hachage sont surtout utiles lorsque le nombre d'entrées

est très important.

La position des éléments dans une table de hachage est aléatoire.

Cette structure n'est donc pas adaptée pour accéder à des données
triées

70/80
 Tables de hachage

Choix d'une bonne fonction de hachage

• Le fait de créer un hachage à partir d'une clé peut engendrer un
problème de collision:
• à partir de deux clés différentes, la fonction de hachage pourrait
renvoyer la même valeur de hachage
• Pour minimiser les risques de collisions, il faut donc choisir
soigneusement sa fonction de hachage.
• Le calcul du hachage se fait parfois en deux temps :
1. une fonction de hachage particulière à l'application est utilisée pour
produire un nombre entier à partir de la donnée d'origine
2. ce nombre entier est converti en une position possible de la table, en
général en calculant le reste modulo la taille de la table.
71/80
 Tables de hachage
Résolution des collisions

Lorsque deux clés ont la même valeur de hachage (collision), ces clés ne
peuvent être stockées à la même position. De nombreuses stratégies de
résolution des collisions existent mais les plus connues et utilisées sont le
chaînage et l'adressage ouvert.
Chaînage : Cette méthode est la plus simple. Chaque case de la table est en fait
une liste chaînée des clés qui ont le même hachage (chaînage en tête de liste).

Adressage ouvert : Cette méthode est généralement utilisée si le nombre

d’informations est peu par rapport à la taille de la table. L'adressage ouvert
consiste, dans le cas d'une collision, à stocker les valeurs de hachage dans
d'autres alvéoles vides.
72/80
 Tables de hachage

Soit h(k,i) une fonction de sondage. Une méthode de sondage consiste à essayer les
alvéoles d'indice h(k,0), h(k,1), ..., jusqu'à ce qu'on trouve une alvéole vide.
Il y a trois méthodes de sondage :

1.Sondage linéaire Soit H : U →{0, ... N-1} une fonction de hachage. La

fonction de sondage linéaire sera :
h(k,i) = (H(k) + i) mod N, avec i = 0, 1, ..., N-1.

73/80
 Tables de hachage

1. Sondage quadratique Soit H : U → {0, …, N-1} une fonction de hachage. La

fonction de sondage quadratique sera :
h(k,i) = (H(k) + c1·i + c2·i2 ) mod N, avec i = 0, 1, ..., N-1 et c2  0

1. Double hachage Soient H1 et H2 : U → {0, …, N-1} deux fonctions de hachage. Il

faudra faire en sorte que H2 ne soit jamais égal à 0. La fonction de sondage par
double hachage sera :
h(k,i) = (H1(k) + i·H2(k)) mod N, avec i = 0, 1, ..., N-1.

74/80
 Tables de hachage
Soit la structure suivante :

Item: Enregistrement
valeur : Entier
etat: Entier
Fin Enreg

THachage: tableau[1..100] de Item

Etat peut prendre les valeurs 0(libre),1(occupé),-1(sipprimé).

Implémentez les opérations :

HashExist (TH : THachage ,m,V :entier) : recherche d’une valeur V dans une table
de taille m, en utilisant un sondage linéaire
Hashinsert(TH: THachage,m,V :entier) : insertion d’une valeur V dans une table de
taille m, en utilisant un sondage linéaire
Hashdelete(TH: THachage,m,V :entier) : suppression d’une valeur V d’une table de
75/80
taille m, en utilisant un sondage linéaire