ECOLE NATIONALE SUPERIEURE DE L'INTELLIGENCE

ARTIFICIELLE ET SCIENCES DED DONNEES - TAROUDANT

Analyse et conception des algorithmes

Pr. Mohammed KASRI

[email protected]
 Plan:

1. Introduction
2. Les tableaux et le tri
3. Les algorithmes de tri élémentaires
4. Les algorithmes de tri avancés
5. Les algorithmes de recherche
6. Les arbres et les arbres binaires
7. Les graphes et ses algorithmes

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 2

 Introduction

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 3

Introduction

Programme = Structures de données + algorithmes

Niklaus Wirth (concepteur du langage Pascal)

Le problème est de concevoir les structures de données de manière à ce que :

• La mémoire utilisée soit minimale
• Les algorithmes soient les plus simples et les plus efficaces possible

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 4

Introduction

Structures de données:

Ordinateur = Système de Traitement de l’Information

• Unité de base = le bit (0/1)
• 1 octet = 8 bits

L’information n’est pas manipulable au même niveau par l’homme et par la

machine.

• Agrégation et structuration de l’information

• Construction de structures plus abstraites

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 5

Introduction

Hiérarchie des données:

Un ensemble structuré de données est construite par agrégation et

hiérarchisation de données ou structures de données plus primitives.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 6

Introduction

Notion d’algorithme:

Un algorithme est la composition d’un ensemble fini d’étapes dont chacune est:
• Définie de façon rigoureuse;
• Définie de façon non ambiguë;
• Effective (pouvant être réalisée en un temps fini).

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 7

Introduction

Simplicité & Efficacité:

Notion d’algorithme plus générale que celle de programme.

Deux besoins (potentiellement contradictoires) :

Simplicité de l’algorithme Efficacité de l’algorithme

• A comprendre • Place mémoire
• A mettre en œuvre • Vitesse d’exécution
• A mettre au point

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 8

Introduction

Exercice d’application:

Ecrire une fonction permettant de calculer la somme de 1 à n.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 9

Introduction

Exemple: Somme des entier de 1 à n

Algorithme naif

def somme(n):
som = 0
for i in range(1,n+1):
som = som + i
print(i,':',som-i,"+",i,'=',som)
return(som)

print("entrer un entier: ")

n=input()
print("resultat: ",somme(int(n)))

• Cet algorithme est-il efficace?

• Combien d'addition en fonction de n va faire cet algorithme?
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 10
Introduction

Exemple: Somme des entier de 1 à n

Algorithme naif

def somme(n): entrer un entier:

som=0 7
for i in range(1,n+1): 1 : 0 + 1 = 1
som = som + i 2 : 1 + 2 = 3
print(i,':',som-i,"+",i,'=',som) 3 : 3 + 3 = 6
return(som) 4 : 6 + 4 = 10
5 : 10 + 5 = 15
print("entrer un entier: ") 6 : 15 + 6 = 21
n=input() 7 : 21 + 7 = 28
print("resultat: ",somme(int(n))) resultat: 28

• Cet algorithme est-il efficace?

• Combien d'addition en fonction de n va faire cet algorithme?
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 11
Introduction

Exemple: Somme des entier de 1 à n

Critères mathématiques:

Récrire la fonction précédente pour qu’elle calcule la somme de 1 à n sans

utiliser les boucles.
Comparer les résultats des deux fonctions.
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 12
Introduction

Exemple: Somme des entier de 1 à n

Critères mathématiques:

Coût: 1 addition, 1 multiplication et 1 division (3 opérations)

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 13

Introduction

Complexité et récursivité:

Un algorithme récursif est un algorithme qui s'appelle lui-même.

On oppose généralement les algorithmes récursifs aux algorithmes dits itératifs

qui s'exécutent sans invoquer ou appeler explicitement l'algorithme lui-même.

La complexité des algorithmes est une mesure de la quantité de ressources

