Diviser pour régner

Algorithme de Strassen

Calculons un produit de matrices :
t u = c d á g h
r s a b e f
LÕalgorithme classique calcule en Add(n) = n 2(n − 1) additions et M ult(n) = n3 multipli-cations. En effet, il y a n2 coefficients à calculer, chacun correspondant un produit scalaire de taille n, donc avec n multiplications, n − 1 additions, et une affectation. Peut-on faire mieux ?1 V. Strassen répond que oui : soient
p1 = a(g − h)
p2 = (a + b)h
p3 = (c + d)e
p4 = d(f − e)
p5 = (a + d)(e + h)
p6 = (b − d)(f + h)
p7 = (a − c)(e + g)
alors on peut écrire
r = p5 + p4 − p2 + p6
s = p1 + p2
t = p3 + p4
u = p5 + p1 − p3 − p7
Comptons maintenant les opérations :
Classique Strassen
M ult(2) = 8 M ult(2) = 7
Add(2) = 4 Add(2) = 18
On a gagné une multiplication, mais en perdant 14 additions ; donc, pour des matrices 2×2, cÕest un bilan négatif. Par contre, il est remarquable que lÕopération ne nécessite pas la commutativité de la multiplication. On peut donc lÕutiliser avec des matrices de taille n paire.
1Dans les temps anciens de l’informatique, il était surtout intéressant de diminuer le nombre de multiplications, quitte à augmenter le nombre d’additions. L’architecture pipelinée des processeurs actuels permet de réaliser, en moyenne, une addition ou une multiplication par temps de cycle.
Supposons donc n = 2m pair, et utilisons la méthode précédente une seule fois, en par-titionnant chaque matrice de départ en quatre sous-blocs de taille m × m. On e ff ectueram3 multiplications pour chaque pi, dÕo`u un total de M ult(n) = 7m3 = 7n3/8 multiplications. Pour les additions, il y a deux sources : les additions effectuées dans chaque produit pi, donc au nombre de 7m2(m − 1), et les additions pour former les 18 matrices auxiliaires, au nombre de 18m2. DÕo`u Add(n) = 7m3 + 11m2 = 7n3/8 + 11n2/4. Asymptotiquement, le terme dominant est en 7n3/8 pour M ult(n) comme pour Add(n), et la nouvelle méthode est gagnante pour n assez grand. La raison profonde est la suivante : une multiplication de deux matrices de taille n requiert O(n3) opérations, alors que leur addition nÕen demande que O (n2). Pour n grand, les additions sont ÒgratuitesÓ en face des multiplications. Ce qui nÕétait pas le cas pour les nombres réels.
LÕalgorithme de Strassen est lÕapplication récursive de la décomposition précédente. On consid`ere le cas o`u n est une puissance de 2, i.e. n = 2s. Si n nÕest pas une puissance de 2, on étend les matrices avec des 0 à la puissance de 2 supérieure : et on remplacera dans les formules qui suivent log n par log n .
Prenons donc n = 2s. On fonctionne de mani`ere récursive : on refait le möeme découpage pour chacun des produits de matrice pi. On sÕarröetera quand on arrive `a des matrices de taille 1, ou mieux, `a la taille pour laquelle la méthode est plus coöuteuse que la méthode classique (n ≈ 32).
Soient :
Ð M(n) = nombre de multiplications réalisées par lÕalgorithme de Strassen pour multiplier 2 matrices de taille n
Ð A(n) = nombre dÕadditions réalisées par lÕalgorithme de Strassen pour multiplier 2 ma-trices de taille n
On a : M(n) = 7 × M(n/2) =⇒ M(n) = 7s = 7log2(n) = nlog2(7) M(1) = 1
Comme précédemment, les additions viennent de 2 sources : les additions liées aux additions de matrices pour la construction des termes pi et les additions effectuées pour les multiplications de matrices (appels récursifs). On a donc :
A(n) = 7 × A(n/2) + 18 × (n/2)2 =⇒ A(n) = 6 × (nlog2(7) − n2)
A(1) = 0
(on verra Section 2.4 comment résoudre cette récurrence). On voit que lÕordre de grandeur du coöut des calculs nÕest plus en n3, mais seulement en nlog27 ≈ n2.8.
LÕalgorithme de Strassen nÕest pas souvent utilisé car il introduit des probl`emes dÕinstabilité numérique. Notons enÞn quÕil existe des algorithmes de complexit« meilleure que celle de Stras-sen, et que le probl`eme de déterminer la complexit« du produit de deux matrices est encore ouvert. La seule borne inférieure connue est en O (n2 ) : il faut bien toucher chaque coefficient au moins une fois. Le meilleur algorithme connu `a ce jour est en O(n2.376).
P = P1 + Xm × P2 Q = Q1 + Xm × Q2

