Chapitre 3 :

Algorithmes Diviser pour Regner

Prof. Abdelmajid DarghamFaculte des Sciences, Oujda

Master Specialise Ingenierie Informatique

Universite Mohamed Premier

Septembre, 2012

Sommaire du chapitre 3

Principe de la technique diviser pour regner

Exemples classiques

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Sommaire du chapitre 3

Principe de la technique diviser pour regner

Exemples classiques

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Sommaire du chapitre 3

Principe de la technique diviser pour regner

Exemples classiques

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Definition 1.1

Un algorithme de type diviser pour regner est une procedurerecursive qui resout un probleme donne selon le schemasuivant :

Diviser : le probleme est decompose en plusieurssous-prolemes dont la resolution est identique a celle duprobleme initial.

Regner : les sous-prolemes sont resolus de faconrecursive. Cependant, un sous-probleme peut etre resoludirectement si la taille de son entree est petite.

Combiner : les solustions des sous-prolemes sontcombinees pour former la solution du probleme initial.

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Definition 1.1

Un algorithme de type diviser pour regner est une procedurerecursive qui resout un probleme donne selon le schemasuivant :

Diviser : le probleme est decompose en plusieurssous-prolemes dont la resolution est identique a celle duprobleme initial.

Regner : les sous-prolemes sont resolus de faconrecursive. Cependant, un sous-probleme peut etre resoludirectement si la taille de son entree est petite.

Combiner : les solustions des sous-prolemes sontcombinees pour former la solution du probleme initial.

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Definition 1.1

Un algorithme de type diviser pour regner est une procedurerecursive qui resout un probleme donne selon le schemasuivant :

Diviser : le probleme est decompose en plusieurssous-prolemes dont la resolution est identique a celle duprobleme initial.

Regner : les sous-prolemes sont resolus de faconrecursive. Cependant, un sous-probleme peut etre resoludirectement si la taille de son entree est petite.

Combiner : les solustions des sous-prolemes sontcombinees pour former la solution du probleme initial.

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Definition 1.1

Un algorithme de type diviser pour regner est une procedurerecursive qui resout un probleme donne selon le schemasuivant :

Diviser : le probleme est decompose en plusieurssous-prolemes dont la resolution est identique a celle duprobleme initial.

Regner : les sous-prolemes sont resolus de faconrecursive. Cependant, un sous-probleme peut etre resoludirectement si la taille de son entree est petite.

Combiner : les solustions des sous-prolemes sontcombinees pour former la solution du probleme initial.

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Schema general d’un algorithme diviser pour regner

Schema general 1.2

Fonction Diviser Regner(P : Probleme) : SolutionVariables S : Solution;

DebutSi (‖P‖ est petite) Alors S := CasBase(P)

Sinon(P1, P2, ..., Pk) := Diviser(P);Pour i := 1 a k Faire Si := Regner(Pi); FinPourS := Combiner(S1, S2, ..., Sk);

FinSiRetourner S;

Fin

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Schema general d’un algorithme diviser pour regner

Schema general 1.2

Fonction Diviser Regner(P : Probleme) : Solution

Variables S : Solution;Debut

Si (‖P‖ est petite) Alors S := CasBase(P)Sinon

(P1, P2, ..., Pk) := Diviser(P);Pour i := 1 a k Faire Si := Regner(Pi); FinPourS := Combiner(S1, S2, ..., Sk);

FinSiRetourner S;

Fin

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Schema general d’un algorithme diviser pour regner

Schema general 1.2

Fonction Diviser Regner(P : Probleme) : SolutionVariables S : Solution;

DebutSi (‖P‖ est petite) Alors S := CasBase(P)

Sinon(P1, P2, ..., Pk) := Diviser(P);Pour i := 1 a k Faire Si := Regner(Pi); FinPourS := Combiner(S1, S2, ..., Sk);

FinSiRetourner S;

Fin

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Schema general d’un algorithme diviser pour regner

Schema general 1.2

Fonction Diviser Regner(P : Probleme) : SolutionVariables S : Solution;

