Introduction

Algorithmes: Complexité, Analyse, Ordre

Diviser pour régner (Chapitre 2)

Programmation dynamique

Algorithmes voraces

Complexité du calcul

Diviser-pour-régner

Pour résoudre un problème P avec la méthode

« diviser-pour-régner »:

1. On subdivise P en sous problèmes P1, P2, … , PN de

même nature que le problème du départ P, mais de moindre

taille.

2. résoudre chacun des problèmes P1, P2, … , PN en

utilisant le même algorithme « d’une façon récursive »

3. On combine les solutions de ces sous problèmes pour

obtenir la solution du problème initial P.

CSI3505 - Paola Flocchini

Diviser-pour-régner

Diviser une instance d'un problème en une

ou plusieurs instances plus petites.

Résoudre chacune des petites instances (Régner) .

A moins qu'une de ces instances ne soit

suffisamment triviale pour être résolue

directement, utiliser le processus de division

récursivement.

Combiner si nécessaire les solutions des

plus petites instances pour obtenir

la solution du problème global.

fonction DPR(x)

{la fonction retourne comme valeur la solution du problème avec input l'instance x}

si x est suffisamment simple alors

retourner SOLU-AD-HOC(x)

sinon décomposer x en sous-instances plus simples x1, …, xk

pour i=1 jusqu'a k faire

yi = DPR(xi)

combiner les yi pour obtenir une solution y pour x

retourner y

CSI3505 - Paola Flocchini

Diviser-pour-régner: Exemples

Exemple - Recherche binaire

Recherche binaire

Tri par Fusion (MergeSort)

Tri de Hoare (QuickSort)

Sélection de la médian

Si la liste est triée

S[bas]----------------------------------------------S[haut]

Algorithme de Strassen pour la multiplication de matrices

CSI3505 - Paola Flocchini

Exemple - Recherche binaire

Opération Diviser:

comparer l'élément central avec x

si x est trouvé, terminer

fonction position(bas, haut)

sinon garder la partie ou x pourrait se trouver

if bas > haut then position:= 0;

(On a divisé le problème en un autre de taille moitié.)

Régner: Résoudre le sous tableau de taille moitié

Combiner: Pas nécessaire

[continuer jusqu'a ce que x est trouvé ou le sous tableau ]

else

Milieu:=  (bas +haut)/2 ;

if S[Milieu] = x then

position:= Milieu;

else if x < S[Milieu] then

position:=position(bas, Milieu-1);

else

position:=position(Milieu+1, haut);

CSI3505 - Paola Flocchini

Exemple - Recherche binaire

(RAPP: Version itérative: W(n) = 2 log n + 2)

Analyse dans le Pire Cas (Algorithme 2.2)

Taille du problème: n, le nombre d'éléments

Opérations élémentaires: comparaisons

Pire Input: ?

1. Diviser : Comparer avec le milieu: 1

2. Résoudre: on doit résoudre récursivement UN SEUL

sous problème de taille n/2. Donc on a W(n/2)

3. Combiner: Rien

CSI3505 - Paola Flocchini

Supposons que n est une puissance de 2 …..

Théorème

W(n) =  log n  + 1

Pour n = 1, W(n) = 1

Pour n > 1, W(n) = W(n/2) + 1

Récurrence a résoudre:

 W(n) = W(n/2) + 1 pour n > 1

 W(1) = 1

W(n) = lg n + 1, si n est une puissance de 2.

Preuve par induction?

Preuve par induction

Base:

n=1  log 1  + 1 = 1

Hypothèse d'induction:

Soit n > 1 pour tout 1 ≤ k ≤ n on assume que

W(K) =  log K  + 1

Considère n

W(n) = 1 + W(  n/2  )

CSI3505 - Paola Flocchini

Case 1) n pair

Relation de recurrence

Case 2) n impair

W(n) = W( n/2  )+1

= W(n/2 )+1

W(n) = W( n/2  ) + 1

= W((n- 1)/2 ) + 1

Par hypothèse d'induction

= (  log n/2  + 1 ) + 1

=  log n - log 2  + 2