Produit de deux polynˆomes

Le but est de multiplier deux polynöomes. On notera n-polynöomes les polynöomes de degr« strictement inférieur à n, donc avec n coefficients. Soient :
Ð P : n-polynöome : n−1 aiXi
i=0
Ð Q : n-polynöome : n−1 biXi
i=0
Ð R = P × Q =? : (2n − 1)-polynöome
Soient :
Ð M(n) = nombre de multiplications réalisées par lÕalgorithme pour multiplier deux n-polynöomes
Ð A(n) = nombre dÕadditions réalisées par lÕalgorithme pour multiplier deux n-polynöomes
Avec lÕalgorithme usuel de multiplication de n-polynöomes :
M(n) = n2 et A(n) = n2 − (2n − 1) = (n − 1)2
af f ectations
Pour compter les affectations, on note que lÕon doit faire une affectation pour chaque coefficient du polynöome R, ce sont des additions en moins. On suppose n pair, n = 2m
avec P1, P2, Q1, Q2 m-polynöomes
Soient :
R1 =P1×Q1
R2 =P2×Q2
R3 = (P1 + P2) × (Q1 + Q2)
On a alors : R = R1 +(R3 − R2 −R1)×Xm +R2 ×X2m, et R1, R2 , R3 sont des ( n−1)-polynöomes. Quel est lÕintéröet ? On ne réalise que 3 multiplications de polynöomes de taille moitié. Les addi-tions sont de deux types : les additions de polynöomes, et les additions liées aux multiplications de m-polynöomes.
On suppose maintenant que n = 2s et on applique lÕalgorithme de mani`ere récursive.
M(n) = 3 × M(n/2) =⇒ M(n) = 3s = nlog2(3) ≈ n1.58
M(1) = 1
A(n) = 3 × A(n/2) + 2 × n/2 + 2 × (n − 1) + (n − 2)
A(1) = 0
−
− R1
appels recursif s pour avoir R3 pour avoir R3 R2 construction de R
En effet, pour la construction de R :
n−2 n−2 n−2
i ri1 × Xi +
R = R1 + (R3 − R1 − R2) × Xm + R2 × X2m = zi × Xi+n/2 + ri2 × Xi+n
=0 i=0 i=0
X0→Xn−2 Xn→X2n−2
Tous les termes du terme du milieu (sauf Xn−1) sÕadditionnent aux termes de gauche et de
droite, il faut donc faire n − 2 additions. DÕo`u : − 8n + 2
A(n) = 3 × A(n/2) + 4 × n − 4 =⇒ A(n) = 6nlog2(3)
A(1) = 0
(on verra Section 2.4 comment résoudre cette récurrence)
Remarque Le meilleur algorithme de multiplication de polynöomes est en O(n × log(n)), il est obtenu par transformée de Fourrier rapide (FFT).
P,Q −→ P (xi), Q(xi) P (xi) Q(xi) −→PQ
−→ × ×
evaluation en 2n points interpolation
LÕévaluation et lÕinterpolation sont réalisées en n2 par la méthode classique, en utilisant Newton et Lagrange. Pour la FFT, on évalue les polynöomes en les racines complexes de lÕunité.

Master theorem

