DIVISER POUR RÉGNER - Université Lavalbherer/AAE04/cours7hans.pdfAnalyse d’Algorithmes 2001 Ch. 7 - DIVISER POUR RÉGNER 5 2. DÉTERMINATION DU SEUIL Détermination théorique

Analyse d’Algorithmes 2001 Ch. 7 - DIVISER POUR RÉGNER 1

CHAPITRE 7DIVISER POUR RÉGNER

Les numéros de section correspondent à l’ancienne structure du contenu;les numéros correspondants des sections du livre sont entre parenthèses

les numéros de page de ces transparents sont à droite.

1. Principe général (7.2) 2

2. Détermination du seuil (7.2) 5

3. Recherche binaire (7.3) 11

4. Tri par fusion (7.4.1) 15

5. Tri de Hoare (7.4.2) 17

6. Sélection et recherche de la médiane (7.5) 24

7. Arithmétique des grands entiers (7.1) 33

8. Multiplication matricielle (7.6)(voir livre)

9. Exponentiation (introduction à la cryptologie) (7.7)(hors programme)

2 Ch. 7 - DIVISER POUR RÉGNER ©2001 R. Lelouche

1. PRINCIPE GÉNÉRAL

TECHNIQUE DE CONCEPTION D’ALGORITHMES

- Décomposer l’exemplaire à résoudreen sous-exemplaires plus petits

- Résoudre le même problèmepour chaque sous-exemplaire indépendamment

- Combiner les sous-solutions obtenuesafin de parvenir à la solution de l’exemplaire original

L’intérêt de cette technique repose sur la facilitéavec laquelle on peut résoudre chaque sous-exemplaire

et recombiner les solutions obtenues.

Exemple

Soient:

• un algorithme A qui prend un temps tA(n) ≤ c n2,

• un algorithme B qui:- décompose l’exemplaire de taille n en 3 sous-exemplaires,- résout ces 3 sous-exemplaires de taille n/2 à l’aide de l’algorithme A,- combine ces résultats pour fournir la réponse.

tB(n) = 3 tA(n/2 ) + t(n)

où t(n) est le temps requis pour faire la décomposition des sous-exemplaireset la recombinaison des solutions partielles on suppose que t(n) ≤ d n. Alors:

tB(n) ≤ 3 c (n+12 )2 + d n

= 34 c n2 + (32 c + d) n + 34 c

Donc:tB(n) ∈ O(n2) est encore vraiemais B est 25% plus rapide que A lorsque n est élevé.



ALGORITHME C

Identique à l’algorithme B sauf que:1º Les sous-exemplaires sont résolus en appelant

récursivement l’algorithme C;2º Si la taille de l’exemplaire à traiter

est inférieure à un certain seuil n0c’est l’algorithme A qui est appelé (au lieu de C).

tC(n) = tA(n) si n ≤ n 0 3 tC( n/2 ) + t(n) sinon

Analyse

Cette approche donne un résultat

tC(n) ∈ O(nlg 3)

Note

Le problème propre à cette approche est le suivant:

Choisir n0 de façon à minimiser la constante cachée...



Fonction DPR(x)

Retourne la solution y de l’exemplaire x Si x est “suffisamment petit” ou “simple” alors

Retourner ADHOC(x) ADHOC est le sous-algorithme de base,servant à résoudre les petits exemplaires

sinon x doit être décomposéDécomposer x en sous-exemplaires plus simples

x1, x2, ..., xk.

Pour i ← 1 jusqu’à k faire yi ← DPR (xi)Combiner les yi pour obtenir une solution y de x.Retourner y.

Fin.

Notes

En général, k ne dépend pas de n.

Conditions pour que la technique soit efficace:a) sous-algorithme de base efficace;b) décomposition efficace de x en sous-exemplaires

et combinaison efficace des sous-solutions;c) décision judicieuse d’utiliser ADHOC;d) sous-exemplaires de tailles semblables.


2. DÉTERMINATION DU SEUIL

Détermination théorique

Exemple précédent

tC(n) = tA(n) s i n ≤ n0 3 tC( n/2 ) + t(n) sinon

Pour déterminer le n0 réduisant le plus possible la valeur detC(n), il ne suffit pas de savoir que tA(n) ∈ Θ(n2) et t(n) ∈ Θ(n).

A) Le choix du seuila une influence considérable sur l’efficacité de l’algorithme.

Prenons tA(n) = n2 millisecondes et t(n) = 16n millisecondes.Considérons un exemplaire de taille 1024. Il prend:

30 minutes avec n0 = 1 (algorithme C)15 minutes avec n0 = ∞ (algorithme A)8 minutes avec un bon choix de n0.

Exercice 4.2.2. - Quelles valeurs de n0 permettent d’obtenirce résultat optimal ?

B) En général, le choix du seuil optimal dépendnon seulement de l’algorithme, mais aussi de l’implantation.



Problème 4.2.1

On garde tA(n) = n2, t(n) = 16n.Choisissons un seuil n0 = 2k, pour un k ≥ 0 donné.Temps pour traiter un exemplaire de taille n = 2p, avec p ≥ k ?

Analyse

Équation de récurrence (posons tp = tC(2p)) :

tp = 4k s i p = k 3 tp – 1 + 16 * 2p s i p > k

Équation caractéristique: (x–3) (x–2) = 0Forme de la solution générale : tp = c1 3p + c2 2p.

Les conditions initiales sont les expressions de tp pour p = ket pour p = k+1. Elles conduisent à

c1 = 2k (2k + 32) 3–k c2 = –32

Solution générale exacte:tp = 2k 3p–k (32+2k) – 2p+5 millisecondes

Application (problème 4.2.2)

Considérons un exemplaire de taille 1024 = 210 (p = 10). On a pour le seuil 2k:t(k) = 2k 310–k(32+2k) –215 msec.

On peut essayer de minimiser par rapport à k:t’(k) = 0 ⇔ k = lg (–32 log(2/3) / log(4/3))

qui donne k ≅ 5,5

Essayons différentes valeurs de k autour de 5.5:k 4 5 6 7

t(k) 8,78 7,75 7,75 8,67

⇒ n0 = 32 (k = 5) ou n0 =64 (k = 6) fait l’affaire.

Note: Le seuil optimal n’est pas nécessairement unique.



Dans une implantation spécifique

À partir d’une implantation spécifique, on peut déterminer unseuil empiriquement:

2 paramètres: le seuil et la taille d’un exemplaire.

⇓Très coûteux en frais d’ordinateur!

Approche hybride