Debut

Si (‖P‖ est petite) Alors S := CasBase(P)Sinon

(P1, P2, ..., Pk) := Diviser(P);Pour i := 1 a k Faire Si := Regner(Pi); FinPourS := Combiner(S1, S2, ..., Sk);

FinSiRetourner S;

Fin

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Schema general d’un algorithme diviser pour regner

Schema general 1.2

Fonction Diviser Regner(P : Probleme) : SolutionVariables S : Solution;

DebutSi (‖P‖ est petite) Alors S := CasBase(P)

Sinon(P1, P2, ..., Pk) := Diviser(P);Pour i := 1 a k Faire Si := Regner(Pi); FinPourS := Combiner(S1, S2, ..., Sk);

FinSiRetourner S;

Fin

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Schema general d’un algorithme diviser pour regner

Schema general 1.2

Fonction Diviser Regner(P : Probleme) : SolutionVariables S : Solution;

DebutSi (‖P‖ est petite) Alors S := CasBase(P)

Sinon

(P1, P2, ..., Pk) := Diviser(P);Pour i := 1 a k Faire Si := Regner(Pi); FinPourS := Combiner(S1, S2, ..., Sk);

FinSiRetourner S;

Fin

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Schema general d’un algorithme diviser pour regner

Schema general 1.2

Fonction Diviser Regner(P : Probleme) : SolutionVariables S : Solution;

DebutSi (‖P‖ est petite) Alors S := CasBase(P)

Sinon(P1, P2, ..., Pk) := Diviser(P);

Pour i := 1 a k Faire Si := Regner(Pi); FinPourS := Combiner(S1, S2, ..., Sk);

FinSiRetourner S;

Fin

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Schema general d’un algorithme diviser pour regner

Schema general 1.2

Fonction Diviser Regner(P : Probleme) : SolutionVariables S : Solution;

DebutSi (‖P‖ est petite) Alors S := CasBase(P)

Sinon(P1, P2, ..., Pk) := Diviser(P);Pour i := 1 a k Faire Si := Regner(Pi); FinPour

S := Combiner(S1, S2, ..., Sk);FinSiRetourner S;

Fin

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Schema general d’un algorithme diviser pour regner

Schema general 1.2

Fonction Diviser Regner(P : Probleme) : SolutionVariables S : Solution;

DebutSi (‖P‖ est petite) Alors S := CasBase(P)

Sinon(P1, P2, ..., Pk) := Diviser(P);Pour i := 1 a k Faire Si := Regner(Pi); FinPourS := Combiner(S1, S2, ..., Sk);

FinSiRetourner S;

Fin

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Principe de la technique diviser pour regner

Schema general d’un algorithme diviser pour regner

Schema general 1.2

Fonction Diviser Regner(P : Probleme) : SolutionVariables S : Solution;

DebutSi (‖P‖ est petite) Alors S := CasBase(P)

Sinon(P1, P2, ..., Pk) := Diviser(P);Pour i := 1 a k Faire Si := Regner(Pi); FinPourS := Combiner(S1, S2, ..., Sk);

FinSiRetourner S;

FinProf. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers

Soit a calculer le produit de deux entiers x et y ayantchacun n chiffres.

L’algorithme naıf effectue n2 multiplications simples(multiplication de 2 chiffres).