=  log n - 1  + 2

=  log n  + 1

CSI3505 - Paola Flocchini

Analyse: Cas Moyen

Si la valeur cherché x est dans la liste

Ii = inputs qui permettent de trouver l’élément cherché

avec i appels

P(I1) = ?

t(I1) = 1

t(I2) = 2

t(Ii) = i

= (  log ((n - 1)/2)  + 1 ) + 1

=  log (n-1) - log 2  + 2

=  log (n-1) - 1  + 2

=  log (n-1)  + 1

Parce-que

 log (n-1) - 1  =

 log (n-1)  - 1

Quand est-ce que  log (n-1)  ≠  log n  ??

Seulement quand n est une puissance de 2

CSI3505 - Paola Flocchini

mais n est impair ...

t(I1) = 1

P(I1) = probabilité que x se trouve exactement au milieu

= 1/n

CSI3505 - Paola Flocchini

t(I2) = 2

P(I2) = ?

P(I2) = probabilité que x se trouve dans les positions ¼ ou ¾

= 2/n

t(I3) = 3

P(I3) = ?

3°

2°

3°

1°

2°

3°

P(I3) = probabilité que x se trouve …..

CSI3505 - Paola Flocchini

4/n

Problème du Tri

Problème:

ordonner n valeurs dans une séquence croissante

Données:

un entier positif n, un vecteur de valeurs S indexé

de 1 à n

Résultat:

Le vecteur S contenant les valeurs dans un ordre

croissant

CSI3505 - Paola Flocchini

t(I1) = 1

t(I2) = 2

t(I3) = 4

P(I1) = 1/n

P(I2) = 2/n

P(I3) = 4/n

t(Ii) = i

P(I3) = 2 i-1 /n

Combien d’appelles récursifs ?

log n + 1

Donc

log n +1

A(n) = Σ i ⋅ 2 i-1 /n

i=1

CSI3505 - Paola Flocchini

= log n ⋅ 2(log n +1) +1

Exemple - Tri par fusion - MERGESORT

1. Diviser le tableau en deux sous-tableaux

à peu près égaux en taille (environ n/2).

2. Résoudre le problème du tri pour chaque