- Déterminer théoriquement la forme des équations derécurrence.

- Trouver empiriquement la valeur des constantesimpliquées, pour l’implantation considérée.

- Trouver expérimentalement n, de manière telle que lestemps pris par l’algorithme de base et celui “Diviser pourRégner” avec un appel récursif seulement soient égaux.

Note:

Si tA(n) ∈ O(n2), il se peut quetA= a n2 + bn + c

où a, b, c dépendent de l’implantation.

Lorsque nous voulons déterminer le seuil, le terme bn+c nepeut être considéré comme négligeable (nous ne sommespas dans les conditions asymptotiques).



Problème 7.8 (4.2.3 de l’ancien livre)

Soient a, b ∈ ℜ +. Soit s ∈ ℜ +. Soit fs: ℜ * → ℜ * définie par:

fs(x) = a x2 s i x ≤ s

3 fs(x2) + b x sinon

Prouvez par induction mathématique que, si u = 4ba et v est

un réel positif quelconque, alors fu(x) ≤ fv(x) ∀ x réel positif.

Preuve

Soit v ≠ u = 4ba .

1er cas: x ≤ min (u, v) ⇒ fu(x) ≤ fv(x).

2me cas: x > min (u, v).

Posons k = min i | x2i ≤ min (u, v). On va montrer par

induction sur j que: fu(x2j) ≤ fv(

x2j) pour j = k, k–1, ..., 0.

i) j = k

C’est vrai car x2k ≤ min (u, v).

ii) Supposons que c’est vrai pour j = i+1 ≤ k, c.-à-d. que:

fu(x

2i+1) ≤ fv(x

2i+1)et montrons que c’est vrai pour j = i (attention: l’inductionfonctionne par j décroissant). Trois cas sont à distinguer,

selon les positions relatives de u et de v par rapport à x2j.



Preuve du problème 7.8 (suite)

a)x2j ≤ u

⇒ x/2i > v

⇒ fu(x/2i) = a (x/2i)2 ≤ 16 b2 /a

fv(x/2i) = 3 fv(x/2i+1) + b (x/2i)

≥ 3 fu(x/2i+1) + b (x/2i)

= 3 a (x/2i+1)2 + b (x/2i)

= (x/2i) (b + 3ax / (4.2i))

⇒ fv(x/2i) – fu(x/2i) ≥ (x/2i) (b – ax / (4.2i)) ≥ 0

car x/2i ≤ u = 4b / a ⇒ ax / (4.2i) ≤ b.

b) x2j > u et

x2j > v

⇒ fu(x/2i) = 3 fu(x/2i+1) + b (x/2i)

≤ 3 fv(x/2i+1) + b (x/2i)

= fv(x/2i).



Preuve du problème 7.8 (fin)

c) x2j > u et

x2j ≤ v

⇒ fv(x/2i) = a (x/2i)2

fu(x/2i) = 3 fu(x/2i+1) + b (x/2i)

≤ 3 fv(x/2i+1) + b (x/2i)

= 3 a (x/2i+1)2 + b (x/2i)

= (x/2i) (b + 3ax / (4.2i))

⇒ fv(x/2i) – fu(x/2i) = (x/2i) (–b + ax / (4.2i)) ≥ 0

car x/2i > u = 4b / a ⇒ ax / (4.2i) > b.

Autre méthode

En essayant de résoudre l’équation de récurrence, on obtient:

fs(x) ∈ a x2 si x≤ s x 1,5lgx–lgs (2b+as) – 2bx si x≥s

fu(x) ∈ a x2 si x≤ u x 1,5lg(ax/4b) (6b) – 2bx si x≥u

Il s’agit de comparer fs(x) à fu(x) pour s < u et pour s > u.

Remarque importanteLa constante u a été choisie telle que a u2 = 3 a(u2)2 + b u. Ce problème illustre

la règle selon laquelle le seuil optimal d’un algorithme DPR peut s’estimer parla taille n de l’instance pour laquelle il est indifférent d’appliquer l’algorithmeadhoc de base ou d’effectuer un niveau supplémentaire de récursion.

Analyse d’algorithmes 2001 Chapitre 8: PROGRAMMATION DYNAMIQUE 1

CHAPITRE 8PROGRAMMATION DYNAMIQUE

Les numéros de section me sont propres;ceux correspondants au livre sont indiqués entre parenthèses;

les numéros de pages sont indiqués à droite.

1 Introduction (8.1) 2Principe d’optimalité (8.3) 4

2 La série mondiale (8.1.1) 5

3 Rendre la monnaie (8.2) 8

4 Problème du sac à dos (8.4) 10

5 Multiplication chaînée de matrices (8.6) 12

6 Les plus courts chemins (8.5) 15

7 Arborescences de fouille optimales 17

8 Le commis voyageur 21

2 Chapitre 8: PROGRAMMATION DYNAMIQUE ©2001 R. Lelouche

1 INTRODUCTION

La technique «diviser pour régner» peut nous amener à créerun grand nombre de sous-exemplaires identiques.

Exemple : Calcul du coefficient binomial

n

k

n

k =

n–1

k–1 +

n–1

k si 0<k<n

1 sinon

FONCTION C(n, k)SI k = 0 ou k = n ALORS

Retourner 1.SINON 0 ≠ k ≠ n

Retourner C(n–1, k–1) + C(n–1, k).FIN.

Le résultat est obtenu en faisant la somme d’un certain nombre de 1==> LE TEMPS DE CALCUL EST DANS Ω(C(n,k)).

TT rr èè ss cc oo ûû tt ee uu xx

C(n,k)

C(n-1,k-1) C(n-1,k)

C(n-2,k-2) C(n-2,k-1) C(n-2,k)

C(n-3,k-3) C(n-3,k-2) C(n-3,k-1)

Ainsi, beaucoup de valeurs C(i,j), i < n et j < k, sont recalculées plusieurs fois.

Analyse d’algorithm

es 2001C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

3

1 INT

RO

DU

CT

ION

ST

RA

TÉ

GIE

Résoudre chaque sous-exem

plaire différent une seule fois,en sauvegardant le résultat.

PR

OG

RA

MM

AT

ION

D

YN

AM

IQU

E

Méthode ascendante qui consiste à résoudre d’abord des

petits sous-exemplaires, com

biner leurs solutions pourobtenir des sous-exem

plaires de plus en plus grands. Et ainsi

de suite jusqu’à l’exemplaire original.

Exem

ple: Calcul de

nk

C(0,0)

C(1,0)

C(1,1)

C(2,0)

C(2,1)