Posons : {x = a × 10

n2 + b

y = c × 10n2 + d

xy = ac × 10n + (ad + bc)× 10n2 + bd (1)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers

Soit a calculer le produit de deux entiers x et y ayantchacun n chiffres.

L’algorithme naıf effectue n2 multiplications simples(multiplication de 2 chiffres).

Posons : {x = a × 10

n2 + b

y = c × 10n2 + d

xy = ac × 10n + (ad + bc)× 10n2 + bd (1)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers

Soit a calculer le produit de deux entiers x et y ayantchacun n chiffres.

L’algorithme naıf effectue n2 multiplications simples(multiplication de 2 chiffres).

Posons : {x = a × 10

n2 + b

y = c × 10n2 + d

xy = ac × 10n + (ad + bc)× 10n2 + bd (1)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers

Soit a calculer le produit de deux entiers x et y ayantchacun n chiffres.

L’algorithme naıf effectue n2 multiplications simples(multiplication de 2 chiffres).

Posons : {x = a × 10

n2 + b

y = c × 10n2 + d

xy = ac × 10n + (ad + bc)× 10n2 + bd (1)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers

Soit a calculer le produit de deux entiers x et y ayantchacun n chiffres.

L’algorithme naıf effectue n2 multiplications simples(multiplication de 2 chiffres).

Posons : {x = a × 10

n2 + b

y = c × 10n2 + d

xy = ac × 10n + (ad + bc)× 10n2 + bd (1)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers

Un premier algorithme de type DR ( Diviser pour regner)base sur la formule (1).

Complexite :

T (n) =

{1 si n = 1

4T (n/2) si n ≥ 2

T (n) = Θ(n2).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers

Un premier algorithme de type DR ( Diviser pour regner)base sur la formule (1).

Complexite :

T (n) =

{1 si n = 1

4T (n/2) si n ≥ 2

T (n) = Θ(n2).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers

Un premier algorithme de type DR ( Diviser pour regner)base sur la formule (1).

Complexite :

T (n) =

{1 si n = 1

4T (n/2) si n ≥ 2

T (n) = Θ(n2).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers

Un premier algorithme de type DR ( Diviser pour regner)base sur la formule (1).

Complexite :

T (n) =

{1 si n = 1

4T (n/2) si n ≥ 2

T (n) = Θ(n2).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers : algorithme deKaratsuba

C’est un algorithme de type DR .

Idee : utiliser 3 multiplications au lieu de 4 dans laformule (1).

ad + bc = ac + bd − (a− b)(c − d) (Forumule de Gauss)

xy = p × 10n + (p + q − r)× 10n2 + q, avec :

Formule de Karatsuba

p := ac

q := bd

r := (a − b)(c − d)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers : algorithme deKaratsuba

C’est un algorithme de type DR .

Idee : utiliser 3 multiplications au lieu de 4 dans laformule (1).

ad + bc = ac + bd − (a− b)(c − d) (Forumule de Gauss)

xy = p × 10n + (p + q − r)× 10n2 + q, avec :

Formule de Karatsuba

p := ac

q := bd

r := (a − b)(c − d)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers : algorithme deKaratsuba

C’est un algorithme de type DR .

Idee : utiliser 3 multiplications au lieu de 4 dans laformule (1).

ad + bc = ac + bd − (a− b)(c − d) (Forumule de Gauss)

xy = p × 10n + (p + q − r)× 10n2 + q, avec :

Formule de Karatsuba

p := ac

q := bd

r := (a − b)(c − d)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers : algorithme deKaratsuba

C’est un algorithme de type DR .

Idee : utiliser 3 multiplications au lieu de 4 dans laformule (1).

ad + bc = ac + bd − (a− b)(c − d) (Forumule de Gauss)

xy = p × 10n + (p + q − r)× 10n2 + q, avec :

Formule de Karatsuba

p := ac

q := bd

r := (a − b)(c − d)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers : algorithme deKaratsuba

C’est un algorithme de type DR .

Idee : utiliser 3 multiplications au lieu de 4 dans laformule (1).

ad + bc = ac + bd − (a− b)(c − d) (Forumule de Gauss)

xy = p × 10n + (p + q − r)× 10n2 + q, avec :

Formule de Karatsuba

p := ac

q := bd

r := (a − b)(c − d)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers : algorithme deKaratsuba

C’est un algorithme de type DR .

Idee : utiliser 3 multiplications au lieu de 4 dans laformule (1).

ad + bc = ac + bd − (a− b)(c − d) (Forumule de Gauss)

xy = p × 10n + (p + q − r)× 10n2 + q, avec :

Formule de Karatsuba

p := ac

q := bd

r := (a − b)(c − d)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers : algorithme deKaratsuba

Complexite de l’algorithme de Karatsuba :

T (n) =

{1 si n = 1

3T (n2) si n ≥ 2

T (n) = Θ(nlog2 3) ' Θ(n1.58).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers : algorithme deKaratsuba

Complexite de l’algorithme de Karatsuba :

T (n) =

{1 si n = 1

3T (n2) si n ≥ 2

T (n) = Θ(nlog2 3) ' Θ(n1.58).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers : algorithme deKaratsuba

Complexite de l’algorithme de Karatsuba :

T (n) =

{1 si n = 1

3T (n2) si n ≥ 2

T (n) = Θ(nlog2 3) ' Θ(n1.58).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des grands entiers : algorithme deKaratsuba

Complexite de l’algorithme de Karatsuba :

T (n) =

{1 si n = 1

3T (n2) si n ≥ 2

T (n) = Θ(nlog2 3) ' Θ(n1.58).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

Soit a calculer la matrice C , produit des deux matricescarrees A et B de dimension n.

Le schema de calcul de l’algorithme naıf est :

Cij :=∑n

k=1 AikBkj

L’algorithme naıf effectue :

n3 multiplications.n2(n − 1) = Θ(n3) additions.

Sa complexite est alors : Θ(n3).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

Soit a calculer la matrice C , produit des deux matricescarrees A et B de dimension n.

Le schema de calcul de l’algorithme naıf est :

Cij :=∑n

k=1 AikBkj

L’algorithme naıf effectue :

n3 multiplications.n2(n − 1) = Θ(n3) additions.

Sa complexite est alors : Θ(n3).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

Soit a calculer la matrice C , produit des deux matricescarrees A et B de dimension n.

Le schema de calcul de l’algorithme naıf est :

Cij :=∑n

k=1 AikBkj

L’algorithme naıf effectue :

n3 multiplications.n2(n − 1) = Θ(n3) additions.

Sa complexite est alors : Θ(n3).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

Soit a calculer la matrice C , produit des deux matricescarrees A et B de dimension n.

Le schema de calcul de l’algorithme naıf est :

Cij :=∑n

k=1 AikBkj

L’algorithme naıf effectue :

n3 multiplications.n2(n − 1) = Θ(n3) additions.

Sa complexite est alors : Θ(n3).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

Soit a calculer la matrice C , produit des deux matricescarrees A et B de dimension n.

Le schema de calcul de l’algorithme naıf est :

Cij :=∑n

k=1 AikBkj

L’algorithme naıf effectue :

n3 multiplications.n2(n − 1) = Θ(n3) additions.

Sa complexite est alors : Θ(n3).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

Soit a calculer la matrice C , produit des deux matricescarrees A et B de dimension n.

Le schema de calcul de l’algorithme naıf est :

Cij :=∑n

k=1 AikBkj

L’algorithme naıf effectue :

n3 multiplications.

n2(n − 1) = Θ(n3) additions.

Sa complexite est alors : Θ(n3).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

Soit a calculer la matrice C , produit des deux matricescarrees A et B de dimension n.

Le schema de calcul de l’algorithme naıf est :

Cij :=∑n

k=1 AikBkj

L’algorithme naıf effectue :

n3 multiplications.n2(n − 1) = Θ(n3) additions.

Sa complexite est alors : Θ(n3).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

Soit a calculer la matrice C , produit des deux matricescarrees A et B de dimension n.

Le schema de calcul de l’algorithme naıf est :

Cij :=∑n

k=1 AikBkj

L’algorithme naıf effectue :

n3 multiplications.n2(n − 1) = Θ(n3) additions.

Sa complexite est alors : Θ(n3).

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

On decompose chaque matrice de dimension n en 4sous-matrices de dimension n

2:

A =

(A11 A12

A21 A22

)B =

(B11 B12

B21 B22

)C =

(C11 C12

C21 C22

)

C11 = A11B11 + A12B21

C12 = A11B12 + A12B22

C21 = A21B11 + A22B21

C22 = A21B12 + A22B22

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

On decompose chaque matrice de dimension n en 4sous-matrices de dimension n

2:

A =

(A11 A12

A21 A22

)B =

(B11 B12

B21 B22

)C =

(C11 C12

C21 C22

)

C11 = A11B11 + A12B21

C12 = A11B12 + A12B22

C21 = A21B11 + A22B21

C22 = A21B12 + A22B22

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

On decompose chaque matrice de dimension n en 4sous-matrices de dimension n

2:

A =

(A11 A12

A21 A22

)B =

(B11 B12

B21 B22

)C =

(C11 C12

C21 C22

)

C11 = A11B11 + A12B21

C12 = A11B12 + A12B22

C21 = A21B11 + A22B21

C22 = A21B12 + A22B22

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

On decompose chaque matrice de dimension n en 4sous-matrices de dimension n

2:

A =

(A11 A12

A21 A22

)B =

(B11 B12

B21 B22

)C =

(C11 C12

C21 C22

)

C11 = A11B11 + A12B21

C12 = A11B12 + A12B22

C21 = A21B11 + A22B21

C22 = A21B12 + A22B22

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

On decompose chaque matrice de dimension n en 4sous-matrices de dimension n

2:

A =

(A11 A12

A21 A22

)B =

(B11 B12

B21 B22

)C =

(C11 C12

C21 C22

)

C11 = A11B11 + A12B21

C12 = A11B12 + A12B22

C21 = A21B11 + A22B21

C22 = A21B12 + A22B22

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

On decompose chaque matrice de dimension n en 4sous-matrices de dimension n

2:

A =

(A11 A12

A21 A22

)B =

(B11 B12

B21 B22

)C =

(C11 C12

C21 C22

)

C11 = A11B11 + A12B21

C12 = A11B12 + A12B22

C21 = A21B11 + A22B21

C22 = A21B12 + A22B22

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

On decompose chaque matrice de dimension n en 4sous-matrices de dimension n

2:

A =

(A11 A12

A21 A22

)B =

(B11 B12

B21 B22

)C =

(C11 C12

C21 C22

)

C11 = A11B11 + A12B21

C12 = A11B12 + A12B22

C21 = A21B11 + A22B21

C22 = A21B12 + A22B22

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

Le schema de calcul precedent donne un algorithme DRdont la complexite est :

T (n) =

{1 si n = 1

8T (n2) + n2 si n ≥ 2

Par consequent, T (n) = Θ(n3)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

Le schema de calcul precedent donne un algorithme DRdont la complexite est :

T (n) =

{1 si n = 1

8T (n2) + n2 si n ≥ 2

Par consequent, T (n) = Θ(n3)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

Le schema de calcul precedent donne un algorithme DRdont la complexite est :

T (n) =

{1 si n = 1

8T (n2) + n2 si n ≥ 2

Par consequent, T (n) = Θ(n3)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices

Le schema de calcul precedent donne un algorithme DRdont la complexite est :

T (n) =

{1 si n = 1

8T (n2) + n2 si n ≥ 2

Par consequent, T (n) = Θ(n3)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

C’est un algorithme de type DR .

Idee : utiliser 7 multiplications au lieu de 8.

Voici les etapes de calcul de cet algorithme :

1 M1 := (A11 + A22)(B11 + B22);2 M2 := (A21 + A22)B11;3 M3 := A11(B12 − B22);4 M4 := A22(B21 − B11);5 M5 := (A11 + A12)B22;6 M6 := (A21 − A11)(B11 + B12);7 M7 := (A12 − A22)(B21 + B22);

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

C’est un algorithme de type DR .

Idee : utiliser 7 multiplications au lieu de 8.

Voici les etapes de calcul de cet algorithme :

1 M1 := (A11 + A22)(B11 + B22);2 M2 := (A21 + A22)B11;3 M3 := A11(B12 − B22);4 M4 := A22(B21 − B11);5 M5 := (A11 + A12)B22;6 M6 := (A21 − A11)(B11 + B12);7 M7 := (A12 − A22)(B21 + B22);

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

C’est un algorithme de type DR .

Idee : utiliser 7 multiplications au lieu de 8.

Voici les etapes de calcul de cet algorithme :

1 M1 := (A11 + A22)(B11 + B22);2 M2 := (A21 + A22)B11;3 M3 := A11(B12 − B22);4 M4 := A22(B21 − B11);5 M5 := (A11 + A12)B22;6 M6 := (A21 − A11)(B11 + B12);7 M7 := (A12 − A22)(B21 + B22);

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

C’est un algorithme de type DR .

Idee : utiliser 7 multiplications au lieu de 8.

Voici les etapes de calcul de cet algorithme :

1 M1 := (A11 + A22)(B11 + B22);2 M2 := (A21 + A22)B11;3 M3 := A11(B12 − B22);4 M4 := A22(B21 − B11);5 M5 := (A11 + A12)B22;6 M6 := (A21 − A11)(B11 + B12);7 M7 := (A12 − A22)(B21 + B22);

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

C’est un algorithme de type DR .

Idee : utiliser 7 multiplications au lieu de 8.

Voici les etapes de calcul de cet algorithme :

1 M1 := (A11 + A22)(B11 + B22);

2 M2 := (A21 + A22)B11;3 M3 := A11(B12 − B22);4 M4 := A22(B21 − B11);5 M5 := (A11 + A12)B22;6 M6 := (A21 − A11)(B11 + B12);7 M7 := (A12 − A22)(B21 + B22);

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

C’est un algorithme de type DR .

Idee : utiliser 7 multiplications au lieu de 8.

Voici les etapes de calcul de cet algorithme :

1 M1 := (A11 + A22)(B11 + B22);2 M2 := (A21 + A22)B11;

3 M3 := A11(B12 − B22);4 M4 := A22(B21 − B11);5 M5 := (A11 + A12)B22;6 M6 := (A21 − A11)(B11 + B12);7 M7 := (A12 − A22)(B21 + B22);

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

C’est un algorithme de type DR .

Idee : utiliser 7 multiplications au lieu de 8.

Voici les etapes de calcul de cet algorithme :

1 M1 := (A11 + A22)(B11 + B22);2 M2 := (A21 + A22)B11;3 M3 := A11(B12 − B22);

4 M4 := A22(B21 − B11);5 M5 := (A11 + A12)B22;6 M6 := (A21 − A11)(B11 + B12);7 M7 := (A12 − A22)(B21 + B22);

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

C’est un algorithme de type DR .

Idee : utiliser 7 multiplications au lieu de 8.

Voici les etapes de calcul de cet algorithme :

1 M1 := (A11 + A22)(B11 + B22);2 M2 := (A21 + A22)B11;3 M3 := A11(B12 − B22);4 M4 := A22(B21 − B11);

5 M5 := (A11 + A12)B22;6 M6 := (A21 − A11)(B11 + B12);7 M7 := (A12 − A22)(B21 + B22);

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

C’est un algorithme de type DR .

Idee : utiliser 7 multiplications au lieu de 8.

Voici les etapes de calcul de cet algorithme :

1 M1 := (A11 + A22)(B11 + B22);2 M2 := (A21 + A22)B11;3 M3 := A11(B12 − B22);4 M4 := A22(B21 − B11);5 M5 := (A11 + A12)B22;

6 M6 := (A21 − A11)(B11 + B12);7 M7 := (A12 − A22)(B21 + B22);

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

C’est un algorithme de type DR .

Idee : utiliser 7 multiplications au lieu de 8.

Voici les etapes de calcul de cet algorithme :

1 M1 := (A11 + A22)(B11 + B22);2 M2 := (A21 + A22)B11;3 M3 := A11(B12 − B22);4 M4 := A22(B21 − B11);5 M5 := (A11 + A12)B22;6 M6 := (A21 − A11)(B11 + B12);

7 M7 := (A12 − A22)(B21 + B22);

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

C’est un algorithme de type DR .

Idee : utiliser 7 multiplications au lieu de 8.

Voici les etapes de calcul de cet algorithme :

1 M1 := (A11 + A22)(B11 + B22);2 M2 := (A21 + A22)B11;3 M3 := A11(B12 − B22);4 M4 := A22(B21 − B11);5 M5 := (A11 + A12)B22;6 M6 := (A21 − A11)(B11 + B12);7 M7 := (A12 − A22)(B21 + B22);

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

La matrice C est calculee ainsi :

1 C11 := M1 + M4 −M5 + M7;2 C12 := M3 + M5;3 C21 := M2 + M4;4 C22 := M1 −M2 + M3 + M6;

La complexite de l’algorithme est :

T (n) =

{1 si n = 1

7T (n2) + 2n2 si n ≥ 2

Par suite : T (n) = Θ(nlog2 7) ' Θ(n2.807)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

La matrice C est calculee ainsi :

1 C11 := M1 + M4 −M5 + M7;2 C12 := M3 + M5;3 C21 := M2 + M4;4 C22 := M1 −M2 + M3 + M6;

La complexite de l’algorithme est :

T (n) =

{1 si n = 1

7T (n2) + 2n2 si n ≥ 2

Par suite : T (n) = Θ(nlog2 7) ' Θ(n2.807)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

La matrice C est calculee ainsi :

1 C11 := M1 + M4 −M5 + M7;

2 C12 := M3 + M5;3 C21 := M2 + M4;4 C22 := M1 −M2 + M3 + M6;

La complexite de l’algorithme est :

T (n) =

{1 si n = 1

7T (n2) + 2n2 si n ≥ 2

Par suite : T (n) = Θ(nlog2 7) ' Θ(n2.807)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

La matrice C est calculee ainsi :

1 C11 := M1 + M4 −M5 + M7;2 C12 := M3 + M5;

3 C21 := M2 + M4;4 C22 := M1 −M2 + M3 + M6;

La complexite de l’algorithme est :

T (n) =

{1 si n = 1

7T (n2) + 2n2 si n ≥ 2

Par suite : T (n) = Θ(nlog2 7) ' Θ(n2.807)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

La matrice C est calculee ainsi :

1 C11 := M1 + M4 −M5 + M7;2 C12 := M3 + M5;3 C21 := M2 + M4;

4 C22 := M1 −M2 + M3 + M6;

La complexite de l’algorithme est :

T (n) =

{1 si n = 1

7T (n2) + 2n2 si n ≥ 2

Par suite : T (n) = Θ(nlog2 7) ' Θ(n2.807)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

La matrice C est calculee ainsi :

1 C11 := M1 + M4 −M5 + M7;2 C12 := M3 + M5;3 C21 := M2 + M4;4 C22 := M1 −M2 + M3 + M6;

La complexite de l’algorithme est :

T (n) =

{1 si n = 1

7T (n2) + 2n2 si n ≥ 2

Par suite : T (n) = Θ(nlog2 7) ' Θ(n2.807)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

La matrice C est calculee ainsi :

1 C11 := M1 + M4 −M5 + M7;2 C12 := M3 + M5;3 C21 := M2 + M4;4 C22 := M1 −M2 + M3 + M6;

La complexite de l’algorithme est :

T (n) =

{1 si n = 1

7T (n2) + 2n2 si n ≥ 2

Par suite : T (n) = Θ(nlog2 7) ' Θ(n2.807)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner

Exemples classiques

Multiplication des matrices : algorithme de Strassen

La matrice C est calculee ainsi :

1 C11 := M1 + M4 −M5 + M7;2 C12 := M3 + M5;3 C21 := M2 + M4;4 C22 := M1 −M2 + M3 + M6;

La complexite de l’algorithme est :

T (n) =

{1 si n = 1

7T (n2) + 2n2 si n ≥ 2

Par suite : T (n) = Θ(nlog2 7) ' Θ(n2.807)

Prof. Abdelmajid Dargham Chapitre 3 : Algorithmes Diviser pour Regner