Conception des algorithmes

Hicham Bensaid

Département RIM

Hicham Bensaid (Département RIM) Conception des algorithmes 1 / 77

Introduction

En première partie, nous avons traité les notions suivantes :

Algorithmes,
algorithmique et
structures de données.
⇒ analyser des algorithmes existants.
Dans cette partie nous allons apprendre certaines stratégies de
conception des algorithmes.
Le cours est largement fondé sur (et inspiré de) les livres :
Fundamentals of Algorithmics, G. Brassard and P. Bratley
Introduction to Algorithms, Third Edition, T. H. Cormen, C. E.
Leiserson, R. L. Rivest and C. Stein

Hicham Bensaid (Département RIM) Conception des algorithmes 2 / 77

Plan

1 Motivations

2 Programmation dynamique
Dégroupage optimal
Multiplication optimale d’une chaine de matrices

3 Algorithmes gloutons

4 Diviser pour régner

Tri par fusion
Tri rapide (quicksort)

Hicham Bensaid (Département RIM) Conception des algorithmes 3 / 77

 Motivations

Plan

1 Motivations

2 Programmation dynamique
Dégroupage optimal
Multiplication optimale d’une chaine de matrices

3 Algorithmes gloutons

4 Diviser pour régner

Tri par fusion
Tri rapide (quicksort)

Hicham Bensaid (Département RIM) Conception des algorithmes 4 / 77

 Motivations

Stratégies

Nous allons aborder 3 techniques importantes de conception des

algorithmes :
Programmation dynamique
Algorithmes gloutons
Diviser pour régner
Nous avons déjà vu (en première partie) d’autres techniques :
Approche incrémentale (tri par insertion)
Exploitation des propriétés des S.D.
Récurrence

Hicham Bensaid (Département RIM) Conception des algorithmes 5 / 77

 Motivations

