View
10
Download
0
Category
Preview:
Citation preview
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
Recommended