sous-tableau (à l'aide du tri par fusion).

3. Combiner les sous-tableaux triés en les

fusionnant en un seul tableau trié,

en utilisant l'algorithme

de fusion 2.3

Exemple 2.2 et Figure 2.2 dans le livre

CSI3505 - Paola Flocchini

Exemple - Tri par fusion

Etape 1 – Diviser

62317425

7425

6231

Résoudre

CSI3505 - Paola Flocchini

Etape 2 – Combiner

O(n)

7542

6321

76543221

O(n)

CSI3505 - Paola Flocchini

Exemple - Tri par fusion

U,V: les sous-vecteurs

Diviser

Combiner

CSI3505 - Paola Flocchini

TriFusion(n,S)

h ← n div 2

m ← n - h

if n > 1 then

copier S[1] … S[h] en U

copier S[h+1]…. S[n] en V

TriFusion(h,U)

TriFusion(m,V)

Fusionner(h,m,U,V,S)

CSI3505 - Paola Flocchini

Fusionner(h,m,U,V,S)

i ← 1; j ← 1; k ← 1;

while i <= h and j<=m do

if U[i] < V[j] then

else

S[k] ← U[i]

i ← i+1

S[k] ← V[j]

j ← j+1

k ← k+1

if i> h then

copy V[j] …. V[m] en S[k] …. S[k+m]

else

copy V[i]…..V[ ] en S[k]…..S[k+m]

CSI3505 - Paola Flocchini

Fusionner(h,m,U,V,S)

2 5 6 9 12 15 20 27

4 7 10 13 16

2 4 5 6

Comparer U[i] et V[j] et mettre le plus petit en S

Incrémenter l'index de la liste ou le plus petit

se trouvait et incrémenter l'index de S

Lorsque l’on arrive a la fin d'une liste,

copier ce qui reste de l'autre liste en S.

CSI3505 - Paola Flocchini

Exemple - Tri par fusion

Analyse dans le Pire Cas (Algorithme 2.2)

Exemple - Tri par fusion

Analyse dans le Pire Cas (Algorithme 2.2)

Taille du problème: n, le nombre d'éléments

Opérations élémentaires: comparaisons

Pire Input: ?

1. Diviser : calculer le milieu. 0

2. Résoudre: on doit résoudre récursivement deux

sous-problèmes de taille n/2. Donc on a 2W(n/2)

3. Combiner: fusionner les deux sous listes triées: n-1

CSI3505 - Paola Flocchini

Supposons que n est une puissance de 2 …..

Pour n = 1, W(n) = 0

Pour n > 1 W(n) = = W(n/2) + W(n/2) + n-1

Récurrence a résoudre:

W(n) = 2 W(n/2) + n - 1 pour n > 1

W(1) =0

CSI3505 - Paola Flocchini

W(n) = 2 W(n/2) + n - 1 pour n > 1

W(n) = 2 ( 2 W(n/4) + n/2 –1) + n - 1

= 22 W(n/4) + n-2 + n - 1

= 2 ( 2 ( 2 W(n/8) + n/4 –1 ) + n/2 –1) + n - 1

= 23 W(n/8) + n-4 + n-2 + n - 1

= 2i W(n/ 2i ) + n- 2i-1 + n- 2i-2 + …. + n-2 + n - 1

= 2i W(n/ 2i ) + Σ (n- 2j )

i-1

j=0

CSI3505 - Paola Flocchini

W(n) = 2i W(n/ 2i ) + Σ (n- 2j )

i-1

j=0

Nous savons que W(1) = 0

1 = n/ 2i quand i = log n

Σ Xi= Xi-1

X -1

i=0

log n -1

W(n) = 0 + Σ (n- 2j )

j=0

log n -1

= Σ n - Σ 2j

j=0

= n log n – 2 log n -1

2 -1

CSI3505 - Paola Flocchini

Exemple - Le tri de Hoare - QUICKSORT

Choisir comme pivot l'un des éléments du

tableau

Partitionner le tableau autour du pivot.

On déplace les éléments de telle

sorte que ceux qui sont supérieurs

se retrouvent a droite du pivot, les

autres a gauche

Trier récursivement les sous-tableau sans

besoin de fusionner

Quicksort(bas, haut)

{ trie le tableau T[bas...haut] en ordre croissant }

si ( haut > bas )

piv ← Pivoter(bas, haut)

Quicksort(bas,piv-1)

Quicksort(piv +1, haut)

{ suite au pivotage,

bas≤ k < piv ⇒ T[k] ≤ T[piv ]

et piv ≤ k < haut ⇒ T[k] > T[piv] }

CSI3505 - Paola Flocchini

Pivoter(bas, haut)

{permute les éléments du tableau de telle sorte que, a la fin bas≤ piv < haut,

tous les éléments de T[bas.. piv -1] sont inférieurs ou égaux à T[piv]=p et les

éléments de T[piv+1 .. haut] sont supérieurs à p }

elempivot := T[bas]

j ← bas

for( i= bas + 1; i≤ haut; i++ )

if T[i] < elempivot then

{ j ← j+1

échanger T[i] et T[j] }

piv:=j

échanger T[bas] et T[piv]

return (piv)

CSI3505 - Paola Flocchini

Analyse de QUICKSORT- Cas Pire

Taille du problème: n, le nombre d'éléments

Opérations élémentaires: echanges

Pire Input: ???

CSI3505 - Paola Flocchini

Analyse de QUICKSORT- Cas Pire

1. Diviser : n-1 (le temps pour pivoter)

2. Résoudre: récursivement deux sous-problèmes de

taille 0 et n-1. Donc on a besoin de W(0) + W(n-1)

3. Combiner: rien

CSI3505 - Paola Flocchini

Partitionnement non -équilibré à chaque étape de l'algo

Tableau déjà trié

W(n) = W(0) + W(n-1) + n-1

pivotage ..

Pour trier la partie gauche

Pour trier la partie droite

W(n) = W(n-1) + n-1

W(0) = 0

n>0

CSI3505 - Paola Flocchini

O(n2)

CSI3505 - Paola Flocchini

Analyse de QUICKSORT- Cas meilleur

Analyse de QUICKSORT- Cas moyen

Partitionnement produit deux régions de taille n/2

toutes les permutations des nombre d'éntrées sont

W(n) = 2W(n/2) + n-1

W(0) = 0

n>0

O(n log n)

CSI3505 - Paola Flocchini

A(n) = n-1 + 1/n Σ A(p-1) + Σ A(n-p) =

p=1

n-1 + 2/n Σ A(p-1) =

p=1

A(1) = A(0) = 0

A(n) = n-1 + 2/n Σ A(p-1)

p=1

équiprobables

⇒

Certain pivotages sont bien équilibrés, certains sont

déséquilibré

A(1) = A(0) = 0

A(n) = Σ 1/n [ A(p-1) + A(n-p) ] + n-1

p=1

Probabilité que le

pivot soit en position p

Trier sous-tableau quand

le pivot est en position p

CSI3505 - Paola Flocchini

Pivotage

A(1) = A(0) = 0

A(n) = n-1 + 2/n Σ A(p-1)

p=1

A(n) = n-1 + 2/n Σ A(p-1) =

n A(n) = n(n-1) + 2 Σ A(p-1)

p=1

(n-1) A(n-1) = (n-1) (n-2) + 2 Σ A(p-1)

Donc pour n-1

n-1

p=1

soustracting

n A(n) - (n-1) A(n-1) = 2(n-1) + 2 A(n-1)

CSI3505 - Paola Flocchini

n A(n) - (n-1) A(n-1) = 2(n-1) + 2 A(n-1)

n (n+1)

A(n) = A(n-1) + 2(n-1)

(n+1)

n (n+1)

Soit an = A(n)/ (n+1)

an = an-1 + 2/n

O(nlog n)

an = an-1 + 2(n-1)

n (n+1)

a0 = 0

Similaire a: an = an-1 + 2/n

CSI3505 - Paola Flocchini

Exemple: Sélection de la médian

Plus général: sélection de l’élément k-eme.

2 6 4 8 10 18 3 9 19 13 14

2 3 4 6 8 9 10 13 14 18 19

médian

Faisons l’hypothèse que les éléments sont distincts

Algorithme simple

Trier: O(n log n)

Prendre l’élément en position n/2

O(n log n)

CSI3505 - Paola Flocchini

Exemple: Sélection de la médian

Select(S,k)

Algorithme linéaire

Hypothèses (pour simplicité):

1) Les éléments sont distincts