(principalement le temps et l'espace) qu'un algorithme utilise en fonction de la
taille de l'entrée.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 14

 Les tableaux et le tri

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 15

Les tableaux et le tri

Définition:

Un tableau est une structure de donnée T qui permet de stocker un certain

nombre d’éléments T[i] repérés par un index i. Les tableaux vérifient
généralement les propriétés suivantes :

 Tous les éléments ont le même type de base ;

 Le nombre d’éléments stockés est fixé ;
 L’accès et la modification de l’élément numéro i est en temps constant
Θ(1), indépendant de i et du nombre d’éléments dans le tableau.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 16

Les tableaux et le tri

Définition:

• En anglais : array, vector.

• Les éléments suivants peuvent être utilisés pour représenter des tableaux en
Python:
• En utilisant des listes
• Via le module de array
• Avec le module NumPy

Remarque: Nous pouvons traiter les listes comme des tableaux. Cependant, le
type d’éléments stockés est complètement différent.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 17

Les tableaux et le tri

Le tri:

Problème : étant donné un tableau d’entiers T , trier T dans l’ordre croissant.

Solution:

• On considère une collection d'entier placés dans un tableau.

• Un opérateur de comparaison (≤,≥, >, <, …)
• Grande richesse conceptuelle :
 Des algorithmes basés sur des idées et des structures de données très
différentes. . .
 Des complexités différentes.
 Des algorithmes optimaux.
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 18
Les tableaux et le tri

Types de tri

• Tri interne : tri en mémoire centrale. Tris externes : données sur un disque
externe.

• Tri de tableau : tri qui trie un tableau. Extensible à toutes structures de

données offrant un accès en temps (quasi) constant à ses éléments.

• Tri générique : peut trier n’importe quel type d’objets pour autant qu’on
puisse comparer ces objets.

• Tri comparatif : basé sur la comparaison entre les éléments (clés).

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 19

Les tableaux te le tri

Types de tri

• Tri itératif : basé sur un ou plusieurs parcours itératifs du tableau.

• Tri récursif : basé sur une procédure récursive.

• Tri en place : modifie directement la structure qu’il est en train de trier. Ne

nécessite qu’une quantité très limitée de mémoire supplémentaire.

• Tri stable : conserve l’ordre relatif des éléments égaux (au sens de la
méthode de comparaison).

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 20

Les algorithmes de tri élémentaires

Les algorithmes de tri élémentaires

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 21

Les algorithmes de tri élémentaires

Tri sélection:

• Tableau toujours divisé en 2 parties

• A chaque étape:
 Choisir le plus petit élément de la partie non triée
 Mettre cet élément à la fin de la partie triée

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 22

Les algorithmes de tri élémentaires

Tri sélection:

1. Trouver le plus petit élément et le mettre au début de la liste

2. Trouver le 2e plus petit et le mettre en seconde position
3. Trouver le 3e plus petit élément et le mettre à la 3e place
4. ...

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 23

Les algorithmes de tri élémentaires

Tri sélection: illustration

2 1 5 0 9 4

0 1 5 2 9 4

0 1 5 2 9 4

0 1 2 5 9 4

0 1 2 4 9 5

0 1 2 4 5 9

0 1 2 4 5 9

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 24

Les algorithmes de tri élémentaires

Tri sélection: Exercice d’application

Ecrire l’algorithme de tri par sélection.
Version 1 Version 2
Algorithme Programmer le tri par sélection. Algorithme Programmer le tri par sélection.
Entrée : T liste de n nombres. Entrée : T liste de n nombres.
Sortie : liste T triée Sortie : liste T triée
Début Début
Pour i de 1 à n − 1 Pour i de 1 à n − 1
indiceMin ← i ind ← IndiceMin(T , i, n)
Pour j de i + 1 à n T [i] ↔ T [ind]
si T[j] < T[i] alors finPour
indiceMin ← j Fin
finSi
finPour
T [i] ↔ T [indiceMin]
finPour
Fin

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 25

Les algorithmes de tri élémentaires

Tri sélection: Exercice d’application

Ecrire le programme python correspondant.
def tri_selection(tab):
for i in range(len(tab)-1):
min = i
for j in range(i+1, len(tab)):
if tab[min] > tab[j]:
min = j
tmp = tab[i]
tab[i] = tab[min]
tab[min] = tmp
return tab

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 26

Les algorithmes de tri élémentaires

Tri sélection: Complexité

• Nombre d’itérations : n - 1
• A chaque itération :
 Recherche du minimum : n − T (T taille courante)
 Mettre l’élément à sa place : 3

• Au total : 3n + n(n − 1)/2

• Complexité : O(n2)

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 27

Les algorithmes de tri élémentaires

Tri insertion:

C’ est un algorithme efficace quand il s’agit de trier un

petit nombre d’éléments.

Le tri par insertion s’inspire de la manière dont la

plupart des gens tiennent des cartes à jouer.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 28

Les algorithmes de tri élémentaires

Tri insertion:

Le tri du joueur de cartes !

• Ordonner les deux premiers éléments.

• Insérer le 3e élément de manière à ce que les 3 premiers éléments soient triés
• Insérer le 4e élément à “sa” place pour que. . .
•...
• Insérer le ne élément à sa place

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 29

Les algorithmes de tri élémentaires

Tri insertion: illustration

7 4 3 1 9 2 5

4 7 3 1 9 2 5

3 4 7 1 9 2 5

1 3 4 7 9 2 5

1 3 4 7 9 2 5

1 2 3 4 7 9 5

1 2 3 4 5 7 9

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 30

Les algorithmes de tri élémentaires

Tri insertion: Exercice d’application

Ecrire l’algorithme de tri insertion

Algorithme Programmer le tri par sélection.

Entrée : T liste de n nombres.
Sortie : liste T triée
Début
Pour i de 1 à n − 1
v ← T[i]
j←i-1
Tanque j>=0 et T[j] > v
T[j+1] ← T[j] alors
J←j-1
finTanque
T[j+1] ← v
Fin

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 31

Les algorithmes de tri élémentaires

Tri insertion: Exercice d’application

Ecrire le programme python correspondant.
def tri_insertion(L):
n =len(L)
for i in range(1,n):
v = L[i]
j = i-1
while j>=0 and L[j] > v:
L[j+1] = L[j]
j = j-1
L[j+1] = v
return(L)

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 32

Les algorithmes de tri élémentaires

Tri insertion: complexité

Dans le pire cas ou en moyenne, la complexité du tri par sélection est en O(n2)

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 33

Les algorithmes de tri élémentaires

Tri à bulle (par permutation):

• Si 2 éléments voisins ne sont pas ordonnés on les échange

• Deux parties dans le tableau

• Les éléments de la partie triée sont inférieurs aux éléments de la partie non
triée.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 34

Les algorithmes de tri élémentaires

Tri à bulle : illustration

7 4 3 1 9 2 5 4 3 1 7 2 5 9 3 1 4 2 5 7 9

4 7 3 1 9 2 5 3 4 1 7 2 5 9 1 3 4 2 5 7 9

4 3 7 1 9 2 5 3 1 4 7 2 5 9 1 3 4 2 5 7 9

4 3 1 7 9 2 5 3 1 4 7 2 5 9 1 3 2 4 5 7 9

4 3 1 7 9 2 5 3 1 4 2 7 5 9 1 3 2 4 5 7 9

4 3 1 7 2 9 5 3 1 4 2 5 7 9 1 3 2 4 5 7 9
4 3 1 7 2 5 9 3 1 4 2 5 7 9
4 3 1 7 2 5 9

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 35

Les algorithmes de tri élémentaires

Tri à bulle : Exercice d’application

Ecrire l’algorithme de tri à bulle

Algorithme Programmer le tri par sélection.

Entrée : T liste de n nombres.
Sortie : liste T triée
Début
Pour i de 0 à n − 1
Pour j de 0 à n – i - 1
si T[j] > T[j+1] alors
T[j] ↔T[j+1]
finSi
finPour

Fin

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 36

Les algorithmes de tri élémentaires

Tri à bulle : Exercice d’application

Ecrire le programme python correspondant.
def tri_bulle(tab):
n = len(tab)
for i in range(0,n):
for j in range(n-i-1):
if tab[j] > tab[j+1] :
tmp=tab[j+1]
tab[j+1]=tab[j]
tab[j] = tmp
return(tab)

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 37

Les algorithmes de tri élémentaires

Tri à bulle : Complexité

Dans le pire cas ou en moyenne, la complexité du tri à bulle est en O(n2).

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 38

Les algorithmes de tri avancés

Les algorithmes de tri avancés

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 39

Les algorithmes de tri avancés

Paradigme "diviser pour régner":

Le diviser pour régner est une méthode algorithmique basée sur le principe
suivant :

1. DIVISER: Divisant un problème en sous-problèmes.

2. RÉGNER: Résolvant (régner) ces sous-problèmes individuellement.
3. COMBINER: Combinant les résultats partiels pour résoudre le problème
initial.

Remarque: Les algorithmes basés sur le paradigme "diviser pour régner" sont
très souvent des algorithmes récursifs.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 40

Les algorithmes de tri avancés

Tri fusion :

Le tri fusion consiste à décomposer une liste en deux sous-listes chacune deux
fois plus petites, de les trier séparément, puis de fusionner les résultats en une
liste triée.

• 1er algo de tri fusion écrit par Von Neumann pour l’EDVAC en 1945.
• Basé sur le paradigme « Diviser pour Régner ».

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 41

Les algorithmes de tri avancés

Tri fusion : illustration

7 4 3 1 9 2 5 Appel récursif

7 4 3 1 9 2 5 Fusion

7 4 3 1 9 2 5

7 4 3 1 9 2

4 7 1 3 2 9

1 3 4 7 2 5 9

1 2 3 4 5 7 9

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 42

Les algorithmes de tri avancés

Tri fusion : algorithme tri fusion

Algorithme Trifusion.
Entrée : T liste de n nombres.
Sortie : Eléments de T ordonnés par ordre croissant
Début
Si n ≤ 1 alors
retourner L
Sinon
L1 <- L[début….milieu]
L2 <- L[milieu…fin]
retourner fusionner(trifusion(L 1),trifusion(L 2))
finsi
Fin

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 43

Les algorithmes de tri avancés

Tri fusion : illustration(fusion)

1 3 4 7 2 5 9 1

1 3 4 7 2 5 9 1 2

1 3 4 7 2 5 9 1 2 3

1 3 4 7 2 5 9 1 2 3 4

1 3 4 7 2 5 9 1 2 3 4 5

1 3 4 7 2 5 9 1 2 3 4 5 7

1 3 4 7 2 5 9 1 2 3 4 5 7 9

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 44

Les algorithmes de tri avancés

Tri fusion : algorithme fusion

Algorithme Fusionner.
Entrée : 2 listes T1 et T1. Tanque i <= n
Sortie : Les deux listes fusionnées T[k] <- T1[i]
Début k <- k+1
i <- indice du début de T1 i <- i+1
n <- indice de fin de T1 Fin Tanque
j <- indice du début de T2
m <- indice de fin de T2 Tanque j <= m
k <- 1 T[k] <- T2[j]
Tanque i<= n et j <= m k <- k+1
Si T1[i] < T2[j] Alors j <- j+1
T[k] <- T1[i] Fin Tanque
i <- i+1
Sinon retourner T
T[k] <- T2[j]
j <- j+1
FinSi
k <- k+1
FinTanque
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 45
Les algorithmes de tri avancés

Tri fusion : Exercice d’application

Implémenter l’algorithme fusion avec Python pour fusionner deux listes triées.
def fusion(L1,L2):
n1 = len(L1) while i1<n1:
n2 = len(L2) L12.append(L1[i1])
L12 = [] i1 += 1;i += 1
i1 = 0; i2 = 0; i = 0 while i2<n2:
while i1<n1 and i2<n2: L12.append(L2[i2])
if L1[i1] < L2[i2]: i2 += 1; i += 1
L12.append(L1[i1]) return(L12)
i1 += 1
else:
L12.append(L2[i2])
i2 += 1
i += 1

Implémentation de tri fusion dans le TP.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 46
Les algorithmes de tri avancés

Tri fusion : complexité

Dans le pire cas ou en moyenne, la complexité du tri à bulle est en O(n log2 n).

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 47

Les algorithmes de tri avancés

Tri rapide (par partitionnement):

• Inventé par Hoare en 1960

• Dans le top 10 des algorithmes du 20-ième siècle (SIAM)
• Approche “diviser pour régner”

Ce tri consiste à choisir un élément dans la liste, appelé le pivot, puis à

réarranger la liste pour que tous les éléments inférieurs ou égaux au pivot
soient situés avant le pivot et tous les éléments supérieurs au pivot soient situés
après le pivot.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 48

Les algorithmes de tri avancés

Tri rapide : algorithme

Algorithme Trirapid.
Entrée : T liste de n nombres, début et fin des entiers
Sortie : Eléments de T ordonnés par ordre croissant
Début
Si n ≤ 1 alors
retourner L
Sinon
Indice_pivot = partitionnement(T, début,fin)
Trirapid(T, début, indice_pivot-1)
Trirapid(T, indice_pivot+1, fin)

finsi
Fin

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 49

Les algorithmes de tri avancés

Tri rapide : illustration (partitionnement)

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 50

Les algorithmes de tri avancés

Tri rapide : Exercice d’application

Implémenter avec Python la fonction de partitionnement. Cette fonction doit

renvoyer la position de pivot.
def partition(L,debut,fin):
pivot = L[fin]
i = debut
j = debut
while j < fin:
if L[j] <= pivot:
L[i],L[j] = L[j],L[i]
i += 1
j += 1
L[fin],L[i] = L[i],L[fin]
return i

Implémentation de tri rapide dans le TP.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 51
Les algorithmes de tri avancés

Tri rapide : complexité

Dans le pire cas, la complexité du tri rapide est en O(n2). Mais en moyenne, elle
est en O(n log(n)).

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 52

Les algorithmes de tri avancés

• Tous les tris vu jusqu’à maintenant sont tris par comparaisons

• Un tri par comparaison est un tri dans lequel on compare une paire
d’éléments.

• Existe-t-il des tris qui ne sont pas par comparaisons?

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 53

Les algorithmes de tri avancés

Tri linéaire (par dénombrement, comptage):

Le tri linéaire est un tri qui opère uniquement sur des listes de valeurs entières
avec une faible dispersion.

Un des algorithmes de tri le plus rapide, et pourtant il est loin d'être compliqué.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 54

Les algorithmes de tri avancés

Tri linéaire :

Les étapes du tri par dénombrement sont les suivantes :

1. Déterminer la valeur maximale dans le tableau

2. Regrouper dans un autre tableau le nombre d'apparitions de chaque valeur

entre 0 et le maximum déterminé à l'étape précédente.

3. Dans ce tableau d'effectifs, la valeur à l'indice x donne le nombre

d'apparitions de x dans le tableau initial.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 55

Les algorithmes de tri avancés

Tri linéaire : illustration

0 1 2 3 4 5 6 0 1 2 3 4 5 6

3 6 4 1 3 4 1 4 0 0 0 0 0 0 0 3 6 4 1 3 4 1 4 0 1 0 2 2 0 1

0 1 2 3 4 5 6 0 1 2 3 4 5 6

3 6 4 1 3 4 1 4 0 0 0 1 0 0 0 3 6 4 1 3 4 1 4 0 2 0 2 2 0 1

0 1 2 3 4 5 6 0 1 2 3 4 5 6

3 6 4 1 3 4 1 4 0 0 0 1 0 0 1 3 6 4 1 3 4 1 4 0 2 0 2 3 0 1

0 1 2 3 4 5 6

3 6 4 1 3 4 1 4 0 0 0 1 1 0 1
0 1 2 3 4 5 6

3 6 4 1 3 4 1 4 0 1 0 1 1 0 1

0 1 2 3 4 5 6

3 6 4 1 3 4 1 4 0 1 0 2 1 0 1

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 56

Les algorithmes de tri avancés

Tri linéaire : illustration

0 1 2 3 4 5 6 0 1 2 3 4 5 6

0 2 0 2 3 0 1 0 2 0 2 3 0 1 1 1 3 3 4 4 4
0 1 2 3 4 5 6 0 1 2 3 4 5 6

0 2 0 2 3 0 1 0 2 0 2 3 0 1 1 1 3 3 4 4 4 6
0 1 2 3 4 5 6

0 2 0 2 3 0 1 1 1
0 1 2 3 4 5 6

0 2 0 2 3 0 1 1 1
0 1 2 3 4 5 6

0 2 0 2 3 0 1 1 1 3 3
0 1 2 3 4 5 6

0 2 0 2 3 0 1 1 1 3 3 4 4 4

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 57

Les algorithmes de tri avancés

Tri linéaire : Algorithme

Algorithme Trilinéaire.
Entrée : T liste de n nombres
Sortie : R contenant les éléments de T ordonnés par ordre croissant
Début
pour i de 0 à m − 1 // ini alisa on
nb[i] <- 0
pour i de 0 à n // calcul des nombres d’apparitions
nb[T[i]] <- nb[T[i]] + 1,

pos[0] <- 0 // calcul des indices du premier élément de chaque catégorie

pour i <- 1 à m − 1 faire
pos[i] <- pos[i] + nb[i − 1]

pour i <- 1 à n //faire recopie des élément originaux du tableau T dans R

R[pos[T[i]]] <- T[i]
pos[T[i] <- pos[T[i] + 1
Fin

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 58

Les algorithmes de tri avancés

Tri linéaire : Exercice d’application

Implémenter l’algorithme tri linéaire avec Python.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 59

Les algorithmes de tri avancés

Tri linéaire : complexité

• L'initialisation du tableau des effectifs se fait en O(n) (avec n la taille du

tableau en entrée)

• La copie des éléments dans notre tableau trié en O(m) (avec m

correspondant à Max).

• La complexité finale de notre algorithme est donc O(n + m), soit une
complexité en temps linéaire.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 60

Les algorithmes de tri avancés

Autres tris:

• Tri cocktail
• Tri par tas
• Smoothsort
• Tri de Shell
• Tri à peigne

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 61

Les algorithmes de tris

Récapitulatif:

Algorithme Complexité Principe

Insertion O(n2) Prendre un élément non encore trié, l’insérer à sa place dans les éléments
triés
Sélection O(n2) Choisir le plus petit élément de la partie non triée, le mettre à la [n de la
partie triée
Permutation O(n2) Si 2 éléments voisins ne sont pas ordonnés on les échange
Fusion O(n log2 n) On divise le tableau en élément plus petit, les tableaux sont triés à la
reconstruction
Rapid O(n2) Utilisation d'un pivot, les éléments sont triés en séparant les liste

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 62

 Les algorithmes de recherche

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 63

Les algorithmes de recherche

Le problème est de trouver un élément dans une structure linéaire (tableau).

- L'élément peut ne pas être présent
- L'élément peut être présent à plusieurs endroits
- Si la structure a plusieurs dimensions, il faut fouiller chaque dimension

Technique intuitive : la recherche séquentielle

- On parcourt la structure dans l'ordre « naturel »
- On s'arrête au bout, ou quand on trouve l'élément
- Parfois on peut s'arrêter plus tôt

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 64

Les algorithmes de recherche

La recherche séquentielle:

La recherche séquentielle (sequential search en anglais) parcourt, case après

case, les éléments d’un tableau et s’arrête au premier élément rencontré qui est
égale à l’élément recherché.

Dans ce cas l’information renvoyée est la position (c.-`a-d. l’indice) contenant

l’élément recherché (ou une indication de l’existence de l’élément).

Complexité : O(n)

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 65

Les algorithmes de recherche

La recherche séquentielle: Exercice d’application

Ecrire une fonction existe_deux(chaine, lettre) qui permet de tester si une lettre
apparaît deux fois dans une chaine.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 66

Les algorithmes de recherche

La recherche dichotomique:

Le tableau est supposé trié par ordre croissant.

Principe de l'algorithme (on cherche un élément x dans un tableau t):

1. On regarde l'élément situé au milieu de t
2. S'il s'agit de x c'est gagné.
3. S'il est plus grand que x, on cherche dans la moitié gauche
4. S'il est plus petit que x, on cherche dans la moitié droite

Remarques :
- Ça ne peut marcher que si le tableau est trié
- On coupe le tableau en deux parties pas forcément égales en taille
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 67
Les algorithmes de recherche

La recherche dichotomique: illustration

On cherche 6
1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

6 7 8 9 10

6 7

6 7

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 68

Les algorithmes de recherche

La recherche dichotomique: Exercice d’application

Implémenter la version itérative de la recherche dichotomique.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 69

Les algorithmes de recherche

La recherche par interpolation:

La recherche par interpolation tient compte de la valeur de l’élément recherché

pour estimer à quel endroit faire une recherche.

C’est le principe de la recherche dans un dictionnaire : pour rechercher le mot «

ananas », on ouvrira le dictionnaire vers le début, plutôt qu’au milieu.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 70

Les algorithmes de recherche

La recherche par interpolation:

Supposons que nous ayons un tableau A contenant n éléments et que nous

voulons trouver un élément donné X.

1. Tanque X se situent dans la plage recherche

2. Trouver l’indice du milieu
3. Si l’élément à la position de la sonde est inférieur à l’élément cible, déplacez-
vous vers la droite
4. Sinon, si l’élément est supérieur à l’élément cible, déplacez-vous vers la
gauche
5. Sinon, nous avons trouvé l’élément et nous retournons l’indice du milieu

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 71

Les algorithmes de recherche

La recherche par interpolation: Exemple

Supposons que nous ayons le tableau : (1, 3, 7, 8, 11, 15, 17, 18, 21), et que nous voulions
trouver X = 18.

1. Initialiser lo = 0 , mid= -1 et hi = 8.
2. Calculer mid utilisant la formule : 0 + (18 - 1)*(8 - 0)//(21-1) = 6.

3. Ensuite, nous comparons A[6] avec X pour voir qu’il est plus petit et nous fixons lo comme
7.

4. Calculer mid en utilisant 7 + (18 - 18)*(8 - 7)/(21 - 18) = 7.

5. Ensuite, on compare A[7] avec X pour voir qu’il est égal à 18 et on obtient l’indice 7.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 72

 Les arbres

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 73

Les arbres

Introduction

Structure de données:

• Linéaire : Listes, Piles, Files, Tableaux

0 1 2 3

3 7 0 9

• Non Linéaire: Arbres, Graphes

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 74

Les arbres

Définition

Un arbre est un ensemble organisé de nœuds dans lequel chaque nœud a un

père et un seul, sauf un nœud que l’on appelle la racine.

• Contient 0 ou N nœuds
• Déplacement entre les nœuds se fait dans un seul sans
• Chaque nœud peut avoir 0 ou N successeurs
• Chaque nœud a 0 ou 1 prédécesseur

Remarques: on représente le père au-dessus de ses fils,

et donc la racine tout en haut.
La taille d'un arbre est le nombre total de nœuds de cet arbre.
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 75
Les arbres

Exercice d’application

1 2 3 4 5 6

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 76

Les arbres

Applications

• Arbres généalogiques: Arbre de descendance des prophètes

• Arbres de classification: intelligence artificielle
• Arbres d’expression: Expression arithmétique

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 77

Les arbres

Types des arbres

Ordre de hiérarchie Arité

Enraciné Non enraciné Binaires N-Aires

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 78

Les arbres

Terminologie

Nœuds
1

2 3 4

5 6 7 8 9

10 11 12

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 79

Les arbres

Terminologie

Nœuds
1
Racine (root)

2 3 4

5 6 7 8 9

10 11 12

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 80

Les arbres

Terminologie

Nœuds
1
Racine (root)
Parent
2 3 4

5 6 7 8 9

10 11 12

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 81

Les arbres

Terminologie

Nœuds
1
Racine (root)
Parent
Files 2 3 4

5 6 7 8 9

10 11 12

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 82

Les arbres

Terminologie

Nœuds
1
Racine (root)
Parent
Files 2 3 4
Feuille (descendant)
5 6 7 8 9

10 11 12

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 83

Les arbres

Terminologie

Nœuds
1
Racine (root)
Parent
Files 2 3 4
Feuille (descendant)
Frères 5 6 7 8 9

10 11 12

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 84

Les arbres

Terminologie

Nœuds
1
Racine (root)
Parent
Files 2 3 4
Feuille (descendant)
Frères 5 6 7 8 9

10 11 12

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 85

Les arbres

Terminologie

Nœuds
1
Racine (root)
Parent
Files 2 3 4
Feuille (descendant)
Frères 5 6 7 8 9
Ancêtres
10 11 12

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 86

Les arbres

Terminologie

Nœuds
1
Racine (root)
Parent
Files 2 3 4
Feuille (descendant)
Frères 5 6 7 8 9
Ancêtres
Branches (Nb branches = Nb nœuds - 1) 11 12
10

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 87

Les arbres

Terminologie

Nœuds
1
Racine (root)
Parent
Files 2 3 4
Feuille (descendant)
Frères 5 6 7 8 9
Ancêtres
Branches (Nb branches = Nb nœuds - 1) 11 12
10
Sous-arbre

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 88

Les arbres

Terminologie

Profondeur:
1
Niveau 0

Niveau 1 2 3 4

5 6 7 8 9
Niveau 2

10 11 12

Niveau 3

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 89

Les arbres

Terminologie

Profondeur:
1
La profondeur d’un nœud (niveau d’un nœud ) et le nombre de
branches que je dois parcourir pour da la racine pour arriver à ce
nœud. 2 3 4

Exemple: 5 6 7 8 9
Profondeur de nœud étiqueté 7=2
Profondeur de nœud étiqueté 10=3 11 12
10

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 90

Les arbres

Terminologie

Profondeur (hauteur):
1
La profondeur d’un nœud (niveau d’un nœud ) et le nombre de
branches que je dois parcourir pour da la racine pour arriver à ce
nœud. 2 3 4

Exemple: 5 6 7 8 9
Profondeur de nœud étiqueté 7=2
Profondeur de nœud étiqueté 10=3 11 12
10

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 91

Les arbres

Terminologie

Profondeur (hauteur):
1
• La hauteur d’un arbre vide est 0.

• La hauteur d’un arbre non vide est la plus grande 2 3 4

hauteur des sous-arbres de la racine.
5 6 7 8 9

Remarque: Certains auteurs compte aussi la hauteur de 11 12

10
la racine dans le calcule de la hauteur.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 92

Les arbres

Exercice d’application

• Quelle est la hauteur de nœud étiqueté 9

1
• Quelle est la hauteur de nœud étiqueté 7

• H(9) = 3 2 3 4 5
• H(7) = 2
6 7 8

9 10

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 93

Les arbres

Terminologie

Chemin d'un nœud:

1

On appelle chemin du nœud la suite des nœuds par lesquels

il faut passer pour aller de la racine vers le nœud. 2 3 4

Exemples: 5 6 7 8 9
Chemin du nœud 10 = (1,2,6,10)
Chemin du nœud 9 = (1,4,9) 11 12
10

Remarque: h( X ) = NbrNoeud( Chemin( X ) ) -1 .

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 94

Les arbres

Terminologie 1

Degré d'un nœud:

2 3 4
le degré d'un nœud est égal au nombre de ses enfants

5 6 7 8 9
Exemples:
Le nœud 1 est de degré 3, car il a 3 enfants
Le nœud 4 est de degré 2, car il a 2 enfants 10 11 12

Remarques: lorsqu'un arbre a tous ses nœuds de degré 1, on le nomme arbre

dégénéré et que c'est en fait une liste.
Le degré d'un arbre est égal au plus grand des degrés de ses nœuds.
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 95
 Les arbres binaires

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 96

Les arbres binaires

Définition:
• Un arbre binaire est un cas particulier des arbres enracinés (un arbre de
degré 2).

• Un arbre binaire est un arbre tels que tout nœud a au plus un fils gauche et
au plus un fils droit. 1

Enfant gauche Enfant droit

2 3

4 5 6 7

8 9 10

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 97

Les arbres binaires

Arbre parfait:

• Un arbre binaire dont tous les nœuds de chaque niveau sont présents est
appelé arbre parfait.

• Si le dernier niveau ne contient pas des nœuds, on dit que l'arbre parfait est
un arbre binaire incomplet si les feuilles du dernier sont regroupées à partir
de la gauche de l'arbre.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 98

Les arbres binaires

Arbre parfait:
Arbre parfait complet Arbre parfait incomplet

Arbres non parfaits

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 99

Les arbres binaires

Parcours d'un arbre binaire:

L'opération qui consiste à retrouver systématiquement tous les nœuds d'un

arbre et d'y appliquer un même traitement se dénomme parcours de l'arbre.

• N’est pas simple que dans le cas d’une liste

• Pas d’ordre naturel
• Deux types de parcours
• En largeur d’abord (Breadth-First Search: BFS)
• En profondeur d’abord (Depth-First Search : DFS)

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 100

Les arbres binaires

Parcours en largeur (ou hiérarchique) :

Un algorithme classique consiste à explorer chaque nœud d'un niveau donné de

gauche à droite, puis de passer au niveau suivant.

Exemple:
Le résultat d'affichage est : 12 ; 1 ; 7 ; 91 ; 67 ; 82 ; 61

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 101

Les arbres binaires

Parcours en profondeur:

Le parcours en profondeur permet d'explorer l'arbre en explorant jusqu'au bout

une branche pour passer à la suivante.

• Parcours préfixe
• Parcours infixe
• Parcours suffixe

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 102

Les arbres binaires

Parcours en profondeur: Parcours préfixe

Tout Nœud est suivi des nœuds de son sous-arbre Gauche puis des nœuds de
son sous-arbre Droit (Valeur, Fils-g, Fils-d).
Parcours prefixe(Arbre A)
Si A est non vide Alors
Afficher l’étiquette de A // Valeur
Parcours prefixe(Fils-g A)
Parcours prefixe(Fils-d A)
FinSi
Exemple:
Le résultat d'affichage est : 12 ; 1 ; 91 ; 67 ; 7; 82 ; 61

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 103

Les arbres binaires

Parcours en profondeur: Parcours infixe

Tout Nœud est précédé des nœuds de son sous-arbre Gauche et suivi des
nœuds de son sous-arbre Droit (Fils-g, Valeur, Fils-d).
Parcours infixe(Arbre A)
Si A est non vide Alors
Parcours infixe(Fils-g A)
Afficher l’étiquette de A // Valeur
Parcours infixe(Fils-d A)
FinSi
Exemple:
Le résultat d'affichage est : 91 ; 1 ; 67 ; 12; 7; 61; 82

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 104

Les arbres binaires

Parcours en profondeur: Parcours postfixe

Tout Noeud est précédé des nœuds de son sous-arbre Gauche et des nœuds de
son sous-arbre Droit (Fils-g, Fils-d, Valeur).
Parcours postfixe(Arbre A)
Si A est non vide Alors
Parcours postfixe(Fils-g A)
Parcours postfixe(Fils-d A)
Afficher l’étiquette de A // Valeur
FinSi
Exemple:
Le résultat d'affichage est : 91 ; 67; 1 ; 61; 82; 7; 12

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 105

Les arbres binaires

Exercice d’application

B
En donnant l’arbre suivant:

H E
Quel est le résultat d’affichage dans les cas suivants:
• Parcours préfixe
A T
• Parcours infixe
• Parcours postfixe

Solution:
BHATE–AHTBE–ATHEB

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 106

Les arbres binaires

Exercice d’application

Quel type de parcours doit être utilisé pour évaluer une expression
arithmétique ?
+

* -

4 3 2 7

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 107

Les arbres binaires

Implémentation

On implémente les arbres binaires non vides par des listes de trois éléments :

[valeur , fils gauche , fils droit ]

Arb=[15, [ 7, [6, None, None] , [9, None, None] ], [20, None,[25, None, None] ] ]
Un arbre vide est : Arb = None

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 108

 Les arbres parfaits

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 109

Les arbres parfaits

Définition:

Un arbre binaire est parfait si :

1. Tous les nœuds de chaque niveau sont présents sauf éventuellement au

dernier niveau où il peut manquer des nœuds (nœuds terminaux = feuilles),
dans ce cas l'arbre parfait est un arbre binaire incomplet.

2. Les feuilles du dernier niveau doivent être regroupées à partir de la gauche

de l'arbre.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 110

Les arbres parfaits

Implémentation:
Un arbre binaire parfait peut être implémenter avec une simple liste L , avec les
règles suivantes :
Règle 1: L[0] est la racine de l’arbre Règle 2: L[2*(i+1)-1] et L[2*(i+1)] sont les feuilles de L[i]

Règle 3: Si i est supérieur ou égale à len(L)//2, L[i] est une feuille.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 111

Les arbres parfaits

Implémentation: exemple

56

56 25
56
56 25 17

56 25 17 21
25 17
56 25 17 21 1
21 1 8 12
56 25 17 21 1 8

56 25 17 21 1 8 12

5
56 25 17 21 1 8 12 5

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 112

Les arbres parfaits

Exercice d’application:

Ecrire une fonction en Python « indice_fils(i) » qui renvoie les indice des fils
gauche et droit du nœud d’indice i

def indice_fils(i):
return 2*i + 1 , 2*i + 2

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 113

Les arbres parfaits

Tri Maximier (Tri par tas):

• L'idée qui sous-tend cet algorithme consiste à voir le tableau comme un

arbre binaire.

• On cherche à obtenir un tas, c'est-à-dire un arbre binaire parfait vérifiant la

propriété suivante:

Chaque nœud est de valeur supérieure (resp. inférieure) à celles de ses deux
fils, pour un tri ascendant (resp. descendant).

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 114

Les arbres parfaits

Tri Maximier (Tri par tas):

Les étapes pour trier un tableau à l'aide du tri par tas sont:

1. Construction du tas: le tableau non trié est transformé en un tas.

2. Tri du tas : l'élément racine (min ou max) est échangé avec le dernier
élément du tableau non trié.
3. Répétition : Les étapes 1 et 2 sont répétées jusqu'à ce que le tableau soit
entièrement trié.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 115

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 1

Liste initiale:
7 27 41 30 10 31 22 3 23
7

27 41

30 10 31 22

3 23

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 116

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 1

Liste initiale:
7 27 41 30 10 31 22 3 23
7

27 41

30 10 31 22

3 23

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 117

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 1

Liste initiale:
7 27 41 30 10 31 22 3 23
7
7 30 41 27 10 31 22 3 23

30 41

27 10 31 22

3 23

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 118

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 1

Liste initiale:
7 27 41 30 10 31 22 3 23
41
7 30 41 27 10 31 22 3 23

41 30 7 27 10 31 22 3 23 30 7

27 10 31 22

3 23

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 119

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 1

Liste initiale:
7 27 41 30 10 31 22 3 23
41
7 30 41 27 10 31 22 3 23

41 30 31 27 10 7 22 3 23 30 31

27 10 7 22
Nouvelle liste (le Tas)
41 30 31 27 10 7 22 3 23
3 23

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 120

Les arbres parfaits

Exercice d’application:

Donner manuellement le tas de la liste suivante:

3 0 12 4 3 1 9
3

0 12

4 3 1 9

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 121

Les arbres parfaits

Exercice d’application:

Donner manuellement le tas de la liste suivante:

3 0 12 4 3 1 9
12

4 9

0 3 1 3

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 122

Les arbres parfaits

Exercice d’application:

Donner manuellement le tas de la liste suivante:

3 0 12 4 3 1 9
12

4 9
Le tas est:
12 4 9 0 3 1 3
0 3 1 3

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 123

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

41

30 31

27 10 7 22

3 23

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 124

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

23

30 31

27 10 7 22

3 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 125

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

31

30 23

27 10 7 22

3 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 126

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

30 23

27 10 7 22

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 127

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

30

3 23

27 10 7 22

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 128

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

30

27 23

3 10 7 22

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 129

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

22

27 23

3 10 7 30

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 130

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

27

22 23

3 10 7 30

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 131

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

22 23

3 10 27 30

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 132

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

23

22 7

3 10 27 30

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 133

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

10

22 7

3 23 27 30

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 134

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

22

10 7

3 23 27 30

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 135

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

10 7

22 23 27 30

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 136

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

10

3 7

22 23 27 30

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 137

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

3 10

22 23 27 30

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 138

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

7 10

22 23 27 30

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 139

Les arbres parfaits

Tri Maximier (Tri par tas): Etape 2

Tableau trié:
41 30 31 27 10 7 22 3 23
3

7 10

22 23 27 30

31 41

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 140

Les arbres parfaits

Exercice d’application:

1. Donner la liste représantant l’arbre suivant:

2. Quel est l’indice de la racine ?
3. Si un nœud interne est situé à l'indice i, à quel indice est situé son fils gauche ? Son fils
droit ? Son père ?
4. Quel est le niveau d'un nœud d'indice i ?

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 141

Les arbres parfaits

Exercice d’application:

1. Donner la liste représantant l’arbre suivant:

20 7 12 3 6 11 9 1 2 4 5 8

2. Quel est l’indice de la racine ? 0

3. Si un nœud interne est situé à l'indice i, à quel indice est situé son fils gauche ? Son fils
droit ? Son père ?
1. 2i+1
2. 2i+2
3. (i-1)//2

4. Quel est le niveau d'un nœud d'indice i ?

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 142

 Les arbres binaires de recherche

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 143

Les arbres binaires de recherche

Les arbres binaires de recherche sont communément appelé ABR.

Les ABR sont des structures de données qui peuvent supporter des opérations
courantes (recherche, min, max, …) sur des ensembles dynamiques.

Un ABR a pour structure logique un arbre binaire.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 144

Les arbres binaires de recherche

Définition:

Un ABR est un arbre binaire tel que :

Pour tout nœud X :

• Les nœuds de son sous arbre-gauche s’ils en existent
ont des valeurs inférieures ou égales à celle de x
• Les nœuds de son sous arbre-droit des valeurs
strictement supérieures.

Ce que l’on traduit par g(A) <= racine(A) < d(A).

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 145

Les arbres binaires de recherche

Définition:

Tout sous-arbre d’un ABR est un ABR :

24

16 29

8 20 27 35

1 15

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 146

Les arbres binaires de recherche

Exercice d’application:
Parmi les arbres suivants, lesquels représentent un ABR ?

2 41
41

3
16 50
16 50
7
16 17 44 60
20 10 44 60
6 8

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 147

Les arbres binaires de recherche

Affichage dans l’ordre:

La propriété d’ABR permet d’afficher toutes les clés de l’arbre dans l’ordre
croissant à l’aide d’un algorithme récursif simple de parcours infixe.

41

Parcours infixe(Arbre A)
Si A est non vide Alors
16 50
Parcours infixe(Fils-g A)
Afficher l’étiquette de A // Valeur
Parcours infixe(Fils-d A)
16 17 44 60
FinSi

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 148

Les arbres binaires de recherche

Recherche récursive (Recherche dichotomique):

• Si le sous-arbre sélectionné est vide, on renvoie Faux.

• On compare l’égalité de l’élément avec la valeur de la racine , s’ils sont égaux

on renvoie Vrai

• Si la valeur est plus petite, on recommence récursivement dans le sous-arbre

gauche ; et réciproquement si la valeur est plus grande dans le sous-arbre
droit.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 149

Les arbres binaires de recherche

Recherche récursive (Recherche dichotomique):

Rechercher(x, Arbre A)
Si A est vide Alors
Retourner Faux
FinSi
Si x égale à l’étiquette de A Alors
Retourner Vrai
FinSi
Si x < à l’étiquette de A Alors
Retourner Rechercher(x, Fils-g A) 41
Sinon
Retourner Rechercher(x, Fils-d A)
FinSi
16 50

Exemple: Soit à rechercher 17 dans l'arbre suivant:

16 17 44 60

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 150

Les arbres binaires de recherche

Insertion et suppression:

• Les opérations d’insertion et de suppression modifient l’ensemble

dynamique représenté par un ABR.

• La structure de données doit être modifiée pour refléter ce changement tout

en conservant la propriété d’ABR.

• Modifier l’arbre pour y insérer un nouvel élément est relativement simple,

mais la suppression est un peu plus délicate à gérer.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 151

Les arbres binaires de recherche

Insertion:

• Le nouveau nœud ajouté devient une feuille.

• Il suffit de faire un parcours en profondeur en descendant systématiquement

à droite ou à gauche suivant qu’on est inférieur ou supérieur à la racine.
Insérer(x, Arbre A)
Si A est vide Alors
Retourner (x, vide, vide)
FinSi
Si x > à l’étiquette de A Alors
Fils-d A <- Insérer(x, Fils-d A)
Sinon
Fils-g A <- Insérer(x, Fils-g A)
FinSi
Retourner A
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 152
Les arbres binaires de recherche

Successeurs et prédécesseurs:

• Le successeur d’un nœud X est le nœud

possédant la plus petite étiquette supérieure à
l’étiquette de X. 41

• Le prédécesseur d’un nœud X est le nœud

possédant la plus grande étiquette inférieure à l’ 16 50

étiquette de X.
16 17 44 60
Exemples:
Le successeur de 41 : 44 19 20
Le prédécesseur de 19: 17
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 153
Les arbres binaires de recherche

Suppression:

Pour supprimer un nœud d’un arbre binaire de recherche, on distingue trois cas
à traiter :

• Cas 1: L’élément à supprimer n’a pas de fils  Il est terminal et il suffit de le

supprimer.

• Cas 2: L’élément a un fils unique  On supprime le nœud et on relie son fils

à son père.

• Cas 3: L’élément à supprimer a deux fils  On le remplace par son

successeur qui est toujours le minimum de ses descendants droits.
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 154
Les arbres binaires de recherche

Suppression:

Exemples:
3
3 3

2 6
2 6 2 6

1 4 7
1 4 7 1 4 7

5
5 5

Cas 1: Supprimer 1 Cas 2: Supprimer 2 Cas 3: Supprimer 3

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 155
Les arbres binaires de recherche

Suppression:

Exemples:
3
3 3

2 6
2 6 2 6

1 4 7
4 7 1 4 7

5
5 5

Cas 1: Supprimer 1 Cas 2: Supprimer 2 Cas 3: Supprimer 3

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 156
Les arbres binaires de recherche

Suppression:

Exemples:
3
3 3

2 6
2 6 1 6

1 4 7
4 7 1 4 7

5
5 5

Cas 1: Supprimer 1 Cas 2: Supprimer 2 Cas 3: Supprimer 3

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 157
Les arbres binaires de recherche

Suppression:

Exemples:
3
3 3

2 6
2 6 1 6

1 4 7
4 7 4 7

5
5 5

Cas 1: Supprimer 1 Cas 2: Supprimer 2 Cas 3: Supprimer 3

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 158
Les arbres binaires de recherche

Suppression:

Exemples:
4
3 3

2 6
2 6 1 6

1 4 7
4 7 4 7

5
5 5

Cas 1: Supprimer 1 Cas 2: Supprimer 2 Cas 3: Supprimer 3

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 159
Les arbres binaires de recherche

Suppression:

Exemples:
4
3 3

2 6
2 6 1 6

1 4 7
4 7 4 7

5
5 5

Cas 1: Supprimer 1 Cas 2: Supprimer 2 Cas 3: Supprimer 3

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 160
Les arbres binaires de recherche

Suppression:

Exemples:
4
3 3

2 6
2 6 1 6

1 5 7
4 7 4 7

5
5 5

Cas 1: Supprimer 1 Cas 2: Supprimer 2 Cas 3: Supprimer 3

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 161
Les arbres binaires de recherche

Suppression:

Exemples:
4
3 3

2 6
2 6 1 6

1 5 7
4 7 4 7

5 5

Cas 1: Supprimer 1 Cas 2: Supprimer 2 Cas 3: Supprimer 3

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 162
Les arbres binaires de recherche

Suppression:

Supprimer(x, Arbre A)
Si x < à l’étiquette de A Alors
Fils-g A <- Supprimer (x, Fils-g A)
Sinon Si x > à l’étiquette de A Alors
Fils-d A <- Supprimer (x, Fils-d A)
Sinon Si Fils-d est vide Alors
Retourner Fils-d A
Sinon Si Fils-g est vide Alors
Retourner Fils-g A
Sinon
Étiquette de A <- min(Fils-d A)
Fils-d A <- supprimer (Étiquette de A , Fils-d A)
FinSi
Retourner A

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 163

 Les graphes

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 164

Les graphes

Introduction:

Imaginez un réseau social ayant 6 abonnés (A, B, C, D, E et F) où :

A est ami avec B, C et D

B est ami avec A et D
C est ami avec A, E et D
D est ami avec tous les autres abonnés
E est ami avec C, D et F
F est ami avec E et D

On peut représenter chaque abonné par un cercle (avec le nom de l'abonné situé dans le
cercle) et chaque relation "X est ami avec Y" par un segment de droite reliant X et Y ("X est
ami avec Y" et "Y est ami avec X" étant représenté par le même segment de droite).

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 165

Les graphes

Introduction:

• Modéliser des relations entre un ensemble fini d’entités

• Chercher des propriétés, des interactions, ….

• Entités = sommets
• Relations binaires = non orientées / orientées / pondérées
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 166
Les graphes

L’origine des Graphes:

• Leonhard Euler : article 1735

• Problème des 7 ponts de Königsberg

Trouver une promenade partant d’un point donné, revenant à ce point et

passant une fois et une seul par chacun des 7 ponts de la ville.
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 167
Les graphes

Exemples des situations modélisées par un graphe:

Chaines alimentaires

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 168

Les graphes

Exemples des situations modélisées par un graphe:

Réseaux de transport

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 169

Les graphes

Exemples des situations modélisées par un graphe:

En informatique :

• Le web : chaque page est un sommet du graphe, chaque lien hypertexte est
une arête entre deux sommets.

• Le routage des réseaux informatiques

• Un réseau social : les sommets sont les personnes, deux personnes sont
adjacentes dans ce graphe lorsqu’elles sont “amies”. Si la notion d’amitié
n’est pas réciproque, le graphe est orienté.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 170

Les graphes

Exercice d’application:

Des étudiants A, B, C, D, E et F doivent passer des examens dans différentes

disciplines, chaque examen occupant une demi-journée :

– Algorithmique : étudiants A et B.
– Compilation : étudiants C et D.
– Bases de données : étudiants C, E, F et G.
– Java : étudiants A, E, F et H.
– Architecture : étudiants B, F, G et H.

Donner le nombre de demi-journées minimal pour organiser la session

d’examen la plus courte possible.
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 171
Les graphes

Exercice d’application:
Cette situation peut être modélisée à l’aide d’un graphe.

– Algorithmique : A et B.
Java – Compilation : C et D.
– Bases de données : C, E, F et G.
Algo BD Com – Java : A, E, F et H.
– Architecture : B, F, G et H.
Arch

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 172

Les graphes

Exercice d’application:
Cette situation peut être modélisée à l’aide d’un graphe.

– Algorithmique : A et B.
A Java EF – Compilation : C et D.
– Bases de données : C, E, F et G.
C
Algo
FH BD Com – Java : A, E, F et H.
– Architecture : B, F, G et H.
B
Arch FG

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 173

Les graphes

Exercice d’application:
Cette situation peut être modélisée à l’aide d’un graphe.

– Algorithmique : A et B.
A Java EF – Compilation : C et D.
– Bases de données : C, E, F et G.
C
Algo
FH BD Com – Java : A, E, F et H.
– Architecture : B, F, G et H.
B
Arch FG

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 174

Les graphes

Exercice d’application:
Cette situation peut être modélisée à l’aide d’un graphe.

A Java EF
Session 1:
BD : C, E, F, G
Algo
C Algo : A,B
FH BD Com

B Session 2:
Arch FG
Java : A, E, F, H
Comp : C

Session 3:
Arch : B, F, G, H

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 175

Les graphes

Définition:

Un graphe est une structure de données constituée d'objets, nommés sommets

et de relations entre ces sommets.

On peut classer les graphes en 2 catégories :

• Les graphes orientés

• Les graphes non orientés

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 176

Les graphes

Définition: graphe non orienté

Dans un graphe non orienté, les relations entre les sommets se nomment arêtes.

Un graphe est dit non orienté lorsque les arêtes ne sont pas dotées d'une direction
spécifique, ce qui signifie que si deux sommets sont reliés par une arête, on peut voyager de
l'un à l'autre dans les deux sens.

• Graphe :
• Ensemble des nœuds (sommets, nodes, vertices) :
• Ensemble des arêtes (edgs):
• Arête est relation binaire:
•
• La relation binaire caractérisée par A est symétrique.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 177

Les graphes

Exercice d’application:

x1 x2

x3 x4

Déterminer X et A.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 178

Les graphes

Définition: graphe orienté

Dans un graphe orienté, les relations entre les sommets se nomment arcs.

Un graphe est dit orienté lorsque les sommets sont reliés par des flèches, appelées arcs ou
arêtes orientées. Ce qui signifie que l'on peut voyager le long de l'arc uniquement dans le
sens déterminé par la flèche.

• Graphe :
• Ensemble des nœuds (sommets, nodes, vertices) :
• Ensemble des arcs :
• Arce est relation binaire orientés:
•
• La relation binaire caractérisée par A n’est pas symétrique.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 179

Les graphes

Définition: graphes étiquetés et pondérés

On appelle graphe étiqueté un graphe où chaque relation est affectée d'un

symbole.

Un graphe est dit pondéré lorsque les arêtes (arcs) ont un poids ou une valeur
numérique positive. Ces poids représentent une mesure telle que la distance, le
coût, la capacité, ou toute autre quantité pertinente entre les sommets qu'elles
relient.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 180

Les graphes

Terminologies

Deux sommets d'un graphe sont dits adjacents s'il existe une arête (ou un arc)
qui les relie.

L’ordre d’un graphe est le nombre de ses sommets.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 181

Les graphes

Terminologies

Degré d’un sommet : nombre d’arêtes reliées à ce sommet.

Chaîne : Une chaine de longueur n est une suite de n

arêtes qui relient un sommet i à un autre j ou à lui-même.
Exemple:
Des chaînes de longueur 2 : ABC, DCA

Chemin : c’est une chaine bien orientée

Exemple:
B C D E est un chemin
C B A n’est pas un chemin
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 182
Les graphes

Terminologies

Une chaine ou un chemin est dit élémentaire si il ne comporte pas plusieurs fois
le même sommet.

Un chemin (chaîne) dont le sommet de début est le même que le sommet de

fin est appelé un circuit (Cycle).

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 183

Les graphes

Terminologies
Un graphe non-orienté est dit connexe lorsqu'il existe une chaîne reliant deux sommets
quelconques.

1 1 6

2 2
Graphe non-connexe
Graphe connexe
3 5 3 5
4
4
Un graphe non-orienté non-connexe se décompose en composantes connexes. Dans
l'exemple ci-dessus, le graphe non-connexe possède deux composantes connexes : {1,2,3,5}
et {4,6}.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 184

Les graphes

Terminologies

Un graphe orienté est dit fortement connexe lorsque pour toute paire de
sommets distincts (A,B) il existe un chemin de A vers B et de B vers A.

A
D

B
C

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 185

Les graphes

Implémentation

Les sommets d’un graphe peuvent représenter n’importe quel type de donnée.

Le choix d’une représentation plutôt qu’une autre dépend des usages que l’on
souhaite faire du graphe (construction, parcours, …)

Deux implémentations possibles :

1. Par les dictionnaires de précédence

2. Par la matrice d’adjacences

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 186

Les graphes

Implémentation: dictionnaire de précédence

Un dictionnaire de précédence associe chaque sommet d’un graphe à ses

voisins, sous forme d’une liste (dictionnaire ou un ensemble).
Graphe non orienté Graphe orienté
G={ G={
'A' : ['B', 'C'], 'A' : ['B'],
'B' : ['A', 'C'], 'B' : ['C'],
'C' : ['A', 'B', 'D'], 'C' : ['A', 'D'],
'D' : ['C', 'E'], 'D' : ['E'],
'E' : ['D’] 'E' : []
} }

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 187

Les graphes

Implémentation: dictionnaire de précédence

Dans le cas d’un graphe contenant de très nombreuses arêtes, le dictionnaire

sera moins avantageux en termes d’occupation mémoire que la matrice
d’adjacence.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 188

Les graphes

Exercice d’application

Donner l’implémentation avec le dictionnaire de précédence du graphe suivant:

G= {
'A' : ['B', 'D'],
'B' : ['D'],
'C : ['B'],
'D' : ['B', 'C']
}

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 189

Les graphes

Implémentation: matrice d’adjacence

Soit un graphe de sommets, d’indices .

La matrice d’adjacence de ce graphe est un tableau A à deux dimensions, de

taille , contenant des booléens indiquant si il y a adjacence entre les
sommets d’indices et .

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 190

Les graphes

Implémentation: matrice d’adjacence

Graphe non orienté :

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 191

Les graphes

Implémentation: matrice d’adjacence

Graphe orienté :

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 192

Les graphes

Implémentation: matrice d’adjacence

Graphe orienté :

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 193

Les graphes

Exercice d’application

Donner l’implémentation avec la matrice d’adjacence du graphe suivant:

A B C D

A 0 1 0 1
B 0 0 0 1

C 0 1 0 0
D 0 1 1 0

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 194

Les graphes

Implémentation: matrice d’adjacence

La dimension de la matrice est égale au carré du nombre de sommets (N×N), ce

qui peut représenter un important espace en mémoire.

Pour obtenir les voisins d’un sommet, il faut une utiliser une fonction de coût
d’ordre O(n).

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 195

Les graphes

Parcours d’un graphe:

Il existe 2 méthodes pour parcourir un graphe :

• Le parcours en largeur d'abord

• Le parcours en profondeur d'abord

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 196

Les graphes

Parcours d’un graphe: parcours en largeur

Ce parcours peut être utilisé pour :

• Chemin plus court entre deux sommets

• Vérifier si un graphe est connexe

Principe d’algorithme :
1. S est le sommet de départ
2. Cet algorithme liste d'abord les voisins de S pour ensuite les explorer un par
un.
3. Répétez (1) pour chaque voisin.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 197

Les graphes

Parcours d’un graphe: parcours en largeur

Illustration:

La liste de sommets visités est: A,

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 198

Les graphes

Parcours d’un graphe: parcours en largeur

Illustration:

La liste de sommets visités est: A, B

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 199

Les graphes

Parcours d’un graphe: parcours en largeur

Illustration:

La liste de sommets visités est: A, B, C

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 200

Les graphes

Parcours d’un graphe: parcours en largeur

Illustration:

La liste de sommets visités est: A, B, C, F, D

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 201

Les graphes

Parcours d’un graphe: parcours en largeur

Illustration:

La liste de sommets visités est: A, B, C, F, D, E

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 202

Les graphes

Parcours d’un graphe: parcours en largeur

Illustration:

La liste de sommets visités est: A, B, C, F, D, E, G.

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 203

Les graphes

Parcours d’un graphe: parcours en profondeur

Ce parcours peut être utilisé pour :

➢Chemin plus court entre deux sommets
➢Vérifier si un graphe est connexe

Principe d’algorithme :
Recherche qui progresse à partir d'un sommet S en s'appelant récursivement
pour chaque sommet voisin de S.

Pour chaque sommet, il prend le premier sommet voisin jusqu'à ce qu'un

sommet n'aie plus de voisins (ou que tous ses voisins soient marqués), et
revient alors au sommet père.
Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 204
Les graphes

Parcours d’un graphe: parcours en profondeur

Illustration:

La liste de sommets visités est: A,

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 205

Les graphes

Parcours d’un graphe: parcours en profondeur

Illustration:

La liste de sommets visités est: A, B,

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 206

Les graphes

Parcours d’un graphe: parcours en profondeur

Illustration:

La liste de sommets visités est: A, B, D,

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 207

Les graphes

Parcours d’un graphe: parcours en profondeur

Illustration:

La liste de sommets visités est: A, B, D, G,

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 208

Les graphes

Parcours d’un graphe: parcours en profondeur

Illustration:

La liste de sommets visités est: A, B, D, G, F,

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 209

Les graphes

Parcours d’un graphe: parcours en profondeur

Illustration:

La liste de sommets visités est: A, B, D, G, F,

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 210

Les graphes

Parcours d’un graphe: parcours en profondeur

Illustration:

La liste de sommets visités est: A, B, D, G, F, E,

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 211

Les graphes

Parcours d’un graphe: parcours en profondeur

Illustration:

La liste de sommets visités est: A, B, D, G, F, E, C

B
F

A D G

C
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 212

Les graphes

Plus courts chemins :

Le problème du Plus Court Chemin (PCC) compte parmi les problèmes le plus
classiques de la théorie des graphes et les plus importants dans leurs
applications.

• Optimisation de réseaux routiers

• Optimisation de réseaux télécommunication
• Navigation des robots

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 213

Les graphes

Plus courts chemins :

• Graphes pondéré : Distance, Temps, ….

• Cout d’un chemin/chaine: Somme des valuations des arcs/arêtes qui le

composent.

• Chercher un chemin (chaine) de cout minimal entre deux sommets donnés

sur un graphe pondéré (1 vers 1)

• Chercher les chemins (chaines) de cout minimal entre 1 sommet donné et

tous les autres sur un graphe pondéré (1 vers n)

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 214

Les graphes

Plus courts chemins : Condition Nécessaire

Le problème du PCC a une solution si et seulement s’il n'existe pas dans le

graphe de circuit de longueur strictement négative pouvant être atteint à partir
de l’origine (s).

Un circuit négatif est appelé circuit absorbant.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 215
Les graphes

Plus courts chemins : Condition d’Optimalité

Les sous-chemins des plus courts chemins sont des plus courts chemins.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 216

Les graphes

Plus courts chemins : Algorithme de Dijkstra

Cet algorithme permet de calculer le PCC d’un sommet «s » à un sommet « d »

ou d’un sommet « s » à tous les autres sommets dans un graphe.

Graphes orientés et Graphes non orientés

Le graphe est connexe ne comporte pas de circuit/cycle de longueur négative.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 217

Les graphes

Plus courts chemins : Algorithme de dijkstra (Principe)

• Label :
• Cout du chemin à l’origine s = 0
• Cout du chemin aux autres sommets ← ∞

• Adaptation d’un parcours en largeur:

• A chaque étape :
1. Sélectionner le sommet de cout le plus faible et marquer ce
sommet comme visité (son cout ne changera plus)
2. Actualiser les couts des sommets adjacents non marqués

• Arrêt : Tous les sommets sont marqués

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 218
Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3
F
1 2 3 4
A 3 G
D
3 2
2 5
C 4
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 219

Les graphes

Plus courts chemins : Algorithme de dijkstra

Règles pour remplir les cases de chaque cellule:

Soit e le sommet de départ.

1. La valeur de chaque cellule est un couple : (d(v), p(v))

Où : d(v) est la distance minimale du sommet de départ e au sommet v et p(v)

représente le sommet précédent du chemin optimal reliant e et v.

1. d(e)=0 (e est le sommet de départ)

2. d(v)=∞ si la distance est non encore calculé

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 220

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3
F
1 2 3 4
A 3 G
D
3 2
2 5
C 4
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 221

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0
F
1 2 3 4
A 3 G
D
3 2
2 5
C 4
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 222

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞
F
1 2 3 4
A 3 G
D
3 2
2 5
C 4
E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 223

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 X
3 4
A D
3 G X
X
3 2
2 5 X
C 4
E X
X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 224

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A)
3 4
A D
3 G X
X
3 2
2 5 X
C 4
E X
X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 225

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞
3 4
A D
3 G X
X
3 2
2 5 X
C 4
E X
X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 226

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G X X
X X
3 2
2 5 X X
C 4
E X X
X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 227

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (3,B) (4,B)
X X
3 2
2 5 X X
C 4
E X X
X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 228

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞
X X
3 2
2 5 X X
C 4
E X X
X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 229

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
X X X
3 2
2 5 X X X
C 4
E X X X
X X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 230

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
Etape 4 X X X (5,C)
3 2
2 5 X X X
C 4
E X X X
X X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 231

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
Etape 4 X X X (3,B)
3 2
2 5 X X X
C 4
E X X X
X X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 232

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
Etape 4 X X X (3,B) (6,C)
3 2
2 5 X X X
C 4
E X X X
X X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 233

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
Etape 4 X X X (3,B) (6,C) (4,B) ∞
3 2
2 5 X X X
C 4
E X X X
X X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 234

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
Etape 4 X X X (3,B) (6,C) (4,B) ∞ D(3)
3 2
2 5 X X X X
C 4
E X X X X
X X X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 235

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
Etape 4 X X X (3,B) (6,C) (4,B) ∞ D(3)
3 2
2 5 Etape 5 X X X X (6,C)
C 4
E X X X X
X X X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 236

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
Etape 4 X X X (3,B) (6,C) (4,B) ∞ D(3)
3 2
2 5 Etape 5 X X X X (5,D) (4,B) (6,D)
C 4
E X X X X
X X X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 237

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
Etape 4 X X X (3,B) (6,C) (4,B) ∞ D(3)
3 2
2 5 Etape 5 X X X X (5,D) (4,B) (6,D) F(4)
C 4
E X X X X X
X X X X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 238

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
Etape 4 X X X (3,B) (6,C) (4,B) ∞ D(3)
3 2
2 5 Etape 5 X X X X (5,D) (4,B) (6,D) F(4)
C 4
E Etape 6 X X X X (5,D) X (6,D)
X X X X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 239

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
Etape 4 X X X (3,B) (6,C) (4,B) ∞ D(3)
3 2
2 5 Etape 5 X X X X (5,D) (4,B) (6,D) F(4)
C 4
E Etape 6 X X X X (5,D) X (6,D) E(5)
X X X X X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 240

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
Etape 4 X X X (3,B) (6,C) (4,B) ∞ D(3)
3 2
2 5 Etape 5 X X X X (5,D) (4,B) (6,D) F(4)
C 4
E Etape 6 X X X X (5,D) X (6,D) E(5)
Etape 7 X X X X X X

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 241

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
Etape 4 X X X (3,B) (6,C) (4,B) ∞ D(3)
3 2
2 5 Etape 5 X X X X (5,D) (4,B) (6,D) F(4)
C 4
E Etape 6 X X X X (5,D) X (6,D) E(5)
Etape 7 X X X X X X (6,D)

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 242

Les graphes

Plus courts chemins : Algorithme de dijkstra

Exemple : Trouver le chemin optimal entre A et G

Etapes A B C D E F G Choix
B 3 Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ A(0)
F
1 2 Etape 2 X (1,A) (2,A) ∞ ∞ ∞ ∞ B(1)
3 4
A D
3 G Etape 3 X X (2,A) (3,B) ∞ (4,B) ∞ C(2)
Etape 4 X X X (3,B) (6,C) (4,B) ∞ D(3)
3 2
2 5 Etape 5 X X X X (5,D) (4,B) (6,D) F(4)
C 4
E Etape 6 X X X X (5,D) X (6,D) E(5)
Etape 7 X X X X X X (6,D) G(6)

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 243

Les graphes

Exercice d’application

Trouver le plus court chemin entre A et H

16 G
B
12
11
9
A 21
10
C F H
14 11
16
13
D
10
10 E

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 244

Les graphes

Exercice d’application

Trouver le plus court chemin entre A et H: A - B - F - H

Etapes A B C D E F G H Choix
Etape 1 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ A(0)
Etape 2 X (12,A) ∞ (14,A) ∞ ∞ ∞ ∞ B(12)
Etape 3 X X ∞ (14,A) ∞ (21,B) (28,B) (33,B) D(14)
Etape 4 X X ∞ X (24,D) (21,B) (28,B) (33,B) F(21)
Etape 5 X X (31,F) X (24,D) X (28,B) (32,F) E(24)
Etape 6 X X (31,F) X X X (28,B) (32,F) G(28)
Etape 7 X X (31,F) X X X X (32,F) C(31)
Etape 8 X X X X X X X (32,F) H(32)

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 245

Les graphes

Exercice d’application : graphe orienté

Trouver le plus court chemin de A vers tous les sommets

1
F
B
10
A–B A → C → B (8)
3 9
A 2 A–C A → C (5)
5
4 A–F A → C → B → F (11)
5
A–D A → C → D (7)
C D
2
3

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 246

Les graphes

Plus courts chemins : Algorithme de Bellman

Cet algorithme permet de calculer le PCC d’un sommet «s » à un sommet « d »

ou d’un sommet « s » à tous les autres sommets dans un graphe orienté sans
circuit de pondération quelconque.

Sommet d’origine doit être sans prédécesseur.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 247

Les graphes

Plus courts chemins : Algorithme de Bellman (Principe)

1. Initialisation: La phase d'initialisation consiste à définir les coûts initiaux des chemins :
• Cost_0(e) = 0 : Le coût du chemin du sommet de départ e à lui-même est 0.
• Cost_0(x) = ∞: Le coût initial de tous les autres sommets est infini .

2. Récurrence
Cost_k(x) = MIN (Cost_k-1(x), Cost_k-1(y) + W(y, x) ), pour tout y prédécesseur de x.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 248

Les graphes

Plus courts chemins : Algorithme de Bellman (Principe)

• Calcul incrémental de Cost_k(x)

• Arrêt :
• Les couts n’évoluent pas
• Un nombre maximal d’itérations est atteint

En effet, si le graphe ne contient pas de circuit absorbant:

• Un chemin solution comportera au plus n-1 arcs (arêtes) car on ne recherche
que des chemins élémentaires.

• Si le nombre d’itérations atteint n alors un circuit absorbant a été détecté.

Analyse et conception des algorithmes ENSIASD - TAROUDANT 249
Les graphes

Plus courts chemins : Algorithme de Bellman

1
D
B
6 Iteration A B C D E
8 0
A 2
1
1 -5
2
3
3
C E
2 4

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 250

Les graphes

Plus courts chemins : Algorithme de Bellman

1
D
B
6 Iteration A B C D E
8 0 0 ∞ ∞ ∞ ∞
A 2
1 0
1 -5
2 0
3
3 0
C E
2 4 0

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 251

Les graphes

Plus courts chemins : Algorithme de Bellman

1
D
B
6 Iteration A B C D E
8 0 0 ∞ ∞ ∞ ∞
A 2
1 0 6
1 -5
2 0
3
3 0
C E
2 4 0

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 252

Les graphes

Plus courts chemins : Algorithme de Bellman

1
D
B
6 Iteration A B C D E
8 0 0 ∞ ∞ ∞ ∞
A 2
1 0 6 3
1 -5
2 0
3
3 0
C E
2 4 0

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 253

Les graphes

Plus courts chemins : Algorithme de Bellman

1
D
B
6 Iteration A B C D E
8 0 0 ∞ ∞ ∞ ∞
A 2
1 0 6 3 ∞ ∞
1 -5
2 0
3
3 0
C E
2 4 0

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 254

Les graphes

Plus courts chemins : Algorithme de Bellman

1
D
B
6 Iteration A B C D E
8 0 0 ∞ ∞ ∞ ∞
A 2
1 0 6 3 ∞ ∞
1 -5
2 0 5 3
3
3 0
C E
2 4 0

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 255

Les graphes

Plus courts chemins : Algorithme de Bellman

1
D
B
6 Iteration A B C D E
8 0 0 ∞ ∞ ∞ ∞
A 2
1 0 6 3 ∞ ∞
1 -5
2 0 5 3 14
3
3 0
C E
2 4 0

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 256

Les graphes

Plus courts chemins : Algorithme de Bellman

1
D
B
6 Iteration A B C D E
8 0 0 ∞ ∞ ∞ ∞
A 2
1 0 6 3 ∞ ∞
1 -5
2 0 5 3 14 7
3
3 0
C E
2 4 0

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 257

Les graphes

Plus courts chemins : Algorithme de Bellman

1
D
B
6 Iteration A B C D E
8 0 0 ∞ ∞ ∞ ∞
A 2
1 0 6 3 ∞ ∞
1 -5
2 0 5 3 14 7
3
3 0 5 3 13 6
C E
2 4 0

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 258

Les graphes

Plus courts chemins : Algorithme de Bellman

1
D
B
6 Iteration A B C D E
8 0 0 ∞ ∞ ∞ ∞
A 2
1 0 6 3 ∞ ∞
1 -5
2 0 5 3 14 7
3
3 0 5 3 13 6
C E
2 4 0 5 3 13 6

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 259

Les graphes

Plus courts chemins : Algorithme de Bellman

Reconstruction des PCC

Si la distance à un sommet v est modifiée à l’étape i :

Distance(v) = Distance(u)+ w(u, v): alors mémoriser u, dernier sommet

intermédiaire pred[v] = u.

Quand l’algorithme est terminé :

• Le graphe constitué des arcs (pred[v], v) est un arbre,
• Dans ce graphe, le chemin entre s et v est un plus court chemin dans G.

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 260

Les graphes

Plus courts chemins : Algorithme de Bellman

Reconstruction des PCC

1
D
B
6 Iteration A B C D E
8 0 0 ∞ ∞ ∞ ∞
A 2
1 0 6 3 ∞ ∞
1 -5
2 0 5 3 14 7
3
3 0 5 3 13 6
C E
2 4 0 5 3 13 6
Pred - C A B B

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 261

Les graphes

Exercice d’application

s
-3 3
4 2

d e
9 -1 -2 -3

a b c
-4 8

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 262

Les graphes

Exercice d’application

s
-3 3 Iteration s a b c d e
4 2
0 0 ∞ ∞ ∞ ∞ ∞
d e 1 0 -3 ∞ -3 4 2
9 -1 -2 -3 2 0 -3 0 -3 4 0
3 0 -4 -2 -3 4 0
a b c
8 4 0 -6 -2 -3 4 0
-4
5 0 -6 -2 -3 3 0
Pred - b e s a c

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 263

Les graphes

Exercice d’application

s
-3 3 Iteration s a b c d e
4 2
0 0 ∞ ∞ ∞ ∞ ∞
d e 1 0 -3 ∞ -3 4 2
9 -1 -2 -3 2 0 -3 0 -3 4 0
3 0 -4 -2 -3 4 0
a b c
8 4 0 -6 -2 -3 4 0
-4
5 0 -6 -2 -3 3 0
Pred - b e s a c

Mohammed KASRI Analyse et conception des algorithmes ENSIASD - TAROUDANT 264