C(2,2)

..........

..........

..........

..........

.....C

(k,0)C

(k,1)C

(k,2).....

.....C

(k,k)C

(k+1,0)

C(k+

1,1)C

(k+1,2)

..........

C(k+

1,k).....

..........

..........

..........

..........

..........

..........

..........

..........

.....C

(n–1,0)C

(n–1,1)C

(n–1,2).....

.....C

(n–1,k)C

(n,0)C

(n,1)C

(n,2).....

.....C

(n,k)

ST

RU

CT

UR

E D

E D

ON

NÉ

ES

:un vecteur de longueur k lequel est m

is à jour de la droitevers la gauche.

temps dans Θ

(n k)espace dans Θ

(k)

4C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

©2001 R

. Lelouche

1 INT

RO

DU

CT

ION

Définition du principe d’optim

alité

Dans une séquence de choix optim

ale,chaque sous-séquence de celle-ci doit aussi être optim

ale

Exem

ple

Si le plus court chem

in entre A et C

passe par B, les trajets A

-B et B

-C sont

aussi les plus courts.

Exem

ple 1

Supposons que l’on cherche au contraire le chem

in simple le plus long entre

deux points (simple =

sans boucle)

1

11

A

1

B1

C

1

Le plus long chemin de A

à C passe par B

; sa longueur est 2. Par contre, le

trajet A-B

n’est pas le plus long (longueur 1), puisque le trajet A-C

-B, qui est

de longueur 2, est plus long. Ainsi, dans ce cas,

Le principe d’optimalité ne s’applique pas.

Exem

ple 2

Supposons que l’on cherche le chem

in le plus rapide entre deux points, p. ex.entre Q

uébec et Montréal. Il passe par T

rois-Rivières. M

ais si on va aussi viteque possible à T

rois Rivières, on risque de tom

ber en panne d’essenceensuite. Les deux trajets les plus rapides ne sont pas indépendants(ressource com

mune). D

ans ce cas,

Le principe d’optimalité ne s’applique pas non plus.


es 2001C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

5

2 LA S

ÉR

IE M

ON

DIA

LE

Description

Il s’agit d’un tournoi où 2 équipes A et B

s’affrontent enm

atches successifs. Le tournoi se termine dès qu’une équipe

a remporté un nom

bre de victoires n fixé à l’avance.

Hypothèses:

-aucun m

atch nul;-

les résultats de chaque match sont indépendants.

Appelons:

-p la probabilité que A

gagne un match quelconque,

-q = 1 – p la probabilité que B

gagne un match quelconque,

-P

(i,j) la probabilité que A gagne la série alors que A

et Bont respectivem

ent besoin de i et j victoires additionnelles).

Avant le début du tournoi, on a:

-P

(n,n) = probabilité que A gagne la série (ce qu’on cherche),

-P

(0,i) = 1 pour tout i=1, 2, ..., n,-

P(i,0) = 0 pour tout i=1, 2, ..., n.

Ainsi:

P(i,j) = p P

(i–1,j) + q P(i,j–1),

∀i ≥ 1, j ≥ 1.

Exercice im

médiat: justifiez-le!

FO

NC

TIO

N P(i,j)S

I i = 0 ALO

RS R

etourner 1S

INO

N SI j = 0

ALO

RS R

etourner 0S

INO

N Retourner p P

(i–1,j) + q P(i,j–1).

Soit T

(k) le temps requis en pire cas pour calculer P

(i,j), où k = i + j. On a:

T(1) = c

T(k) ≤ 2T

(k–1) + d, k > 1qu’on sait résoudre par la m

éthode de l’équation caractéristique. On obtient:

T(k) ∈

O(2

k)

6C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

©2001 R

. Lelouche

2 LA S

ÉR

IE M

ON

DIA

LE

Étude des appels récursifs

En exam

inant les appels récursifs générés, on a:

P(i,j)

P(i–1,j)

P(i,j–1)

P(i–2,j)

P(i–1,j–1)

P(i,j–2)

P(i–r, j–(a–r))

(avec r =0,1...,a et a–j ≤ r ≤ i)

il reste k matches

il reste k–1 matches

il reste k–2 matches

il reste k–a matches

P(1,0)

il reste 1 match

.........

.........

ce qui est identique au calcul naïf de C(i+j,j).

D’où pour le nom

bre total d’appels récursifs (exercice 1):

2

i+jj – 2

Ainsi, le tem

ps de calcul de P(i,j) est dans Ω (

i+

jj)

et donc celui de P(n,n) dans Ω(

2nn

), donc (cf. problème 1.42)

dans Ω( 4nn).

Cela est très coûteux pour les grandes valeurs de n


es 2001C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

7

2 LA S

ÉR

IE M

ON

DIA

LE

Algorithm

e basé sur la programm

ation dynamique

(voir algorithme form

el dans le livre, p. 262)

Significations de k et s

•k = i + j (com

me pour la page 5)

•s est le num

éro de la diagonale en cours de traitement

(variable de contrôle de la boucle la plus externe).

s

k0

12

34

. . .n

0123

0

1

0

1

0

pp

p(2-p)

1

...

n0

P(n,n)

...

1. . .

1

p

Calcul de l’efficacité

Tem

ps: Avec cet algorithm

e, le temps de calcul est dans

Θ(n

2), c’est-à-dire le temps pris pour rem

plir le tableau n × n.

Espace m

émoire: Il n’est pas nécessaire d’utiliser un tableau:

un vecteur de longueur n suffit (diagonales successives dutableau carré n × n ). D

onc espace dans Θ(n).

8C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

©2001 R

. Lelouche

3 RE

ND

RE

LA M

ON

NA

IE(livre section 8.2, p. 263-265)

Description du problèm

e

Déjà vu lors de l’étude des algorithm

es voraces.

L’algorithme vorace ne m

arche pas pour certains systèmes

de dénominations de pièces.

Exem

ple: système com

prenant des pièces de 1, 4 et 6 ¢.R

endre 8¢ demanderait 3 pièces par l’algo vorace (6+1+1)

au lieu de 2 (4+4).

Résolution par program

mation dynam

ique

Soit à rendre N

cents en utilisant n types de pièces. Pour

cela, on remplit un tableau N

bPièces de n lignes (une par

catégorie de pièces) et N colonnes (la som

me à rendre).

NbP

ièces [i, j] contient le nombre m

inimal de pièces à utiliser

pour rendre j ¢ en utilisant seulement des pièces des

catégories 1 à i. Il s’agit donc de calculer NbP

ièces [n, N].