2) n = 5 (2r +1)

Ex: n = 35 ou n = 55 ….

CSI3505 - Paola Flocchini

1) si |S| ≤ 5

retourner l’elem. K-eme

2) Diviser les élément en groupes de cinq et trouver

la médian de chaque groupe. Soit M l’ensemble qui contient

les médians.

> m1

< m1

> mi

…..

< mi

M = {m1 , … , mi , … , m2r +1 }

CSI3505 - Paola Flocchini

n = 5 (2r +1)

Select(S,13)

> m1

< m1

CSI3505 - Paola Flocchini

3) m* = Select(M,|M|/2)

A> mi

…

< mi

< m*

> m*

…

Select(M,3)

> 7

CSI3505 - Paola Flocchini

3) m* = Select(M,|M|/2)

A> mi

…

< mi

< m*

> m*

…

4) Comparer chaque élément en A et D avec m*

Soit S1 = C ∪ { clef de A ∪ D qui sont plus petits que m*}

Soit S2 = B ∪ {clef de A ∪ D qui sont plus grands que m*}

> 7

Soit S1 = C ∪ { clef de A ∪ D qui sont plus petits que m*}

Soit S2 = B ∪ {clef de A ∪ D qui sont plus grands que m*}

Je cherche maintenant le 7-eme de ce qui reste

S1 = 2,3,5,6

S2 = 8,10,11,14,15,17,21,22

CSI3505 - Paola Flocchini

5) Si ( k = |S1| +1 ) m est le k-eme, retourner m