Diviser pour r`egner : On consid`ere un probl`eme de taille n, quÕon découpe en a sous-probl`emes de taille n/b permettant de résoudre le probl`eme. Le coöut de lÕalgorithme est alors :
S(1) = 1
S(n) = a × S(n/b) + Reconstruction(n)
c × nα en general
a b α c
Strassen 7 2 2 18/4
Polynomes 3 2 1 4
S(n) = a × S(n/b) + R(n) = a2 × S(n/b2) + a × R(n/b) + R(n) = . . .
On pose n = bk (k = logb(n)), on a alors :
k−1 ai × R(n/bi) avec R(n) = c × nα
S(n) = ak ×S(1) +
n log (a) i=0
b
P
et :
k−1
= c × nα(a/bα)i
i=0
On distingue alors plusieurs cas :
1. (a > bα) : ∼ nα × ( a )k ∼ ak =⇒ S(n) = O(nlogb(a))
bα
3. (a < b ) : c n 1 α = S(n) = O(n )
2. (a = bα) : k × nα = S(n) = O(nα × log(n))
α ∼ α ⇒ ⇒ α
∼ × × − b
La preuve compl`ete est dans le Cormen.
Retour sur Strassen :
A la lumi`ere de ce qui préc`ede, et si on découpait les matrices en 9 blocs de taille n/3 au lieu
de 4 blocs de taille n/2 ?
On a : ×
a b α c
a 3 2
18
Pour que lÕalgorithme soit plus intéressant que Strassen, il faut que :
log3(a) < log2(7)
⇒a < elog2(7)×log2(3)
⇒a < 7log2(3) ≈ 21, 8
CÕest un probl`eme ouvert : on connaöõt une méthode avec a = 23 mais pas avec a = 21 !

Résolution des récurrences

Résolution des récurrences homog`enes

p0 × sn + p1 × sn−1 + á á á + pk × sn−k = 0
k pi constantes
Soit P = i=0 pi × Xk−i. On cherche les racines de P. Si les racines de P sont distinctes : k
sn = ci × rin
Sinon, si qi est lÕordre de multiplicité de ri
l ×rin
sn = Pi(n) −
=0
polynome de degre qi 1
i

Résolution des récurrences avec second membre