Pour tout i et tout j, on a (pourquoi?):

NbP

ièces [i, j] = Min (N

bPièces [i–1, j], N

bPièces [i, j–d

i ] + 1

où di est la dénom

ination des pièces de la catégorie i.

Pour rendre 8 cents avec les pièces ci-dessus, on est conduit

ainsi à remplir le tableau suivant indiquant , N

bPièces [i, j],

le nombre m

inimum

de pièces à utiliser pour rendre la somm

e j en utilisantuniquem

ent les pièces de dénomination 1 à i:

Som

me:

01

23

45

67

8

d1 = 1

01

23

45

67

8d

2 = 40

12

31

23

42

d3 = 6

01

23

12

12

2

PROBLÈMES

-1- Lors de la phase de conception d’un circuit électrique, on a souvent besoin de relier entre elles les broches de composants électriquement équivalents. Pour interconnecter un ensemble de n broches, on peut utiliser un arrangement de n-1 câbles, chacun reliant deux broches. Parmi tous les arrangements possibles, celui qui utilise une longueur de câble minimale est souvent le plus souhaitable. Comment déterminer cet arrangement ?

-2- Comment rendre la monnaie ?

PROBLÈME Lors de la phase de conception d’un circuit électrique, on a souvent besoin de relier entre elles les broches de composants électriquement équivalents. Pour interconnecter un ensemble de n broches, on peut utiliser un arrangement de n-1 câbles, chacun reliant deux broches. Parmi tous les arrangements possibles, celui qui utilise une longueur de câble minimale est souvent le plus souhaitable. Comment déterminer cet arrangement ?

MODÉLISATION On peut modéliser ce problème de câblage à l’aide d’un graphe non orienté connexe

ANG ,= où N est l’ensemble des broches et A l’ensemble des connexions possibles entre paires de broches. De plus, pour chaque arête u,v ∈ A on a une «valeur» (longueur, coût,…) w(u,v) qui spécifie le «coût» de u,v. Le problème est alors de trouver un sous-ensemble acyclique T ⊆ A qui connecte tous les sommets et dont le cout total :

∑

∈

=Tvu

vuwTw,

),()( est minimal.

C’est le problème de l’arbre couvrant minimal (MST).

APPROCHE Compte tenu de la nature du problème, nous aimerions utiliser une approche vorace pour l’obtention d’une solution (choix optimal ponctuel). Nous optons pour cette approche car nous remarquons les faits suivants (constituants de l’approche vorace):

i) Les candidats sont les arêtes de G. ii) Un ensemble d’arêtes est une solution si cet ensemble constitue un arbre

de recouvrement. iii) Un ensemble d’arêtes est réalisable s’il est acyclique. iv) La fonction de sélection variera selon l’algorithme. v) La fonction objective consiste à minimiser le coût total de l’arbre de

recouvrement. Deux stratégies nous viennent à l’esprit :

a) Choisir les arêtes en partant de celle de coût minimal et ainsi de suite jusqu’à l’obtention d’un MST. (Algorithme de Kruskal)

b) En partant d’un sommer arbitraire, construire de proche en proche un MST en faisant un choix vorace à chaque étape. (Algorithme de Pri

ALGORITHMES

1- Algorithme de Kruskal Fonction Kruskal( ANG ,= ;coût : A → ℜ +) : ensemble d’arêtes Trier A en ordre croissant de coût n ← | N | T ← ∅ initialiser les n singletons repeat e ← u,v ← arête de coût minimum disponible ucomp ← find(u) vcomp ← find(v) if ucomp ≠ vcomp then merge(ucomp,vcomp) T ← T ∪ e

until | T | = n – 1 return T

2- Algorithme de Prim

a) Générique Fonction Prim( ANG ,= ;coût : A → ℜ +) : ensemble d’arêtes

T ← ∅ B ← élément arbitraire de N while B ≠ N do Trouver e = u,v de cout minimum tel que U ∈ B et v ∈ N \ B T ← T ∪ e B ← B ∪ v return T

b) Implantation avec matrice symétrique Fonction Prim(L[1..n,1..n]) :ensemble d’arêtes

T ← ∅ for i = 2 to n do nearest[i] ← 1

mindist[i] ← L[i,1] repeat n-1 times min ← ∞ for j ←2 to n do If 0 ≤ mindist[j] < min then