sinon si (k <= | S1 | )

le k-eme se trouve en S1

retourner (Select(S1,k) )

sinon

le k-eme se trouve en S2

retourner (Select(S2,k-|S1|-1) )

Complexité

Soit n = 5 (2r +1)

Taille du problème: n, le nombre d'éléments

Opérations élémentaires: comparaisons

Pire Input: ???

S1 = 2,3,5,6

S2 = 8,10,11,14,15,17,21,22

CSI3505 - Paola Flocchini

(Select(S2,7-4-1) )

CSI3505 - Paola Flocchini

n = 5 (2r +1)

r groupes de 5

…

< m*

2(r+1) +r = 3r +2

> m*

…

2) Diviser les élément en groupes de cinq et trouver la médian de

chaque groupe

Trouver la median d’un groupe de 5 = 6 comparaisons

3r +2

Tot: 6 n/5 comparaisons

3) m* = Select(M,|M|/2)

|M| = n/5

W(n/5) comparaisons

4) Comparer chaque élément en A et D avec m*

4 r comparaisons

|A| + |D| = 4r

CSI3505 - Paola Flocchini

S1 = C ∪ { clef de A ∪ D qui sont plus petits que m*}

S2 = B ∪ {clef de A ∪ D qui sont plus grands que m*}

5) Si ( k = |S1| +1 ) retourner m*

sinon si le k-eme se trouve en S1

retourner (Select(S1,k) )

sinon retourner (Select(S2,k) )

Cas Pire:

tous les 4r éléments dans A et D sont dans la même cote de m*

( tous plus petits ou tous plus grands).

B et C contienent 3r + 2 elem chacun

Max{| S1 | ,| S2 |} = |A|+|D|+|C| = 7r +2

W(7r + 2) comparaisons

CSI3505 - Paola Flocchini

6 n/5 + W(n/5) + 4 r + W(7r + 2)

r est approximativement n/10 -

W(n) ≤ 1.2 n + W(n/5) + 0.4 n + W(7/10 n)

W(n) ≤ W(n/5) + W(7/10 n) + 1.6 n

Solution: O(n)

CSI3505 - Paola Flocchini

Exemple - Algorithme de Strassen pour la

Exemple - Algorithme de Strassen

multiplication matricielle

L’algorithme 1.4 a une complexité de W(n) = n3.

Avec l’Algorithme 1.4, pour multiplier deux matrices de

taille 2x2 on a besoin de faire 23 =8 multiplications

a11 a12

a22

a21

b11 b12

b22

b21

c11 c12

c22

c21

On peut le faire en utilisant 7 multiplications scalaires

L'idée de Strassen

Calculer 7 valeurs: m1, m2 … m7

chaqu'un avec une seule multiplication.

ou c12 = a11 b12 + a12 b22

Exprimer chaque cij comme somme et soustractions des mi

CSI3505 - Paola Flocchini

m1 = (a11 + a22 ) (b11 + b22 )

m2 = (a21 + a22 ) b11

m3 = a11 (b12 - b22 )

m4 = a22 (b21 - b11 )

m5 = (a11 + a12 ) b22

m6 = (a21 - a11 ) (b11 + b12 )

m7 = (a12 - a22 ) (b21 + b22 )

m1 + m4 - m5 + m7

m3 + m5

C =

m2 + m4

m1 + m3 - m2 + m6

Verifique …...

c12

doit être égal a

a11 b12 + a12 b22

CSI3505 - Paola Flocchini

Exemple - Algorithme de Strassen

• Vérification:

m1 + m4 - m5 + m7

= (a11 + a22 ) (b11 + b22 ) + a22 (b21 - b11 ) -(a11 + a12 ) b22 + (a12 - a22 ) (b21 + b22 )

= (a11 b11 + a11 b22+ a22b11 + a22b22) + (a22b21 - a22b11 ) -(a11b22 + a12b22) +

(a12 b21+ a12 b22 - a22b21 - a22b22 ) =

= a11 b11 + a12 b21 = c11

m1 + m4 - m5 + m7

m3 + m5

C =

m2 + m4