On note E lÕopérateur de décalage : E{sn} = {sn+1}.
On déÞnit les opérations suivantes sur les suites :
c.{sn} = {c.sn} (2.1)
(E1 + E2){sn} = E1 {sn} + E2{sn} (2.2)
(E1E2){sn} = E1 (E2{sn}) (2.3)
(2 + E2){sn} = {2sn + sn+2}
ex : (E − 3){sn} = {sn+1 − 3sn}
P (E) annule {sn} si P (E){sn} = 0 ex :
suite annulateur
c } 1
{ E − k+1
(n) } (E−1)
{Qkn
{ c } c
{c n E − k+1
× Qk(n)} (E − c)
o`u Qk(n) est un polynöome de degr« k. En effet, il suffit de montrer la derni`ere relation, par récurrence sur k :
(E − c)k+1 {cn × Qk(n)} = (E − c)k [(E − c){cn(a0nk + Qk−1 (n))}]
{ { }
−
cn×(a0nk+Qk−1(n))} cn+1(a0(n+1)k+Qk−1(n+1)) cn+1(a0nk+Qk−1(n))
= (E − c)k[cn+1 × Rk−1(n)]
= 0
(par hypoth`ese de récurrence)
Résolution pour les additions dans lÕalgorithme de Strassen :
A(n) = 7 × A(n/2) + 18 n2
On a n = 2s, on pose As = A(2s)
(2s+1)2
As+1 = 7 × As + 18 × = 7 × As + 18 × 4s
4
(E−4) (E − 7){As } =
0
A =  k  As+1 −7As=18×4s
⇒ s 1 × 7s + k 2 × 4s
avec :
A0 = 0
A1 = 18
On en déduit les valeurs de k1 et k2 données plus haut.
Résolution pour les additions dans lÕalgorithme de multiplication de polynöomes :
A(n) = 3 × A(n/2) + 4n − 4
As = 3 × As−1 + 4 × 2s − 4
DÕo`u : (E − 1)(E − 2)(E − 3){As} = 0
⇒ As = k1 × 3s + k2 × 2s + k3
avec :
A0 = 0
A1 = 4
A2 = 24
On en déduit les valeurs de k1 = 6, k2 = −8 et k3 = 2 données plus haut.

Multiplication et inversion de matrices

Soient :
Ð M(n) = coöut de la multiplication de 2 matrices dÕordre n
Ð I(n) = coöut de lÕinversion dÕune matrice dÕordre n
Ð Hypoth`eses : − O(n2) ≤ M(n) ≤ O(n3)
I(n)
− M(n) et I(n) croissants
Théor`eme 3. M(n) et I(n) ont le möeme ordre de grandeur.
Démonstration. On montre que chaque opération est au moins aussi ÒdifficileÓ que lÕautre : 20
La multiplication est au moins aussi complexe que l’inversion
On veut multiplier les matrices A et B de taille n. Soit Z de taille 3n suivante :
I A 0
Z = 0 0 I
0 I B
⇒ I −A A.B
Z−1 = 0 I B
DÕo`u : M(n) ≤ I(3n)
L’inversion est au moins aussi complexe que la multiplication
On proc`ede en deux étapes :
Si A est symétrique définie positive C
A = D
B tC
Soit S = D − C.B−1. tC (Shur complement).
A−1 = B − 1 + B−1. tC.S−1.C.B−1 − B−1. tC.S−1
−S−1.C.B−1 S−1
Il suffit de construire :
B−1, C.B−1, (C.B−1). tC, S−1, S−1.(C.B−1), t(C.B−1).(S−1.C.B−1)
dÕo`u : I(n) = 2 × I(n/2) + 4 × M(n) + O(n2) = O(M(n))
Cas général On pose B = tA × A. On veut calculer A−1, et on sait calculer B−1 car B est symétrique déÞnie positive.
I = B−1.B = B−1.( tA.A) = (B−1. tA).A ⇒ A−1 = B−1. tA
DÕo`u : I(n) = 2 × M(n) + O(M(n)) = O(M(n))

Exercices

Exercice 2.6.1. Matrice de TÏplitz
Une matrice de TÏplitz est une matrice n×n (ai,j) telle que ai,j = ai−1,j−1 pour 2 ≤ i, j ≤ n. Question 2.1 La somme de deux matrices de TÏplitz est-elle une matrice de TÏplitz ? Et le produit ?
Question 2.2 Trouver un moyen dÕadditionner deux matrices de TÏplitz en O(n). Question 2.3 Comment calculer le produit dÕune matrice de TÏplitz n × n par un vecteur de longueur n ? Quelle est la complexit« de lÕalgorithme ?
Exercice 2.6.2. Plus grand et deuxi`eme plus grand de n entiers
Soit E une liste de n eléments rangés dans un tableau numérot« de 1 à n . On suppose que la seule opération quÕon sait effectuer sur les eléments est de vériÞer si deux eléments sont égaux ou non. On dit quÕun elément x ∈ E est majoritaire si lÕensemble Ex = {y ∈ E|y = x} a strictement plus de n/2 eléments. On suppose que n est une puissance de 2, et on sÕintéresse à la complexit« dans le pire des cas.
Question 2.4 Algorithme na¨ıf
« Ecrire un algorithme calculant le cardinal cx de Ex pour un x donné. En déduire un al-gorithme pour vériÞer si E poss`ede un elément majoritaire. Quelle est la complexit« de cet algorithme ?
Question 2.5 Diviser pour régner Donner un autre algorithme récursif basé sur un découpage de E en deux tableaux de möeme taille. Quelle est sa complexit« ?
Pour améliorer lÕalgorithme précédent, on va se contenter dans un premier temps de mettre au point un algorithme possédant la propriét« suivante :
Ð soit lÕalgorithme garantit que E ne poss`ede pas dÕélément majoritaire,
Ð soit lÕalgorithme fournit un entier p > n/2 et un elément x tels que x apparaisse au plus p fois dans E et tout elément autre que x apparaöõt au plus n − p fois dans E.
Question 2.6 Donner un algorithme récursif possédant cette propriét«. Quelle est sa com-plexit« ?
Question 2.7 En déduire un algorithme efficace vériÞant si E poss`ede un elément majoritaire.
Algorithme des balles – On change la mani`ere de voir les choses. On a un ensemble de n balles et on cherche le cas echéant sÕil y a une couleur majoritaire parmi les balles.
Question 2.8 Supposons que les balles soient rangées en Þle sur une étag`ere, de mani`ere à nÕavoir jamais deux balles de la möeme couleur à cöoté. Que peut-on en déduire sur le nombre maximal de balles de la möeme couleur ?
On a un ensemble de n balles, une étag`ere vide o`u on peut les ranger en Þle et une corbeille vide. Considérons lÕalgorithme suivant :
– Phase 1 – Prendre les balles une par une pour les ranger sur lÕétag`ere ou dans la corbeille. SI la balle nÕest pas de la möeme couleur que la derni`ere balle sur lÕétag`ere, la ranger à cöoté, et si de plus la corbeille nÕest pas vide, prendre une balle dans la corbeille et la ranger à cöoté sur lÕétag`ere. SINON, cÕest à dire si la balle est de la möeme couleur que la derni`ere balle sur lÕétag`ere, la mettre dans la corbeille.
– Phase 2 – Soit C la couleur de la derni`ere balle sur lÕétag`ere à la Þn de la phase 1. On compare successivement la couleur de la derni`ere balle sur lÕétag`ere avec C. SI la couleur est la möeme on jette les deux derni`eres balles posées sur lÕétag`ere, sauf sÕil nÕen reste quÕune, auquel cas on la met dans la corbeille. SINON on la jette et on jette une des balles de la corbeille, sauf si la corbeille est déj`a vide auquel cas on sÕarröete en décrétant quÕil nÕy a pas de couleur majoritaire. Quand on a epuisé toutes les balles sur lÕétag`ere, on regarde le contenu de la corbeille. Si elle est vide alors il nÕy a pas de couleur majoritaire, et si elle contient au moins une balle alors C est la couleur majoritaire.
Question 2.9 (Correction de lÕalgorithme) Montrer quÕ`a tout moment de la phase 1, toutes les balles éventuellement présentes dans la corbeille ont la couleur de la derni`ere balle de lÕétag`ere. En déduire que sÕil y a une couleur dominante alors cÕest C. Prouver la correction de lÕalgorithme. Question 2.10 (Complexit«) Donner la complexit« dans le pire des cas en nombre de compa-raisons de couleurs des balles.

1 Introduction : calcul de xn 
1.1 ´Enonc´e du probl`eme
1.2 Algorithme na¨ıf
1.3 M´ethode binaire
1.4 M´ethode des facteurs
1.5 Arbre de Knuth
1.6 R´esultats sur la complexit´e
1.7 Exercices
1.8 R´ef´erences bibliographiques
2 Diviser pour r´egner 
2.1 Algorithme de Strassen
2.2 Produit de deux polynˆomes
2.3 Master theorem
2.4 R´esolution des r´ecurrences
2.4.1 R´esolution des r´ecurrences homog`enes
2.4.2 R´esolution des r´ecurrences avec second membre
2.5 Multiplication et inversion de matrices
2.6 Exercices
2.7 R´ef´erences bibliographiques
3 Programmation dynamique 
3.1 Pi`eces de Monnaies
3.2 Le probl`eme du sac `a dos
3.2.1 En glouton
3.2.2 Par programmation dynamique
3.3 Quelques exemples de programmation dynamique
3.3.1 Chaˆınes de matrices
3.3.2 Plus longue sous-suite
3.3.3 Location de skis
3.4 Exercices
3.5 R´ef´erences bibliographiques
4 Algorithmes gloutons 
4.1 Exemple du gymnase
4.2 Route `a suivre pour le glouton
4.3 Coloriage d’un graphe
4.3.1 Algorithme glouton 1
4.3.2 Algorithme glouton 2
4.3.3 Graphe d’intervalles
4.3.4 Algorithme de Brelaz
4.4 Th´eorie des matro¨ıdes
4.4.1 Matro¨ıdes
4.4.2 Algorithme glouton
4.5 Ordonnancement
4.6 Exercices
4.7 R´ef´erences bibliographiques
5 Tri 
5.1 Tri fusion
5.2 Tri par tas : Heapsort
5.2.1 D´efinitions
5.2.2 Tri par tas
5.2.3 Insertion d’un nouvel ´el´ement
5.2.4 Suppression d’un ´el´ement du tas
5.2.5 Complexit´e du tri par tas
5.3 Tri rapide
5.3.1 Coˆut
5.3.2 M´ediane en temps lin´eaire
5.4 Complexit´e du tri
5.4.1 Les grands th´eor`emes
5.4.2 D´emonstration des th´eor`emes
5.4.3 Peut-on atteindre la borne ?
5.5 Exercices
5.6 R´ef´erences bibliographiques
6 Graphes 
6.1 D´efinitions
6.2 Arbres
6.2.1 Caract´erisation
6.2.2 Parcours d’arbres binaires
6.2.3 Arbres binaires de recherche
6.3 Structures de donn´ees pour les graphes
6.4 Accessibilit´e
6.4.1 Rappels sur les relations binaires
6.4.2 Chemins dans les graphes
6.4.3 Fermeture transitive
6.5 Plus courts chemins
6.5.1 D´efinitions
6.5.2 Pr´esentation des plus courts chemins
6.5.3 Avec des poids positifs
6.5.4 Chemins alg´ebriques dans les semi-anneaux
6.5.5 Algorithme de Dijkstra
6.6 Parcours en largeur
6.7 Parcours en profondeur
6.7.1 Premi`ere version
6.7.2 Analyse fine du parcours en profondeur
6.8 Tri topologique
6.9 Forte connexit´e
6.10 Exercices
6.11 R´ef´erences bibliographiques
7 Tables de hachage 
7.1 Recherche en table
7.2 Tables de hachage
7.3 Collisions s´epar´ees
7.4 Adressage ouvert
7.5 R´ef´erences bibliographiques
8 Analyse amortie 
8.1 Compteur
8.1.1 M´ethode des acomptes
8.1.2 M´ethode du potentiel
8.2 Malloc primaire
8.2.1 M´ethode globale
8.2.2 M´ethode des acomptes
8.2.3 M´ethode du potentiel
8.3 Insertion ET suppression
8.4 Gestion des partitions
8.4.1 Repr´esentation en listes chaˆın´ees
8.4.2 Repr´esentation en arbres
8.5 R´ef´erences bibliographiques
9 NP-Compl´etude 
9.1 Probl`emes de P
9.1.1 Pens´ee du jour (PJ)
9.1.2 D´efinition
9.1.3 Exemples
9.1.4 Solution d’un probl`eme
9.2 Probl`emes de NP
9.2.1 D´efinition
9.2.2 Probl`emes NP-complets
9.2.3 Exemples de probl`emes dans NP
9.2.4 Probl`emes de d´ecision vs optimisation
9.2.5 Exemple de probl`emes n’´etant pas forc´ement dans NP
9.2.6 Probl`emes polynomiaux
9.3 M´ethode de r´eduction
9.4 3-SAT
9.5 Clique
9.6 Couverture par les sommets
9.7 Cycle hamiltonien
9.8 Coloration de graphes
9.8.1 COLOR
9.8.2 3-COLOR
9.8.3 3-COLOR-PLAN
9.9 Exercices
9.10 R´ef´erences bibliographiques
10 Algorithmes d’approximation 
10.1 D´efinition
10.2 Vertex cover
10.2.1 Version classique
10.2.2 Version pond´er´ee
10.3 Voyageur de commerce : TSP
10.3.1 D´efinition
10.3.2 Inapproximabilit´e de TSP
10.3.3 2-approximation dans le cas o`u c v´erifie l’in´egalit´e triangulaire
10.4 Bin Packing : BP
10.4.1 D´efinition
10.4.2 Next Fit