min ← mindist[j] k ← j T ← T ∪ nearest[k],k mindist[k]← -1 /* k est maintenant dans B For j ← 2 to n do If L[j,k] < mindist[j] then mindist[j]←L[j,k] nearest[j]←k return T

Analyse d’Algorithmes 2001 Ch. 6 - APPROCHE VORACE 7

Algorithme de Kruskal

PRINCIPE

À chaque itération, on ajoute la plus petite arête parmicelles qui ne créent pas de cycle, quelle que soit sa localisation

EXEMPLE

12

3

4 5 6

7

1 2

6

3

54

8

6

743

4

a) Tri des arêtes en ordre de longueurs croissantes(1,2), (2,3), (4,5), (6,7), (1,4), (2,5), (4,7), (3,5), (2,4), (3,6), (5,7), (5,6).

b) Arête ajoutée Composantes connexes associées(Initialisation) 1, 2, 3, 4, 5, 6, 7→ (1,2) 1,2, 3, 4, 5, 6, 7→ (2,3) 1,2,3, 4, 5, 6, 7→ (4,5) 1,2,3, 4,5, 6, 7→ (6,7) 1,2,3, 4,5, 6,7→ (1,4) 1,2,3,4,5, 6,7

(2,5) (refusée)→ (4,7) 1,2,3,4,5,6,7.

8 Ch. 6 - APPROCHE VORACE ©2001 R. Lelouche

Algorithme de Kruskal ( suite)

FONCTIONNEMENTThéorème 6.3.2, p. 193 sq. (ancien problème 3.2.2)

L’algorithme de Kruskal fonctionne correctement

PreuveIl est clair que les arêtes retenues à la fin forment un graphe connexe et sanscycle, donc un arbre sous-tendant. Il suffit de montrer qu’il est à coût minimal,c’est-à-dire qu’à chaque étape, incluant la dernière, les arêtes retenuesforment un ensemble prometteur.

Base

C’est vrai pour l’état initial (il n’y a aucune arête, et l’ensemble vide esttrivialement prometteur).

Induction

Hypothèse d’induction: Supposons que c’est vrai pour k–1 arêtes, c’est-à-direque les k–1 premières arêtes forment un ensemble prometteur.

Soit e = (u, v) la ke arête choisie. Soit B l’ensemble des sommets reliés à uavant l’ajout de e. Avant l’ajout de e, B est inclus strictement dans N car vn'appartient à B. De plus, aucune arête ne quitte B (ne relie B à N–B). Enfin,e est de longueur minimale parmi les arêtes qui quittent B. Donc, le lemmede l’augmentation d’un ensemble prometteur peut s’appliquer, et par suitel’ensemble des arêtes retenues après l’ajout de e est prometteur.

Lorsque la dernière arête est ajoutée, l’ensemble des arêtes accumulées estprometteur, c’est-à-dire que l’arbre sous-tendant obtenu est minimal.


Algorithme de Kruskal ( suite)

IMPLANTATION

1˚ Choix des structures de données

Pour chaque arête (x,y), il faut déterminer à quelle composante connexe x ety appartiennent.

- détection de cycles- fusion de 2 ensembles

Choix: structure d’ensembles disjoints.

2˚ Algorithme

FONCTION Kruskal (G=<N,A>: graphe;longueur: tableau [A] ∈ R*): ensemble d’arêtes

DÉBUT.Trier A par longueurs croissantes.n ← Card(N); C ← A; T ← Ø.Former une composante pour chacun des nœuds de N.TANT QUE Card(T) < n – 1 FAIRE

N.B. - L’algorithme ne marcherait pas si on mettait n au lieu de n–1:dès que Card(T) = n – 1, on chercherait en vain à ajouter à T une ne arête

(u,v) ← plus courte arête de C.Enlever l’arête (u,v) de C.Ucomp ← Trouver (u). trouver la composante Ucomp contenant uVcomp ← Trouver (v). trouver la composante Vcomp contenant vSI Ucomp ≠ Vcomp ALORS

Fusionner (Ucomp, Vcomp).Ajouter l’arête (u,v) à T.FIN SI.

FIN TANT QUE.RETOURNER T.FIN.

Exercice (problème 6.10 a ou ancien 3.2.4)Qu’arrive-t-il si, par erreur, on fait tourner l’algorithme sur un graphe nonconnexe?


Algorithme de Kruskal (suite)

ANALYSE

Soit un graphe G ayant n sommets et a arêtes.

1º Tri des arêtes

Il y a a arêtes, d’où un tri dans O(a lga)

Mais n–1 ≤ a ≤ n (n–1)2 . Donc O(a) ⊆ O(n2) d’où O(lga) = O(lgn).

D’où un tri dans: O(a lgn)

2º Initialisation des n ensembles

Dans O(n)

3º Opérations Trouver et Fusionner

Comme il y a au plus 2a opérations Trouver et n–1 opérations Fusionner surun univers à n éléments, ce nombre est en pire cas dans:

O((2a + n–1) lg* n)

où lg* n ≡ min k | lg lg...lgn ≤ 0.k fois

Mais O(lg*n) ⊆ O(lgn) (voir exemple 2.2.10) et O(a + n) = O(a) par 1º.

Donc au plus dans: O(a lgn)

D’où un ordre global pour l’algorithme de Kruskal:

O(a lgn)

—> Problème 6.9 ou ancien 3.2.5 (exercice 3)


Algorithme de Prim

PRINCIPE

KRUSKAL: Choix d’arêtes prometteuses sans nous préoccuper desconnexions avec les arêtes déjà choisies.

PRIM : À chaque étape, nous avons un (seul) arbre sous-tendantminimal partiel B.

EXEMPLE (le même)

12

3

4 5 6

7

1 2

6

3

54

8

6

743

4

arête ajoutée B correspondant1

(1,2) 1, 2(2,3) 1, 2, 3(1,4) ou (2,5) 1, 2, 3, 4 ou 1, 2, 3, 5(4,5) ou (5,4) 1, 2, 3, 4, 5 ou 1, 2, 3, 4, 5(4,7) 1, 2, 3, 4, 5, 7(6,7) 1, 2, 3, 4, 5, 6, 7


Algorithme de Prim ( suite)

IDÉE GÉNÉRALE DE L’ALGORITHME

FONCTION PRIM (G=<N, A>: graphe;Longueur: Tableau[A] ∈ R*): ensemble d’arêtes;

DÉBUT.T ← Ø;B ← un élément quelconque de N;TANT QUE B ≠ N les sommets ne sont pas tous atteints FAIRE

Trouver (u,v) une arête de longueur minimaletelle que u ∈ N–B et v ∈ B;

T ← T ∪ (u,v)B ← B ∪ u.FIN TANT QUE.

Retourner T.FIN Prim.

<B, T> est un arbre sous-tendant minimal

FONCTIONNEMENT (Théorème 6.3.3 ou anc. problème 3.2.6 )

L’algorithme de Prim fonctionne correctement

Procédons par induction sur le nombre de sommets dans B. Il s’agit demontrer qu’à chaque itération T forme un ensemble prometteur.

Cas initial B contient un seul élément.

Évident.

Cas récurrent

Supposons que, au début d’une itération, T forme un ensemble prometteur.Alors l’arête e = (u,v) que l’on ajoute dans le corps de bouclepossède une extrémité dans B et l’autre dans N – B, donc e quitte B.Aucune arête de T ne quitte B.L’arête e est celle de longueur minimale parmi les arêtes qui quittent B.D’après le lemme 6.3.1 (p. 6), T ∪ e forme un ensemble prometteur.

VALIDITÉ DES ALGORITHMES

Cette partie est habituellement une des plus difficiles. Montrer formellement qu’un algorithme (et par la suite son implantation, ce qui est alors encore plus difficile !) résout le problème est une partie intéressante et de plus en plus importante en informatique théorique. Avant de montrer la validité de nos algorithmes, il nous faut quelques définitions et surtout un lemme qui nous sera très utile ! Définitions :

1) Solution : ensemble d’arêtes T tel que <N,T> soit un arbre de recouvrement.

2) Ensemble réalisable : ensemble d’arêtes ne contenant aucun cycle.

3) Ensemble prometteur : ensemble réalisable qui peut être compléter pour former une solution réalisable optimale.

4) Une arête quitte un ensemble de sommets si une de ses deux extrémités est dabs cet ensemble et l’autre pas.

Lemme de l’augmentation d’un ensemble prometteur Soit ANG ,= un graphe connexe non orienté, avec un coût associé à chaque arête. Soit B ⊂ N un sous-ensemble strict des sommets de G et soit T ⊆ A un ensemble prometteur d’arêtes tel qu’aucune arête de T ne quitte B. Soit e une arête de coût minimal parmi celles qui quittent B. Alors T ∪ e est prometteur.

Preuve (en classe) Théorème 1 : L’algorithme de Kruskal fonctionne correctement

Preuve (en classe) Théorème 2 : L’algorithme de Prim fonctionne correctement

Preuve (en classe)

ANALYSE DES ALGORITHMES

Kruskal - )log( aaθ pour trier les arêtes = )log( naθ

- )(nθ afin d’initialiser les n ensembles disjoints

- )),2(2( naaαθ pour les find et merge (voir section 5.9)

- Au pire, )(aO pour les autres opérations.

Ainsi, comme )(log)),2(( nOnaO ⊂α , on en déduit que :

)log()( nanK θ= .

Prim

Il suffit de remarquer que la boucle principale est exécutée n-1 fois et que chaque tour s’exécute en )(nθ pour en déduire que :

)()( 2nnP θ= .

CHOIX DE L’ALGORITHME

Nous avons obtenu les résultats suivants :

)log()( nanK θ= et

)()( 2nnP θ= Ainsi, il faut regarder l’effet de a sur le temps d’exécution. Comme nous savons que

2)1(1 −≤≤− nnan , on en déduit facilement que si

a) 2

)1( −→ nna alors )log()( 2 nnnK θ→ ;

b) 1−→ na alors )log()( nnnK θ→ . La conclusion est alors la suivante : « Si le graphe initial est dense, nous optons pour Prim alors que si le graphe initial est creux, nous optons pour Kruskal.»

Lemme de l’augmentation d’un ensemble prometteur

Soit ANG ,= un graphe connexe non orienté, avec un coût associé à chaque arête. Soit B ⊂ N un sous-ensemble strict des sommets de G et soit T ⊆ A un ensemble prometteur d’arêtes tel qu’aucune arête de T ne quitte B. Soit v une arête de coût minimal parmi celles qui quittent B. Alors T ∪ v est prometteur. Preuve : Soit U un MST de G tel que T ⊆⊆⊆⊆ U.

(un tel U existe puisque T est prometteur par hypothèse)

Premièrement, si v ∈∈∈∈ U alors il n’y a rien à prouver. (car T ∪ v ⊆ U est alors trivialement prometteur !)

Deuxièmement, si v ∉∉∉∉ U alors l’ajout de v à U crée un cycle

(car U est un MST)

Comme v quitte B, au moins une autre arête, disons u, quitte B (sinon, le cycle ne pourrait être fermé)

Si on enlève u, on obtient un nouvel arbre de recouvrement V de G

(élimination du cycle crée par v )

Comme w(v) ≤≤≤≤ w(u) alors w(V) ≤≤≤≤ w(U) (v est l’arête de coût minimal qui quitte B)

Ainsi, V contient v et est aussi un MST de G

(Puisque U est MST par hypothèse)

Finalement, T ⊆⊆⊆⊆ V car l’arête u ne pouvait pas appartenir à T. (car u quitte B et ainsi T demeure prometteur)

D’où le résultat.

PROBLÈME Nous voulons rendre la monnaie. De façon plus précise : «Rendre N cents en utilisant n types de pièces de monnaie de manière à minimiser le nombre de pièces». Approche vorace ? Pourquoi ?

- Propriété de sous-structure optimale ? oui ! - Propriété du choix vorace ? Pas toujours ! - Les candidats sont un ensemble de pièces - Un test de solution ( bon montant ?) - Test de réalisabilité ( somme ≤ montant ) - Fonction de sélection (pièce de plus haute valeur) - Fonction objective (# de pièces utilisées)

Si nous avons un nombre «illimité» de pièces de chacune des valeurs et que la propriété du choix vorace est vérifiée, alors (par exemple): Fonction Make-Change(N) : set of coins Const C = 100,25,10,5,1 S ← ∅ somme ← 0 While somme ≠ N do x ←plus grand élément de C t.q. somme + x ≤ N (*) Si une telle pièce n’existe pas Alors Return NO SOLUTION S ← S ∪ une pièce de valeur x (**) somme ← somme + x Return S ANALYSE : Dans ce cas, l’analyse est directe. Avec (**) comme instruction baromètre et en remarquant que (*) prend un temps dans θ(1) (pourquoi ?) on obtient facilement que dans le pire des cas notre algorithme prend un temps dans θθθθ(N). Malheureusement, la propriété du choix vorace n’étant pas toujours satisfaite, deux situations peuvent alors se présenter :

• Pas de solution; • solution pas optimale.

Exemple 1 : C = 1,4,6 et N = 8 L’algorithme vorace retourne S = 6,1,1 alors que la solution optimale est S = 4,4 Exemple 2 : C = 3,4,6 et N = 7 L’algorithme vorace retourne NO SOLUTION alors que S = 3,4 est une solution optimale ! Que faire ? Programmation dynamique ! Pour le moment, afin de simplifier, remarquons que si les pièces de valeur égale à $0.01 sont en nombre illimité, on peut toujours obtenir une solution. Sinon, pour certain N il n’y a effectivement aucune solution (donnez un exemple).

(Algorithme formel à la page 264)


es 2001C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

7

2 LA S

ÉR

IE M

ON

DIA

LE

Algorithm

e basé sur la programm

ation dynamique

(voir algorithme form

el dans le livre, p. 262)

Significations de k et s

•k = i + j (com

me pour la page 5)

•s est le num

éro de la diagonale en cours de traitement

(variable de contrôle de la boucle la plus externe).

s

k0

12

34

. . .n

0123

0

1

0

1

0

pp

p(2-p)

1

...

n0

P(n,n)

...

1. . .

1

p

Calcul de l’efficacité

Tem

ps: Avec cet algorithm

e, le temps de calcul est dans

Θ(n

2), c’est-à-dire le temps pris pour rem

plir le tableau n × n.

Espace m

émoire: Il n’est pas nécessaire d’utiliser un tableau:

un vecteur de longueur n suffit (diagonales successives dutableau carré n × n ). D

onc espace dans Θ(n).

8C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

©2001 R

. Lelouche

3 RE

ND

RE

LA M

ON

NA

IE(livre section 8.2, p. 263-265)


e

Déjà vu lors de l’étude des algorithm

es voraces.


arche pas pour certains systèmes

de dénominations de pièces.

Exem

ple: système com

prenant des pièces de 1, 4 et 6 ¢.R

endre 8¢ demanderait 3 pièces par l’algo vorace (6+1+1)

au lieu de 2 (4+4).


mation dynam

ique

Soit à rendre N

cents en utilisant n types de pièces. Pour

cela, on remplit un tableau N

bPièces de n lignes (une par

catégorie de pièces) et N colonnes (la som

me à rendre).

NbP

ièces [i, j] contient le nombre m

inimal de pièces à utiliser

pour rendre j ¢ en utilisant seulement des pièces des

catégories 1 à i. Il s’agit donc de calculer NbP

ièces [n, N].


NbP

ièces [i, j] = Min (N

bPièces [i–1, j], N

bPièces [i, j–d

i ] + 1

où di est la dénom

ination des pièces de la catégorie i.

Pour rendre 8 cents avec les pièces ci-dessus, on est conduit

ainsi à remplir le tableau suivant indiquant , N

bPièces [i, j],

le nombre m

inimum

de pièces à utiliser pour rendre la somm

e j en utilisantuniquem

ent les pièces de dénomination 1 à i:

Som

me:

01

23

45

67

8

d1 = 1

01

23

45

67

8d

2 = 40

12

31

23

42

d3 = 6

01

23

12

12

2


es 2001C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

9

3 RE

ND

RE

LA M

ON

NA

IE

Algorithm

e formel: voir livre

Exercices

Que se passe-t-il si certaines pièces sont en nom

bre limité

(problème 8.9)?

Le tableau ci-dessus donne seulement le nom

bre optimum

de pièces. Que faut-il faire pour connaître en outre les pièces

à rendre?

Analyse

Pour connaître seulem

ent le nombre de pièces

Il faut remplir un tableau n × (N

+1), chaque élément prenant

un temps unitaire. D

onc

Te

mp

s da

ns Θ

( nN

)

Pour connaître la valeur des pièces à rendre

Il faut en outre remonter dans ce tableau :

-chaque ligne pour passer à la dénom

ination suivante;-

NbP

ièces [n, N] fois vers la gauche pour rendre une pièce.

D’où:

Te

mp

s da

ns Θ

( n +

Nb

Piè

ces [n

, N])

10C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

©2001 R

. Lelouche

4 PR

OB

LÈM

E D

U S

AC

À D

OS

(livre section 8.4, p. 266-268)


e

Mêm

e énoncé que pour l’algorithme vorace, m

ais on n’a plusle droit de fractionner les objets: on prend tout ou rien.

Supposons qu’il y a n objets. L’objet i a un poids w

i > 0 et unevaleur v

i > 0; xi = 1 s’il est pris et x

i = 0 s’il n’est pas pris. Lacapacité du sac est W

. Il s’agit de (pourquoi?)

Maxim

iser ∑i=1 n x

i vi su

jet

à

∑i=1 n x

i wi ≤ W


arche plus. Exem

ple:

W = 10; n = 3; w

1 = 6, v1 = 8; w

2 = w3 = 5, v

2 = v3 = 5.


mation dynam

ique

On rem

plit un tableau Valeur de n lignes (une par objet) et

W+1 colonnes (une par unité de poids du sac). V

aleur [i, j]contient la valeur m

aximum

transportable pour une capacité jen utilisant seulem

ent les objets des catégories 1 à i. Il s’agitdonc de calculer V

aleur [n, W].


Valeur [i, j] = M

ax (Valeur [i–1, j], V

aleur [i–1, j–wi ] + v

i

Algorithm

e formel: problèm

e 8.11

Une fois notre tableau construit, pouvons nous y «lire» facilement la solution ? (quelles pièces remettre ?) Oui ! Supposons que nous voulons payer un montant j avec des pièces 1,2,….i de valeur di. Le nombre de pièces est donné par C[ i, j ]. Si C[ i, j ] = C[ i-1, j ] alors aucune pièce de valeur di n’est nécessaire et nous allons alors à C[ i-1, j ]. Après, si C[ i, j ] = 1 + C[ i,j-di] alors on retourne une pièce i de valeur di et nous nous déplaçons à C[i,j-di]. Par la suite, si C[ i-1, j ] et 1 + C[ i, j-di ] sont égaux à C[ i, j ], un choix arbitraire est effectué. On poursuit alors jusqu’à C[ 0, 0 ].

PROBLÈME : Sac à dos (sac alpin) Il existe plusieurs variantes de ce problème. Pour le moment, regardons la forme la plus simple. Nous disposons de n objets et d’un sac à dos. Chaque objet i = 1…n possède un poids wi>0 et une valeur vi>0. Notre but est de remplir notre sac à dos de sorte à maximiser la valeur totale de notre charge tout en respectant une contrainte W de poids maximal. Notre «version simplifiée» nous permet de fractionner les objets. Ainsi, une proportion xi∈ [0,1] peut être transportée. On obtient alors (modélisation mathématique) :

Maximiser ∑=

n

iiivx

1

où ∑=

≤n

iii Wwx

1

.

Comme il est facile d’identifier les constituants de l’approche vorace (et ses principes), c’est cette approche que nous allons implanter. Le point délicat consiste à déterminer la «bonne» fonction de sélection. Dans notre version du problème, il est évident qu’une solution optimale doit satisfaire :

∑=

=n

iii Wwx

1

.

(Algorithme formel page 203)

Ainsi, pour notre fonction de sélection, trois possibilités s’offrent à nous :

1) max vi 2) min wi

3) max i

i

wv

Afin d’orienter notre choix, regardons un exemple avec chacun de nos choix. Exemple : W = 100 et n = 5.

w 10 20 30 40 50 v 20 30 66 40 60

v/w 2.0 1.5 2.2 1.0 1.2

Select x1 x2 x3 x4 x5 Valeur Max vi 0 0 1 0.5 1 146 Min wi 1 1 1 1 0 156

max i

i

wv

1 1 1 0 0.8 164

Cet exemple nous permet seulement d’espérer que max i

i

wv

puisse constituer une

fonction de sélection valide pour l’approche vorace. Nous allons le prouver !

Théorème :

«Si les objets sont sélectionnés en ordre décroissant de i

i

wv , alors

l’algorithme vorace Knapsack produit une solution optimale.» Preuve : Supposons (sans perte de généralité) que les objets sont classés de sorte que :

n

n

wv

wv

wv

≥≥≥ ...2

2

1

1 .

Soit ),...,,( 21 nxxxX = une solution retournée par l’algorithme vorace. Si tous les 1=ix alors la solution est optimale. Sinon, soit j le plus petit entier tel que 1<jx . En regardant l’algorithme on déduit facilement que :

- 1=ix pour i < j - 0=ix pour i > j

et que ∑=

=n

iii Wwx

1

.

Soit ∑=

=n

iiivxXV

1)( et soit ),...,( 1 nyyY = une solution réalisable.

Comme Y est réalisable, nous devons avoir ∑=

≤n

iii Wwy

1

et donc que

∑ ∑∑= ==

≥−=−n

i

n

iiii

n

iiiii wyxwywx

1 110)( .

Soit ∑=

=n

iiivyYV

1)( . Ainsi, nous obtenons que :

∑ ∑= =

−=−=−n

i

n

i i

iiiiiii w

vwyxvyxYVXV

1 1

)()()()(

et finalement que

∑ ∑= =

≥−≥−=−n

i

n

iiii

j

j

i

iiii wyx

wv

wvwyxYVXV

1 10)()()()(

d’où le résultat !

L’analyse est encore une fois directe.

- O(n logn) pour trier - O(n) pour la boucle

Ainsi, le temps d’exécution est O(n logn) QUESTION : Qu’arrive-t-il si nous imposons maintenant xi ∈ 0,1 ? L’algorithme vorace ne fonctionne plus ! (construire un exemple) Que faire ? Programmation dynamique !


es 2001C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

9

3 RE

ND

RE

LA M

ON

NA

IE

Algorithm

e formel: voir livre

Exercices

Que se passe-t-il si certaines pièces sont en nom

bre limité

(problème 8.9)?

Le tableau ci-dessus donne seulement le nom

bre optimum

de pièces. Que faut-il faire pour connaître en outre les pièces

à rendre?

Analyse


ent le nombre de pièces

Il faut remplir un tableau n × (N

+1), chaque élément prenant

un temps unitaire. D

onc

Te

mp

s da

ns Θ

( nN

)

Pour connaître la valeur des pièces à rendre

Il faut en outre remonter dans ce tableau :

-chaque ligne pour passer à la dénom

ination suivante;-

NbP

ièces [n, N] fois vers la gauche pour rendre une pièce.

D’où:

Te

mp

s da

ns Θ

( n +

Nb

Piè

ces [n

, N])

10C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

©2001 R

. Lelouche

4 PR

OB

LÈM

E D

U S

AC

À D

OS

(livre section 8.4, p. 266-268)


e

Mêm

e énoncé que pour l’algorithme vorace, m

ais on n’a plusle droit de fractionner les objets: on prend tout ou rien.

Supposons qu’il y a n objets. L’objet i a un poids w

i > 0 et unevaleur v

i > 0; xi = 1 s’il est pris et x

i = 0 s’il n’est pas pris. Lacapacité du sac est W

. Il s’agit de (pourquoi?)

Maxim

iser ∑i=1 n x

i vi su

jet

à

∑i=1 n x

i wi ≤ W


arche plus. Exem

ple:

W = 10; n = 3; w

1 = 6, v1 = 8; w

2 = w3 = 5, v

2 = v3 = 5.


mation dynam

ique

On rem

plit un tableau Valeur de n lignes (une par objet) et

W+1 colonnes (une par unité de poids du sac). V

aleur [i, j]contient la valeur m

aximum

transportable pour une capacité jen utilisant seulem

ent les objets des catégories 1 à i. Il s’agitdonc de calculer V

aleur [n, W].


Valeur [i, j] = M

ax (Valeur [i–1, j], V

aleur [i–1, j–wi ] + v

i

Algorithm

e formel: problèm

e 8.11


es 2001C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

11

4 PR

OB

LÈM

E D

U S

AC

À D

OS

Exem

ple

W = 11, n = 5, w

i = 1, 2, 5, 6, 7; vi = 1, 6, 18, 22, 28.

On est conduit au tableau suivant:

Poids lim

ite:0

12

34

56

78

910

11

w1 =

1, v1 =

10

11

11

11

11

11

1w

2 = 2, v

2 = 6

01

67

77

77

77

77

w3 = 5, v

3 = 180

16

77

1819

2425

2525

25w

4 = 6, v4 = 22

01

67

718

2224

2829

2940

w5 = 7, v

5 = 280

16

77

1822

2829

3435

40

Le tableau ci-dessus donne seulement la valeur du

chargement optim

um. Q

ue faut-il faire pour connaître enoutre les objets à transporter?

Analyse

Analogue à l’algorithm

e pour rendre la monnaie.


ent la valeur du chargement optim

al

Te

mp

s da

ns Θ

(nW

)

Pour connaître la com

position du chargement optim

al

Te

mp

s sup

plé

me

nta

ire d

an

s O(n

+ W

)

Rem

arqueLe term

e W est très pessim

iste, et peut être remplacé par le nom

bre d’objetsretenus (pourquoi?), qui est inférieur à W

, et mêm

e inférieur ou égal à n.

On obtient alors un tem

ps supplémentaire dans O

(n).

12C

hapitre 8: PR

OG

RA

MM

AT

ION

DY

NA

MIQ

UE

©2001 R

. Lelouche

5

MU

LTIP

LICA

TIO

N

CH

AÎN

ÉE

DE

M

AT

RIC

ES

Position du problèm

e

Il s’agit d’effectuer le produit matriciel

M = M

1 M2 . . . M

n .P

uisque la multiplication m

atricielle est associative, l’ordredans lequel les produits m

atriciels sont effectués estindifférent quant au résultat, m

ais peut influer sur le temps

total nécessaire.

Pourquoi se poser des questions

sur l’ordre des produits?

1)S

oient A ∈

M p×q et B

∈ M

q×r (M p×q est l’ensem

ble desm

atrices de p lignes et q colonnes). Alors,

A×B

nécessite pqr multiplications de nom

bres scalaires.

2)S

oit M = M

1 M2 ... M

n , avec Mi ∈ M

pi × q

i ∀ i (p

i = qi–1 ).

Supposons de plus que p

i ≤ qi pour tout i.

(... ((M1 M

2 ) M3 ) ... M

n–1 )Mn (de droite à gauche)

nécessite un nombre de m

ultiplications dansO (p

1 ∑

i=1,...,n–1

pi q

i )tandis que

M1 (M

2 (... (Mn–2 (M

n–1 Mn ))...)) (de gauche à droite)

nécessite un nombre de m

ultiplications dansO (q

n ∑

i=1,...,n–1

pi q

i )

Nette différence !

Documents

DIVISER POUR RÉGNER - Université Lavalbherer/AAE04/cours7hans.pdfAnalyse d’Algorithmes 2001 Ch. 7 - DIVISER POUR RÉGNER 5 2. DÉTERMINATION DU SEUIL Détermination théorique