m1 + m3 - m2 + m6

CSI3505 - Paola Flocchini

Exemple - Algorithme de Strassen

Pour les matrices de taille plus grande que 2 on applique

la même stratégie.

Pour simplifier l’analyse on suppose que n est une

puissance de 2 …… n = 2 k

Décomposer la matrice de taille nxn en 4 sous matrices,

chacune de taille n/2 x n/2

Disons que n est une puissance de 2 …… n = 2 k

Décomposer chaque matrice en 4 sous-matrices

A11

A12

A21

A22

A = 2n x 2n

A11 = n x n

A11 =

a11 a12 ……..

a22

a21

a1n/2

a2n/2

an/2 1 an/2 2

an/2 n/2

CSI3505 - Paola Flocchini

M1 = (A11 + A22) ( B11 + B22)

CSI3505 - Paola Flocchini

Exemple - Algorithme de Strassen

Nous pouvons alors multiplier deux matrices

2n x 2n avec 7 multiplications de matrices n x n

(plus un certain nombre de soustractions)

c11 c12

c22

c21

C11

C21

C12

C22

a11 a12

a22

a21

A11

A12

A21

A22

b11 b12

b22

b21

B11

B21

B12

B22

M1 + M4 - M5 + M7

M3 + M5

C =

M2 + M4

M1 + M3 - M2 + M6

CSI3505 - Paola Flocchini

Strassen(n,A,B,C)

if n <= seuil then

calculer C ← A x B en utilisant l'algo classique

else

partitionner A en 4 sous-matrices A11 A12 A21 A22

partitionner B en 4 sous-matrices B11 B12 B21 B22

calculer C ← A x B en utilisant Strassen

Strassen(n/2, A11+ A22, B11+ B22 , M1)

Strassen(n/2, A21 + A22 , B11 , M2)

…

Strassen(n/2, A12 - A22 , B21 + B22 , M7)

C ← sommes et soustractions des Mi

Algorithme de Strassen : analyse du cas pire

Taille du problème: n

Opérations élémentaires: multiplications

Pire Input: ?

n = 2 k

Nous allons considerer comme seuil: n = 1

W(1) = 1

W(n) = 7 W(n/2)

CSI3505 - Paola Flocchini

W(1) = 1

W(n) = 7 W(n/2)

= 7 W(2k-1)

= 7 ( 7 W(2k-2 ))

= …

= 7i W(2k-i )

= …

= 7k W(20)

= 7k W(1)

= 7k

W(n) = 7 log n

CSI3505 - Paola Flocchini

Théorème

Prouver formellement que W(n) = 7 log n

Preuve

Par induction.

Base.

W(1) = 1

Hypothèse

d'induction.

vrai pour 1 ≤ m ≤ n

Considère n.

W(n) = 7 W(n/2)

= 7 (7 log (n/2) )

= 7 log (n/2) + 1

= 7 log n - log2 + 1

= 7 log n - 1 + 1

CSI3505 - Paola Flocchini

= 7 log n

Résume

Multiplication matricielle

• Et si on ne compte que les additions et

soustractions:

Algorithme classique (1.4): n2 (n-1) = n3 – n2

n x n

A x B

n x n

1. Algo classique (1.4)

2. Algo de Strassen

Algorithme Strassen: (voir Exemple B.20, App.B)

W(n) = 7 W(n/2) + 18 (n/2)2

W(1) = 0

Solution: 6nlog7 – 6n2 = 6n2.81 – 6 n2

Classique

Strassen

Multiplications

n2.81

7 log n =

Additions +

soustractions

n3 -n2

6n 2.81 - 6 n 2

CSI3505 - Paola Flocchini

Dans le pire cas, la complexité de Strassen est

O (n2.81)

Peut-on faire mieux que Strassen?????

Coppersmith & Winograd (1987) O(n 2.38)

On ne peux pas faire mieux que Ω(n2)

Ω(n2) ≤ Meilleure algorithme ≤ O(n 2.38)

CSI3505 - Paola Flocchini

Diviser pour régner et Analyse des Algorithmes

Diviser pour régner et Analyse des Algorithmes