Exemple introductif
Terme général de la suite de Fibonacci :
(
n si n ∈ {0, 1}
Fn =
F n−1 + F n−2 si n ≥ 2

Implémentation récursive 4
simple
w '
Mais complexité 3 2

exponentielle  
2 1 1 0

La cause : les mêmes 

calculs répétés plusieurs 1 0

fois
Nous allons voir comment faire de manière plus efficace (et plus
intelligente)

Hicham Bensaid (Département RIM) Conception des algorithmes 6 / 77

 Programmation dynamique

Plan

1 Motivations

2 Programmation dynamique
Dégroupage optimal
Multiplication optimale d’une chaine de matrices

3 Algorithmes gloutons

4 Diviser pour régner

Tri par fusion
Tri rapide (quicksort)

Hicham Bensaid (Département RIM) Conception des algorithmes 7 / 77

 Programmation dynamique

Programmation dynamique

Résout les problèmes en combinant les solutions des sous problèmes

(un peu comme diviser pour régner)
Utile quand les sous problèmes chevauchent (contrairement à DpR)
Utile quand on peut exhiber une structure de sous problèmes optimaux
La programmation dynamique résout chaque problème 1 seule fois et
stocke le résultat pour d’autre usages (d’où l’intérêt du
chevauchement)
Utile dans les problèmes d’optimisation (mais pas que, cf. suite de
Fibonacci)

Hicham Bensaid (Département RIM) Conception des algorithmes 8 / 77

 Programmation dynamique

Étapes de la programmation dynamique

1 Caractériser la structure d’une solution optimale

2 Définir récursivement la valeur d’une solution optimale
3 Calculer la valeur d’une solution optimale
4 Construire une solution optimale à partir de la valeur (info) calculée

Hicham Bensaid (Département RIM) Conception des algorithmes 9 / 77

 Programmation dynamique

Programmation dynamique à travers l’exemple

Nous allons étudier cette technique à travers deux exemples :

Problème du dégroupage optimal de la bande passante
Problème de multiplication optimale de plusieurs matrices

Hicham Bensaid (Département RIM) Conception des algorithmes 10 / 77

 Programmation dynamique Dégroupage optimal

Premier exemple : dégroupage optimal de la bande passante

Une bande passante d’un opérateur à partager avec un ou plusieurs

concurrents
En dégroupant, chaque “morceau” de bande passante a un prix de
session
Comment maximiser le gain (la somme des prix) après dégroupage ?

largeur B.P. i 1 2 3 4 5 6 7 8 9 10
prix p i 1 5 8 9 10 17 17 20 24 30

Hicham Bensaid (Département RIM) Conception des algorithmes 11 / 77

 Programmation dynamique Dégroupage optimal

Dégroupage optimal

Exemple : bande passante de largeur = 4

La solution optimale dans ce cas est de partager en 2 sous-bandes de

largeurs identiques = 2
Le gain maximal = 5 + 5 = 10
Le problème : algorithme pour résoudre le problème (et non pas l’instance)

Hicham Bensaid (Département RIM) Conception des algorithmes 12 / 77

 Programmation dynamique Dégroupage optimal

Dégroupage optimal

1ère solution (naïve) : énumérer tous les dégroupages possibles

Problème : complexité exponentielle. Il y a 2n−1 dégroupages possibles
(il existe 2n−1 applications de l’ensemble {0, 1} (couper / ne pas couper)
dans l’ensemble {1, 2, . . . , n − 1})
Sinon ... on analyse le problème
caractériser
¡
la solution optimale : ¢
r n = max p n , r 1 + r n−1 , r 2 + r n−2 , . . . , r n−1 + r 1
Problème initial décomposé en plusieurs problèmes similaires mais sur
des instances plus petites
la solution optimale globale utilise des solutions optimales des sous
problèmes définis (solvables indépendamment)
⇒ Le problème de découpe optimale présente une sous structure
optimale
¡ ¢
r n peut être encore simplifiée : r n = max p i + r n−i

Hicham Bensaid (Département RIM) Conception des algorithmes 13 / 77

 Programmation dynamique Dégroupage optimal

Solution récursive
¡ ¢
La formule r n = max p i + r n−i suggère d’utiliser diviser pour régner
(solution récursive)
Entrée : un tableau p et un entier n indiquant la largeur où "couper"
Résultat : le gain maximum
1 function degrouperBPRec(p, n )
2 if n == 0 then
3 return 0
4 q = −∞
5 for i = 1 to n¡ do ¢
6 q = max q, p[i ] + degrouperBPRec(p, n − i )
7 return q
Algorithme 1 : degrouperBPRec
Complexité ?

Hicham Bensaid (Département RIM) Conception des algorithmes 14 / 77

 Programmation dynamique Dégroupage optimal

Analyse de la complexité de la solution récursive

On caractérise T (n) le coût de recherche d’une solution optimale sur une
bande passante de largeur n :
Pn−1
T (n) = 1 + i =0 T (i )
Pn−1 Pn−1
T (n) + i =0 T (i ) = 1 + 2. i =0 T (i )

S(n) = 1 + 2.S(n − 1) ⇒ S ′ (n) = 2.S ′ (n − 1)

Pn−1
S ′ (n) = 2n et donc S(n) = 2n − 1 et T (n) + i =0 T (i ) = 2n − 1
Pn−1
donc 2.T (n) =2n (puisque 1 + i =0 T (i ) = T (n))

finalement T (n) = 2n−1

⇒ Complexité exponentielle
Hicham Bensaid (Département RIM) Conception des algorithmes 15 / 77
 Programmation dynamique Dégroupage optimal

La programmation dynamique à la rescousse

Le problème avec DpR : on calcule la même chose plusieurs fois :

4
 &
t + 1
3 2 0
 %   
u
2 1 0 1 0 0
   
1 0 0 0

0

Solution : faire en sorte de ne le faire qu’une fois

Hicham Bensaid (Département RIM) Conception des algorithmes 16 / 77

 Programmation dynamique Dégroupage optimal

Approches

Approche top-down : utilise la technique de mémoïsation

une fois une valeur calculée, on la mémorise (dans un tableau par
exemple) pour usage ultérieur
⇒ pas besoin de recalculer

Approche bottom-up : repose sur une relation d’ordre sur la taille du

sous problème :
dans l’exemple précédent le calcul de r k nécessite le calcul de tous les
r i tels que i < k
⇒ on calcule r 0 ensuite r 1 puis r 2 puis r 3 , . . .
⇒ notion de tri topologique

Hicham Bensaid (Département RIM) Conception des algorithmes 17 / 77

 Programmation dynamique Dégroupage optimal

Version mémoïsée
Entrée : un tableau p et un entier n indiquant la largeur où couper et un
tableau r
Résultat : le gain maximum
1 function degrouperBPMemAux(p, n, r )
2 if r [n] ≥ 0 then
3 return r [n]
4 if n == 0 then
5 q =0
6 else
7 q = −∞
8 for i = 1 to n¡ do ¢
9 q = max q, p[i ] + degrouperBPMemAux(p, n − i , r )
10 r [n] = q
11 return q
Algorithme 2 : degrouperBPMemAux
Hicham Bensaid (Département RIM) Conception des algorithmes 18 / 77
 Programmation dynamique Dégroupage optimal

Version mémoïsée

Entrée : un tableau p et un entier n indiquant la largeur de la B. P.

Résultat : le gain maximum
1 function degrouperBPMem(p, n )
2 Soit r [0..n] un nouveau tableau
3 for i = 1 to n do
4 r [i ] = −∞
5 return degrouperBPMemAux(p, n, r )
Algorithme 3 : degrouperBPMem

Complexité en O n 2
¡ ¢

Hicham Bensaid (Département RIM) Conception des algorithmes 19 / 77

 Programmation dynamique Dégroupage optimal

Version bottom-up

Entrée : un tableau p et un entier n indiquant la largeur de la bande

Résultat : le gain maximum
1 function degrouperBPBotUp(p, n, r )
2 Soit r [0..n] un nouveau tableau
3 r [0] = 0
4 for j = 1 to n do
5 q = −∞
6 for i = 1 to j¡ do ¢
7 q = max q, p[i ] + r [ j − 1]
8 r [j] = q
9 return r [n]
Algorithme 4 : degrouperBPBotUp

Complexité en O n 2
¡ ¢

Hicham Bensaid (Département RIM) Conception des algorithmes 20 / 77

 Programmation dynamique Multiplication optimale d’une chaine de matrices

Deuxième exemple : multiplication optimale d’une chaine de

matrices

Une chaine de n matrices 〈A 1 , A 2 , . . . , A n 〉 à multiplier et on veut

calculer le produit A 1 A 2 . . . A n
On peut utiliser l’algorithme standard de multiplication de deux
matrices
Il faut choisir un parenthésage pour appliquer l’algorithme
Plusieurs manières de parenthéser (la multiplication de matrices est
associative) conduisant au même résultat
Un produit de matrices est complètement parenthésé ssi
une seule matrice ou
produit de deux matrices complètement parenthésées

Hicham Bensaid (Département RIM) Conception des algorithmes 21 / 77

 Programmation dynamique Multiplication optimale d’une chaine de matrices

Exemple

Chaine à multiplier : 〈A 1 , A 2 , A 3 , A 4 〉
5 manières de parenthéser le produit A 1 A 2 A 3 A 4 :(pourquoi 5 ?,
comment généraliser pour n ?)
(A 1 (A 2 (A 3 A 4 )))
(A 1 ((A 2 A 3 ) A 4 ))
((A 1 A 2 ) (A 3 A 4 ))
((A 1 (A 2 A 3 )) A 4 )
(((A 1 A 2 ) A 3 ) A 4 )
Comment parenthéser peut impacter de manière drastique la
complexité globale du calcul du produit.

Hicham Bensaid (Département RIM) Conception des algorithmes 22 / 77

 Programmation dynamique Multiplication optimale d’une chaine de matrices

Algorithme simple de multiplication de deux matrices

Entrée : deux matrices A et B à multiplier

Résultat : le produit A.B si A et B sont compatibles
1 function produitDeuxMatrices( A, B )
2 Soit C = (ci j ) une nouvelle matrice de taille A.l i g nes × [Link] onnes
3 if [Link] onnes 6= B.l i g nes then
4 error "Matrices incompatibles"
5 else
6 for i = 1 to A.l i g nes do
7 for j = 1 to [Link] onnes do
8 ci j = 0
9 for k = 1 to [Link] onnes do
10 c i j = c i j + (a i k .b k j )

11 return C
Algorithme 5 : produitDeuxMatrices

Temps d’exécution : ≈ n × m × k où n, m, k resp. A.l i g nes , [Link] onnes ,

[Link] onnes
Hicham Bensaid (Département RIM) Conception des algorithmes 23 / 77
 Programmation dynamique Multiplication optimale d’une chaine de matrices

Parenthétisation et complexité

Produit de la chaine 〈A 1 , A 2 , A 3 〉 avec A 1 : 10 × 100, A 2 : 100 × 5, A 3 : 5 × 50

Temps d’exécution :
(A 1 (A 2 A 3 )) : (100 × 5 × 50) + (10 × 100 × 50) = 75000 opérations (à peu
près)
((A 1 A 2 ) A 3 ) : (10 × 100 × 5) + (10 × 5 × 50) = 7500 opérations (à peu près)

On peut aller 10 fois plus vite (ou 10 fois plus lentement) en fonction du
parenthésage ! ! !

Hicham Bensaid (Département RIM) Conception des algorithmes 24 / 77

 Programmation dynamique Multiplication optimale d’une chaine de matrices

Problème de multiplication d’une chaine de matrices

Problème
Etant donnée une chaine de matrices 〈A 1 , A 2 , . . . , A n 〉 où chaque A i est de
dimensions p i −1 × p i , parenthéser complètement le produit A 1 A 2 . . . A n de
manière à minimer le nombre de multiplications scalaires.

Attention
On ne procède pas à une multiplication des matrices mais uniquement
à determiner un parenthésage (ordre de multiplication) qui minimise le
nombre de multiplications scalaires (et donc le temps d’exécution)
Le temps nécessaire pour déterminer le parenthésage est largement
compensé par la réduction du temps de calcul du produit lui même (un
facteur de 10 dans l’exemple)

Hicham Bensaid (Département RIM) Conception des algorithmes 25 / 77

 Programmation dynamique Multiplication optimale d’une chaine de matrices

Première solution (naïve)

Essayer de manière exhaustive toutes les parenthétisations possibles

Problème : solution très inneficace :
P (n) : le nombre
 de parenthétisations possibles d’une chaine de taille n

1 si n = 1
P (n) = n−1
X
 P (k)P (n − k) si n ≥ 2

k=1
On peut démontrer que P (n) = Ω(2n ) (idée : a.b ≥ a + b + 1 et
récurrence)
⇒ solution non satisfaisante

Hicham Bensaid (Département RIM) Conception des algorithmes 26 / 77

 Programmation dynamique Multiplication optimale d’une chaine de matrices

La programmation dynamique à la rescousse

Utiliser la programmation dynamique pour résoudre le problème en utilisant

l’approche en 4 étapes :
1 Caractériser la structure d’une solution optimale
2 Définir la valeur de la solution optimale de manière récursive
3 Calculer la valeur de la solution optimale
4 Construire la solution optimale depuis l’information calculée

Hicham Bensaid (Département RIM) Conception des algorithmes 27 / 77

 Programmation dynamique Multiplication optimale d’une chaine de matrices

1. Structure de la parenthétisation optimale

On doit trouver la sous structure optimale et l’utiliser pour construire
une solution optimale au problème à partir des solutions optimales des
sous problèmes.
Pour notre exemple on note A i .. j où i ≤ j matrice du produit
A i A i +1 . . . A j .
Dans le cas non trivial (i < j ), pour parenthéser A i . . . A j on doit
scinder le produit entre A 1 . . . A k et A k+1 A j pour un i ≤ k < j
C (A 1 . . . A j ) = C (A 1 . . . A k ) +C (A k+1 A j ) + P où P est le coût du produit
entre (A 1 . . . A k ) et (A k+1 A j )
La sous structure optimale est la suivante :
Pour parenthéser (de manière optimale) A i A i +1 . . . A j on scinde le
produite entre A k et A k+1
La parenthétisation de A 1 . . . A k doit être optimale ainsi que celle de
A k+1 A j (sinon on peut trouver une meileure solution ... pourquoi ?)
Il reste à trouver le bon k qui optimise le résultat global.
Hicham Bensaid (Département RIM) Conception des algorithmes 28 / 77
 Programmation dynamique Multiplication optimale d’une chaine de matrices

2. Une solution récursive

m[i , j ] le nombre minimum de multiplications scalaires pour calculer le

produit A i A i +1 . . . A j (m[1, n] est la solution donc au problème global)
si i = j alors m[i , j ] = 0
sinon en supposant connaitre la valeur du bon k
m[i , j ] = m[i , k] + m[k + 1, j ] + p i −1 p k p j
le problème donc est de trouver le bon k

0 si i = j
m[i , j ] = ¡ ¢
 min m[i , k] + m[k + 1, j ] + p i −1 p k p j si i < j
i ≤k< j

m[i , j ] donne le coût de la solution optimale mais ne donne pas la

solution
⇒ on utilise un tableau s[i , j ] pour stocker (en calculant m[i , j ]) le
bon k retenu.
Hicham Bensaid (Département RIM) Conception des algorithmes 29 / 77
 Programmation dynamique Multiplication optimale d’une chaine de matrices

3. Calculs des coûts optimaux

L’implémentation naïve de la formule récursive est exponentielle (vous

pouvez vérifier et voir pourquoi)
En fait le problème vient des chevauchements entre sous problèmes :
le même sous problème peut être rencontré plusieurs fois
une des caractéristiques fondamentales de quand utiliser la
programmation dynamique
On utilise une approche bottom-up (fondée sur un tri topologique)
pour éviter de calculer plusieurs fois la même chose
­ ®
Entrée : une séquence p 0 , p 1 , . . . , p n de taille n + 1 (les tailles des
matrices, on n’a pas besoins des matrices elles mêmes)
La procédure utilise un tableau m[i , j ] pour stocker les coûts et un
tableau s[i , j ] pour les choix des scissions (permet de construire la
solution optimale)

Hicham Bensaid (Département RIM) Conception des algorithmes 30 / 77

 Programmation dynamique Multiplication optimale d’une chaine de matrices

3. Calculs des coûts optimaux - suite

Idée du tri topologique utilisé :

Pour traiter un produit A i . . . A j (i.e. traiter une chaine de j − i + 1)
éléments on a besoin de traiter des sous chaines de tailles < j − i + 1.
Le traitement doit donc aller des plus petites chaines (le cas dégénéré
une chaine réduite à un seul élément) puis les chaines à deux éléments
en allant jusqu’aux chaines ayant le plus d’éléments

Hicham Bensaid (Département RIM) Conception des algorithmes 31 / 77

 Programmation dynamique Multiplication optimale d’une chaine de matrices

3. Calculs des coûts optimaux - L’algorithme (bottom up)

Entrée : une chaine p de tailles de matrices
Résultat : la solution optimale et son coût
1 function produitMatricesTriTopo(p )
2 Soit m[1..n, 1..n] et s[1..n − 1, 2, n] deux tableaux
3 for i = 1 to n do
4 m[i , i ] = 0
5 l représente la taille de la chaine
6 for l = 2 to n do
7 for i = 1 to n − l + 1 do
8 j = i +l −1
9 m[i , j ] = ∞
10 for k = i to j − 1 do
11 q = m[i , k] + m[k + 1, j ] + p i −1 p k p j
12 if q<m[i,j] then
13 m[i , j ] = q
14 s[i , j ] = k

15 return m et s
Algorithme 6 : produitMatricesTriTopo
Hicham Bensaid (Département RIM) Conception des algorithmes 32 / 77
 Programmation dynamique Multiplication optimale d’une chaine de matrices

Exemple

matrice A1 A2 A3 A4 A5 A6
dimension 30 × 35 35 × 15 15 × 5 5 × 10 10 × 20 20 × 25

La solution optimale est donnée par m[1, 6]

Exemple :

m[2, 2] + m[3, 5] + p 1 p 2 p 5 = 13000


m[2, 5] = min m[2, 3] + m[4, 5] + p 1 p 3 p 5 = 7125 = 7125


m[2, 4] + m[5, 5] + p p p = 11375
1 4 5

Hicham Bensaid (Département RIM) Conception des algorithmes 33 / 77

 Programmation dynamique Multiplication optimale d’une chaine de matrices

4. Construire une solution optimale

Le tableau m ne donne pas comment parenthéser (il donne uniquement le
nombre d’opérations optimal)
s permet de construire le parenthésage : s[i , j ] = k indique où il faut scinder
entre A i et A j dans le produit A i . . . A k A k+1 A j
En commençant depuis s[1, n] = k on peut construire récursivement en
considérant s[1, k] et s[k + 1, n]
Entrée : un tableau s et deux indices i ≤ j
1 procedure imprimerParenthesageOptimal(s, i , j )
2 if i = j then
3 imprimer " A i "
4 else
5 imprimer "("
6 k = s[i , j ]
7 imprimerParenthesageOptimal(s, i , k )
8 imprimerParenthesageOptimal(s, k + 1, j )

Algorithme 7 : imprimerParenthesageOptimal
L’appel imprimerParenthesageOptimal(s, 1, 6) sur l’exemple précédent
produit le parenthésage : ((A 1 (A 2 A 3 )) ((A 4 A 5 ) A 6 ))
Hicham Bensaid (Département RIM) Conception des algorithmes 34 / 77
 Programmation dynamique Multiplication optimale d’une chaine de matrices

Version top down (memoïsation)

1 function produitMatricesMemoisation(p )
2 n = p.t ai l l e − 1
3 Soit m[1..n, 1..n] un nouveau tableau
4 for i = 1 to n do
5 for j = 1 to n do
6 m[i , j ] = ∞

7 return chercherChaine(m, p, 1, n )
Algorithme 8 : produitMatricesMemoisation
1 function chercherChaine(m, p, i , j )
2 if m[i , j ] < ∞ then
3 return m[i , j ]
4 if i==j then
5 m[i , j ] = 0
6 else
7 for k = i to j − 1 do
8 q =chercherChaine(m, p, i , k ) + chercherChaine(m, p, k + 1, j ) +p i −1 p k p j
9 if q < m[i , j ] then
10 m[i , j ] = q

11 return m[i , j ]
Hicham Bensaid (Département RIM) Conception des algorithmes 35 / 77
 Programmation dynamique Multiplication optimale d’une chaine de matrices

Pour résumer

Quand utiliser la programmation dynamique ?

Deux ingrédients pour pouvoir le faire :
sous structure optimale
sous problèmes chevauchants

Hicham Bensaid (Département RIM) Conception des algorithmes 36 / 77

 Algorithmes gloutons

Plan

1 Motivations

2 Programmation dynamique
Dégroupage optimal
Multiplication optimale d’une chaine de matrices

3 Algorithmes gloutons

4 Diviser pour régner

Tri par fusion
Tri rapide (quicksort)

Hicham Bensaid (Département RIM) Conception des algorithmes 37 / 77

 Algorithmes gloutons

Algorithmes gloutons

Un problème d’optimisation = séquence d’étapes

Dans chaque étape il faut faire un choix parmi plusieurs possibilités
Cela ressemble aux problèmes traités par la programmation dynamique
la programmation dynamique est justement parfois disproportionnée
Un algorithme glouton choisit à chaque étape l’option qui semble la
meilleure parmi celles possibles
Une sorte de suite d’optimisations locales successives vers une
optimisation globale
Exemples : arbre de recouvrement minimal d’un graphe, plus court
chemin dans un graphe acyclique (Dijkstra), codes de Huffman, . . .

Hicham Bensaid (Département RIM) Conception des algorithmes 38 / 77

 Algorithmes gloutons

Exemple explicatif : problème de choix de tâches

Problème de planification de plusieurs tâches concurrentes

Une ressource partagée entre toutes les tâches accessible en exclusion
mutuelle
A un instant donnée, une seule tâche peut être active
Objectif : choisir le plus grand nombre de tâches mutuellement
compatibles
S 1 = {a 1 , . . . , a n } ensemble de tâches
Chaque tâche ai a un instant de début s i et de fin f i
£ £
Une tâche est active pendant s i , f i
£ £ £ £
a i et a j sont mutuellement compatibles ssi s i , f i ∩ s j , f j = ;
Hypothèse de simplification : f 1 ≤ f 2 ≤ . . . ≤ f n

Hicham Bensaid (Département RIM) Conception des algorithmes 39 / 77

 Algorithmes gloutons

Instance du problème

i 1 2 3 4 5 6 7 8 9 10 11
si 1 3 0 5 3 5 6 8 8 2 12
fi 4 5 6 7 9 9 10 11 12 14 16

{a 3 , a 9 , a 11 } tâches mutuellement compatibles mais non optimale

{a 1 , a 4 , a 8 , a 11 } est plus grande (elle est en fait optimale)
{a 2 , a 4 , a 9 , a 11 } est une autre solution optimale

Hicham Bensaid (Département RIM) Conception des algorithmes 40 / 77

 Algorithmes gloutons

Résolution du problème

On va résoudre le problème en plusieurs étapes

1 Essayer de réfléchir à une solution de type programmation dynamique
plusieurs choix pour choisir les sous problèmes de la solution optimale
2 Pour cet exemple, on verra qu’il suffit de considérer un seul choix
le choix glouton
3 Solution récursive du problème
4 Transformation de la solution récursive en itérative

Hicham Bensaid (Département RIM) Conception des algorithmes 41 / 77

 Algorithmes gloutons

Sous structure optimale du problème

S i j : ensemble de tâches qui démarrent après la fin de a i et qui se

terminent avant le début de a j
© ª
S i j = ak | f i ≤ sk ≤ f k ≤ s j

On cherche une ensemble maximal A i j de tâches compatibles dans S i j

Soit ak ∈ A i j
A i j = A i k ∪ {a k } ∪ A k j où A i k = A i j ∩ S i k et A k j = A i j ∩ S k j
|A i j | = |A i k | + |A k j | + 1
A i j contient également les solution optimales de S i k et S k j ( A i k et
A k j sont des solutions optimales pour S i k et S k j )
′
Sinon on aurait A i k ∪ {ak } ∪ A k j solution de S i j et supérieure à A i j

Hicham Bensaid (Département RIM) Conception des algorithmes 42 / 77

 Algorithmes gloutons

La programmation dynamique une bonne solution ?

¡ ¢ ¡ ¢
c i , j = c (i , k) + c k, j + 1
Comme on ne connait pas exactement quel ak choisir :

¡ ¢ 0 si S i j = ;
c i, j = © ¡ ¢ ª
 max c (i , k) + c k, j + 1 sinon
a k ∈S i j

Problème solvable en programmation dynamique (algorithme récursif

+ mémoïsation)
Mais . . . est ce qu’on ne peut pas faire mieux ? . . .

Hicham Bensaid (Département RIM) Conception des algorithmes 43 / 77

 Algorithmes gloutons

Faire le choix glouton

L’idée pour faire mieux est d’essayer de ne considérer qu’un seul choix
(le choix glouton)
Problème : il faut une condition suffisante pour que le choix glouton
implique une solution optimale
Par exemple, intuitivement si on choisit systématiquement la tâche qui
se termine le plus tôt, on laisse plus de temps pour plus de tâches . . .
Après© le choix glouton,
ª
il reste un seul sous problème :
S k = a i ∈ S|s i ≥ f k (toutes les tâches qui démarrent après la fin de
ak )
La question est : est-ce que l’intuition (choisir la tâche la première à
finir) est correcte ?

Hicham Bensaid (Département RIM) Conception des algorithmes 44 / 77

 Algorithmes gloutons

Correction de l’intuition
Théorème
Soient S k 6= ; un sous-problème et am ∈ S k telle que am est la première à terminer (dans
S k ).
a m appartient à un sous-ensemble maximum de tâches de S k mutuellement compatibles

Démonstration.
A k un ensemble maximum solution de S k .
a j ∈ A k est celle qui termine la première
Si a j = a m alors c’est OK (a m ∈ A k )
′
Sinon, soit A k = A k − {a j } ∪ {a m }
′
Les tâches de A k sont disjointes : celles de A k le sont et a j est la première à terminer
dans A k et f m ≤ f j

(toutes les autres tâches ai 6= a j de A k démarrent après f j et donc

après f m )
′ ′
|A k | = |A k | et donc A k est maximal

Hicham Bensaid (Département RIM) Conception des algorithmes 45 / 77

 Algorithmes gloutons

Algorithme glouton récursif

On choisit la tâche ak qui termine la première

On ne garde que les tâches compatibles avec ak
On répète jusqu’à la fin des tâches
Les instants de fin sont croissants
Une tâche n’est considérée qu’une seule fois

Hicham Bensaid (Département RIM) Conception des algorithmes 46 / 77

 Algorithmes gloutons

Algorithme glouton récursif

Entrée : un tableau s des instants de début, un tableau f des instants de
fin, un indice k pour définir le sous-problème S k à résoudre et la
taille n du problème d’origine
Résultat : un sous ensemble de tâches mutuellement compatibles
maximum
1 function tâchesCompatiblesMax( f , s, k, n )
2 m = k +1
3 while m ≤ n and s[m] < f [k] do
4 m = m +1
5 if m ≤ n then
6 return am ∪ tâchesCompatiblesMax( f , s, m, n )
7 else
8 return ;
Algorithme 9 : tâchesCompatiblesMax
On appelle tâchesCompatiblesMax( f , s, 0, n )
Hicham Bensaid (Département RIM) Conception des algorithmes 47 / 77
 Algorithmes gloutons

Une autre façon de voir les algorithmes gloutons

Résolution d’un problème de manière optimale. Pour construire la

solution du problème, on a un ensemble (ou liste) C de candidats (les
différentes tâches e.g. )
Lors du déroulement de l’algorithme on accumule deux ensembles :
Un ensemble S des candidats déjà traités et retenus (ils ne seront plus
traités)
Un ensemble X des candidats déjà traités et rejetés (ils ne seront plus
traités)
Il existe une fonction sol ut i on qui vérifie si un ensemble de candidats
fournit une solution au problème (sans tenir compte de l’optimalité)

Hicham Bensaid (Département RIM) Conception des algorithmes 48 / 77

 Algorithmes gloutons

Une autre façon de voir les algorithmes gloutons

Une autre fonction f ai sabl e vérifie si un ensemble de candidats peut

être étendu avec un nouvel élément vers une solution
Une fonction de sélection sel ect i on indique à tout moment quel est le
candidat non encore traité le plus prometteur (ça sera le choix glouton)
Enfin une fonction objectif qui donne le résultat trouvé

Hicham Bensaid (Département RIM) Conception des algorithmes 49 / 77

 Algorithmes gloutons

Algorithme glouton général itératif

Entrée : un ensemble C
Résultat : un sous-ensemble S de C optimal
1 function gloutonIteratif(C )
2 ; // C est l’ensemble de candidats
3 S =; // Le sous-ensemble solution est construit dans S
4 while C 6= ; and not sol ut i on(S) do
5 x = sel ec t i on(C )
6 C =C −x
7 if f ai sabl e(S ∪ x) then
8 S =S∪x

9 if sol ut i on(S) then

10 return S
11 else
12 return "Pas de solution"
Algorithme 10 : gloutonIteratif
Hicham Bensaid (Département RIM) Conception des algorithmes 50 / 77
 Algorithmes gloutons

Application à notre exemple

C = {a 1 , . . . , a n }
¡© ª¢
sol ut i on a i 1 , . . . , a i l = vr ai ssi les a i j mutuellement compatibles et
C = ; (ceci est un cas particulier)
sel ect i on (C ) retourne la première tâche à terminer non encore traitée
¡© ª¢
f ai sabl e a i 1 , . . . , a i l ssi les a i j mutuellement compatibles

Hicham Bensaid (Département RIM) Conception des algorithmes 51 / 77

 Algorithmes gloutons

Exemple : Problème du sac à dos

Problème du sac à dos (version simple)

Un ensemble d’articles U = {u 1 , u 2 , . . . , u N }
Chaque article a un poids p i et une valeur v i (p i , v i ∈ N)
Le poids maximum que peut contenir le sac à dos P
Comment choisir des fractions des articles à mettre dans le sac à dos
pour maximiser la valeur globale transportée ?

Hicham Bensaid (Département RIM) Conception des algorithmes 52 / 77

 Algorithmes gloutons

Problème du sac à dos : construire une solution gloutonne

Chaque article i choisi contribue avec x i p i dans le poids total

et avec x i v i dans la valeur globale transportée
Il s’agit de résoudre :
maximiser ni=1 x i v i
P

sous la contrainte P ≥ ni=1 x i p i

P

avec v i > 0, p i > 0 et 0 ≤ x i ≤ 1

Solution gloutonne : les candidats sont les différents objets
La solution = {x 1 , . . . , x n } est faisable si elle respecte les contraintes
la fonction objectif = valeur totale transportée
Pn
Remarque : si i =1 p i ≤ P alors la solution est triviale . . . et si
Pn
x p
i =1 i i < P alors on peut toujours ajouter une fraction pour remplir
⇒ dans une solution optimale : ni=1 x i p i = P
P

Hicham Bensaid (Département RIM) Conception des algorithmes 53 / 77

 Algorithmes gloutons

Algorithme glouton
Entrée : un ensemble C et un poids maximimum P du sac à dos
Résultat : une configuration x1 , . . . , xn optimale
1 function sacADosGlouton(C , P ) // C est un ensemble d’articles
2 S =; // Le sous-ensemble solution est construit dans S
3 for i = 1 to n do // initialisation
4 x[i ] = 0
5 poi d s = 0
6 while C 6= ; and poi d s < P do
7 c = sel ect i on(C )
8 C =C −c
9 if poi d s + [Link] d s ≤ P then
10 x[i ] = 1
11 poi d s = poi d s + [Link] d s
12 else
13 x[1] = (P − poi d s)/[Link] d s
14 poi d s = P

15 return x
Algorithme 11 : sacADosGlouton
Hicham Bensaid (Département RIM) Conception des algorithmes 54 / 77
 Algorithmes gloutons

Algorithme glouton
La question est comment choisir le bon candidat ?
à chaque fois au moins trois possibilités :
Choisir l’article restant ayant la plus grande valeur
Choisir l’article restant le plus léger
Choisir l’article restant ayant le meilleur rapport v i /p i
Exemple : pour n = 5 et P = 100
p 10 20 30 40 50
v 20 30 66 40 60
v/p 2.0 1.5 2.2 1.0 1.2

sélection xi valeur
max v i 0 0 1 0.5 1 146
min p i 1 1 1 1 0 156
max v i /p i 1 1 1 0 0.8 164

Hicham Bensaid (Département RIM) Conception des algorithmes 55 / 77

 Algorithmes gloutons

Solution optimale

Les deux premiers critères ne sont pas optimaux, le troisième l’est-il ?

La réponse est oui.
Pourquoi ? : le théorème suivant

Théorème
Si les articles sont choisis dans l’ordre décroissant des v i /p i alors
sacADosGlouton trouve une solution optimale.

Démonstration.
On suppose (s.p.g.) que v 1 /p 1 ≥ v 2 /p 2 ≥ . . . ≥ v n /p n . X = (x 1 , . . . , x n )
solution optimale.

Hicham Bensaid (Département RIM) Conception des algorithmes 56 / 77

 Algorithmes gloutons

Solution optimale
Démonstration.
(suite)
Si tous les x i = 1 alors la solution est optimale
Sinon, soit j le plus petit indice tq x j < 1
∀i < j x i = 1 et ∀i > j x i = 0 et ni=1 x i p i = P
P

Soit Y = y 1 , . . . , y n une solution réalisable. donc ni=1 y i p i ≤ P et

¡ ¢ P
Pn
i =1 (x i − y i )p i ≥ 0
V (X ) − V (Y ) = ni=1 (x i − y i )p i . pv ii
P

On va montrer que (x i − y i )(v i /p i ) ≥ (x i − y i )(v j /p j )

Si i < j , x i = 1 et donc (x i − y i ) ≥ 0 et v i /p i ≥ v j /p j
Si i > j , x i = 0 et donc (x i − y i ) ≤ 0 et v i /p i ≤ v j /p j
si i = j , v i /p i = v j /p j et donc (x i − y i )(v i /p i ) = (x i − y i )(v j /p j )
V (X ) − V (Y ) ≥ (v j /p j ) ni=1 (x i − y i )p i ≥ 0
P

⇒ Aucune solution réalisable n’est meilleure que V (X )

Hicham Bensaid (Département RIM) Conception des algorithmes 57 / 77
 Algorithmes gloutons

Limites de l’approche gloutonne

Le problème du sac à dos entier est une variation du problème
précédent
Pas de fractions : ou bien un article est retenu ou bien il ne l’est pas
Exemple : n = 3 et P = 50
p 10 20 30
v 60 100 120
v/p 6 5 4
Une stratégie gloutonne commencerait par choisir l’article 1
ou bien 1 + 2 : valeur = 160
ou bien 1 + 3 : valeur = 180
Solutions non optimales ! !
La solution optimale dans ce cas est 2 + 3 : valeur = 220
La programmation dynamique permet de résoudre le problème
Mais c’est un problème très coûteux (on ne lui connait aucune solution
polynomiale)
Hicham Bensaid (Département RIM) Conception des algorithmes 58 / 77
 Diviser pour régner

Plan

1 Motivations

2 Programmation dynamique
Dégroupage optimal
Multiplication optimale d’une chaine de matrices

3 Algorithmes gloutons

4 Diviser pour régner

Tri par fusion
Tri rapide (quicksort)

Hicham Bensaid (Département RIM) Conception des algorithmes 59 / 77

 Diviser pour régner Tri par fusion

Tri par fusion : la fusion

Complexité linéaire : Θ(n)
Entrée : un tableau T , trois indices p, q, r tels que T [p..q] et T [q + 1, r ] sont triés
Résultat : T [p..r ] est trié
1 procedure fusion(T, p, q, r )
2 n1 = q − p + 1
3 n2 = r − q
4 Soient G[1..n 1 + 1] et D[1..n 2 + 1] deux nouveaux tableaux
5 G[1..n 1 ] = T [p..q]
6 D[1..n 2 ] = T [q + 1..r ]
7 G[n 1 + 1] = ∞
8 D[n 2 + 1] = ∞
9 i = j =1
10 for k = p to r do
11 if G[i ] ≤ D[ j ] then
12 T [k] = G[i + +]
13 else
14 T [k] = D[ j + +]
Hicham Bensaid (Département RIM) Conception des algorithmes 60 / 77
 Diviser pour régner Tri par fusion

Tri par fusion

Complexité en Θ(n lg n) : si n ∈ 2N alors t (n) = 2t (n/2) + Θ(n)

Entrée : un tableau T , deux indices p, r
Résultat : T est trié
1 procedure triFusion(T, p, r )
2 if p < r ¥then ¦
3 q = (p + r )/2
4 triFusion(T, p, q )
5 triFusion(T, q + 1, r )
6 fusion(T, p, q, r )
Algorithme 13 : triFusion

Hicham Bensaid (Département RIM) Conception des algorithmes 61 / 77

 Diviser pour régner Tri rapide (quicksort)

Quicksort

algorithme de tri de complexité dans le pire cas en Θ(n 2 )

mais en pratique c’est le meilleur :
complexité moyenne en Θ(n lg(n)) et constantes cachées faibles
effectue le tri sur place
fondé sur la stratégie diviser pour régner
diviser : partitionner en réarrangeant T [p..r ] en 2 sous tableaux
T1 = T [p..q − 1] et T2 = T [q + 1..r ] tq T [i ] ≤ T [q] ≤ T [ j ]
pour i ∈ [p..q − 1] et j ∈ [q + 1..r ]. Le calcul de q est le
résultat de cette procédure
régner : trier T1 et T2 récursivement par quicksort
combiner : il n’y a rien à faire ...

Hicham Bensaid (Département RIM) Conception des algorithmes 62 / 77

 Diviser pour régner Tri rapide (quicksort)

Quicksort : l’algorithme

Entrée : un tableau T , deux indices p, r

Résultat : T [p..r ] trié
1 procedure quicksort(T, p, r )
2 if p < r then
3 q = partitionner(T, p, r )
4 quicksort(T, p, q − 1)
5 quicksort(T, q + 1, r )
Algorithme 14 : quicksort
Pour trier un tableau T il suffit d’exécuter quicksort(T, 1, T.t ai l l e )

Hicham Bensaid (Département RIM) Conception des algorithmes 63 / 77

 Diviser pour régner Tri rapide (quicksort)

Quicksort : partitionner

Entrée : un tableau T , deux indices p, r

Résultat : q la position du pivot
1 function partitionner(T, p, r )
2 x = T [r ]
3 i = p −1
4 for j = p to r − 1 do
5 if T [ j ] ≤ x then
6 i = i +1
7 échanger T [i ] et T [ j ]

8 q = i +1
9 échanger T [q] et T [r ]
10 return q
Algorithme 15 : partitionner

Hicham Bensaid (Département RIM) Conception des algorithmes 64 / 77

 Diviser pour régner Tri rapide (quicksort)

Exemple

T [r ] est le pivot x
Les éléments en gris clair =
première partition (tous ≤ x )
Les éléments en gris foncé =
deuxième partition (tous > x )
Les autres ne sont pas encore
traités
(Le dernier élément est le pivot)
A la dernière étape on échange
T [r ] et T [i + 1]

Hicham Bensaid (Département RIM) Conception des algorithmes 65 / 77

 Diviser pour régner Tri rapide (quicksort)

Quicksort : comment ça marche ?

Si T [ j ] > x , on incrémente j
Si T [ j ] ≤ x on incrémente i , puis on échange T [i ] et T [ j ] enfin on
incrémente j
Hicham Bensaid (Département RIM) Conception des algorithmes 66 / 77
 Diviser pour régner Tri rapide (quicksort)

Quicksort : complexité dans le pire cas

On va démontrer que dans le pire cas T (n) = Θ(n 2 )
On démontre que T (n) = O(n 2 ) et T (n) = Ω(n 2 )
Dans le pire cas on a l’équation de récurrence
¡ ¢
T (n) = max T (q) + T (n − q − 1) + Θ(n)
0≤q≤n−1

S. q. T (k) ≤ ck 2 ∀k ≤ n − 1 et remplaçons dans la récurrence

T (n) ≤ max (c q 2 + c(n − q − 1)2 ) + Θ(n) =
0≤q≤n−1
c. max (q 2 + (n − q − 1)2 ) + Θ(n)
0≤q≤n−1
Le maximum est atteint pour q = 0 ou q = n − 1
donc max (q 2 + (n − q − 1)2 ) ≤ (n − 1)2
0≤q≤n−1
et T (n) ≤ cn − c(2n − 1) + Θ(n) ≤ cn 2 en prenant c suffisamment
2

grande pour que c(2n − 1) domine le terme en Θ(n)

Attention aux conditions aux limites ! ! !
Donc T (n) = O(n 2 )
Hicham Bensaid (Département RIM) Conception des algorithmes 67 / 77
 Diviser pour régner Tri rapide (quicksort)

Quicksort : complexité dans le pire cas

On démontre que T (n) = Ω(n 2 )

Dans le pire cas on a l’équation de récurrence
¡ ¢
T (n) = max T (q) + T (n − q − 1) + Θ(n)
0≤q≤n−1

S. q. T (k) ≥ d k 2 ∀k ≤ n − 1 et remplaçons dans la récurrence

T (n) ≥ max (d .q 2 + d .(n − q − 1)2 ) + Θ(n) ≥ d .(n − 1)2 + Θ(n)
0≤q≤n−1

et T (n) ≥ d .n 2 − d (2n − 1) + Θ(n) ≥ d n 2 en prenant d suffisamment

petite pour que d (2n − 1) soit dominé par le terme en Θ(n)
Attention aux conditions aux limites ! ! !
Donc T (n) = Ω(n 2 )
Conclusion : T (n) = Θ(n 2 ) dans le pire cas

Hicham Bensaid (Département RIM) Conception des algorithmes 68 / 77

 Diviser pour régner Tri rapide (quicksort)

Quicksort : complexité dans le meilleur cas

On va démontrer que dans le meilleur cas T (n) = Θ(n lg n)

¡ ¢
Dans le meilleur cas : T (n) = min T (q) + T (n − q − 1) + Θ(n)
0≤q≤n−1
S. q. T (k) ≤ c.k lg k ∀k ≤ n − 1 et remplaçons dans la récurrence
¡ ¢
T (n) ≤ min c.q lg q + c.(n − q − 1) lg(n − q − 1) + Θ(n)
0≤q≤n−1
T (n) ≤ c.q 0 lg q 0 + c.(n − q 0 − 1) lg(n − q 0 − 1) + Θ(n) avec q 0 = (n − 1)/2
T (n) ≤ c. ((n − 1)/2) lg ((n − 1)/2) + c. ((n − 1)/2) lg ((n − 1)/2) + Θ(n)
donc T (n) ≤ c.(n − 1) lg(n − 1) − c.(lg 2.)(n − 1) + Θ(n)
et T (n) ≤ c.n. lg(n) (car n lg n ր) en choisissant c telle que
c.(lg 2.)(n − 1) domine la fonction en Θ(n)
Attention aux conditions aux limites (il faut les vérifier) . . .
Donc T (n) = O(n lg n) dans le meilleur cas

Hicham Bensaid (Département RIM) Conception des algorithmes 69 / 77

 Diviser pour régner Tri rapide (quicksort)

Quicksort : complexité dans le meilleur cas

On va démontrer que dans le meilleur cas T (n) = Ω(n lg n)

¡ ¢
T (n) = min T (q) + T (n − q − 1) + Θ(n)
0≤q≤n−1
S. q. T (k) ≥ c.k lg k ∀k ≤ n − 1 et remplaçons dans la récurrence
¡ ¢
T (n) ≥ min c.q lg q + c.(n − q − 1) lg(n − q − 1) + Θ(n)
0≤q≤n−1
¢′
f ′ (q) = c.q lg q + c.(n − q − 1) lg(n − q − 1) = lg q/(n − q − 1)
¡ ¡ ¢

lim f ′ (q) = −∞ et lim f ′ (q) = +∞ et

q→0+ q→n−1−

f ′′ (q) = (n − 1)(n − 1 − q)/(n − q − 1)2 ≥ 0 donc f ′ :−∞ ր 0 ր+∞ et

traverse 0 en q0 tq f ′ (q0 ) = 0

Hicham Bensaid (Département RIM) Conception des algorithmes 70 / 77

 Diviser pour régner Tri rapide (quicksort)

Quicksort : complexité dans le meilleur cas

f est donc : ց q 0 ր (minimum atteint en q 0 )

q 0 = n − q 0 − 1 ⇒ q 0 = (n − 1)/2 : l’optimum est atteint quand on divise
le tableau en deux
T (n) ≥ c. ((n − 1)/2) lg ((n − 1)/2) + c. ((n − 1)/2) lg ((n − 1)/2) + Θ(n)
donc T (n) ≥ c.(n − 1) lg(n − 1) − c.(lg 2.)(n − 1) + Θ(n)
¡ ¢
et T (n) ≥ c.n lg n + c.(n − 1) lg(n − 1) − cn lg n − c.(lg 2.)(n − 1) + Θ(n)

Hicham Bensaid (Département RIM) Conception des algorithmes 71 / 77

 Diviser pour régner Tri rapide (quicksort)

Quicksort : complexité dans le meilleur cas

or c.(n − 1) lg(n − 1) − cn lg n = −n lg (1 + 1/(n − 1)) − lg(n − 1)

et lg (1 + 1/(n − 1)) ∼ 1/(n − 1) (D. L. de log au voisinage de 1)
donc c.(n − 1) lg(n − 1) − cn lg n ∼ −1 − lg(n − 1) ≥ −α lg(n)
donc
c.(n − 1) lg(n − 1) − cn lg n − c.(lg 2.)(n − 1) + Θ(n) ≥ −α lg(n) − βc n + Θ(n)
on choisissant c suffisamment petite pour que la fonction en Θ(n)
domine α lg(n) + βc n
On a T (n) ≥ c.n. lg(n)
Attention aux conditions aux limites (il faut les vérifier) . . .
Donc T (n) = Ω(n lg n) dans le meilleur cas
Donc T (n) = Θ(n lg n)

Hicham Bensaid (Département RIM) Conception des algorithmes 72 / 77

 Diviser pour régner Tri rapide (quicksort)

Quicksort : complexité en moyenne

On suppose que les éléments sont équitablement répartis

Probabilité pour choisir un élément comme pivot parmi n éléments =
1/n

Temps d’exécution de Quicksort dominé par les appels à par t i t i on

Chaque appel à par t i t i on choisit un pivot
un pivot choisit n’est plus jamais choisi après
⇒ au plus n appels à par t i t i on

Hicham Bensaid (Département RIM) Conception des algorithmes 73 / 77

 Diviser pour régner Tri rapide (quicksort)

Quicksort : complexité en moyenne

Complexité de par t i t i on Entrée : un tableau T , deux

O(1) : toutes les opérations indices p, r
sauf la boucle for (lignes 4 à Résultat : q la position du pivot
7) 1 function partitionner(T, p, r )
une quantité proportionnelle 2 x = T [r ]
au nombre d’itération de la 3 i = p −1
boucle for (lignes 4 à 7) 4 for j = 1 to r − 1 do
Chaque itération effectue une 5 if T [ j ] ≤ x then
comparaison entre le pivot et 6 i = i +1
un autre élément du tableau 7 échanger T [i ] et T [ j ]
(ligne 5)
Il faut donc compter le 8 q = i +1
nombre total de 9échanger T [q] et T [r ]
10 return q
comparaisons
Hicham Bensaid (Département RIM)
Algorithme 16 : partitionner 74 / 77
Conception des algorithmes
 Diviser pour régner Tri rapide (quicksort)

Quicksort : relation entre la complexité et le nombre de

comparaison

Lemme
Soit X le nombre de comparaisons exécutées dans la ligne 5 de par t i t i on
durant toute la durée d’une exécution de qui cksor t sur un tableau de
taille n
Le temps d’exécution de qui cksor t est O(n + X )

Démonstration.
Preuve immédiate

Hicham Bensaid (Département RIM) Conception des algorithmes 75 / 77

 Diviser pour régner Tri rapide (quicksort)

Quicksort : évaluation de X

On va compter le X global (et non pas combien de comparaisons à

chaque itération)
Z = {z 1 , . . . z n } où z i est le i ème plus petit élément
Zi j = {z i , z i +1 , . . . , z j }
Quand est ce qu’on compare z i et z j ?
chaque paire est comparée au plus une fois
on ne compare qu’avec le pivot qui n’est utilisé qu’une fois
X i j ∈ {0, 1} variable aléatoire de l’évènement comparaison de z i et z j
X = in−1
P Pn
=1 j =i +1 X i j

Hicham Bensaid (Département RIM) Conception des algorithmes 76 / 77

 Diviser pour régner Tri rapide (quicksort)

Quicksort : évaluation de X

hP i
n−1 Pn
E [X ] = E i =1 j =i +1 X i j

E [X ] = in−1
P Pn £ ¤
=1 j =i +1 E X i j
E [X ] = in−1
Pn ¡ ¢
j =i +1 P r z i est comparé à z j
P
=1
z i est comparé à z j ssi z i ou z j est le pivot de Zi j
P r z i soit choisit comme pivot = j −i1+1 (les éléments sont
¡ ¢

équiprobables)
Pn−1 Pn 1
donc E [X ] = 2. i =1 j =i +1 j −i +1 soit par changement de variable
(k = j − i )
Pn−1 Pn 1
E [X ] = 2. i =1 k=1 k
E [X ] = O(n lg n)

Hicham Bensaid (Département RIM) Conception des algorithmes 77 / 77