Introduction

Diviser pour régner:

tri rapide

tri par fusion

Plus complexe que le précédent?
seulement dans le fait qu'on est obligé d'utiliser un deuxième tableau

minmax

Trouver le minimum et le maximum d'un tableau

multiplication de longs entiers

Multiplication de deux entiers représentés par plusieurs chiffres à une base b

Addition est rapide (linéaire); multiplication lente

Considérer la moitié gauche des chiffres x et la moitié droite y; le nombre est Bx+y où B est une puissance de b.
(Bx1+y1)*(Bx2+y2)
=B2x1x2+B(x1y2+x2y1)+y1y2

Calculer x1x2, y1y2 et (x1+y1)(x2+y2) et soustraire.

Economiser une mutiplication à un coût de 3 addition/soustractions de plus

analyse pour nombres de n chiffres

L'algorithme de Strassen pour multiplication de matrices

Même idée (on suppose que les matrices sont carrées et de la même taille paire n): si le produit de A et B est C, on peut diviser chaque matrice en quatre blocs de taille n/2 et:

(
A1,1
A1,2
A2,1
A2,2
)×(
B1,1
B1,2
B2,1
B2,2
) =
(
A1,1B1,1+A1,2B2,1
   A1,1B1,2+A1,2B2,2
A2,1B1,1+A2,2B2,1
     A2,1B1,2+A2,2B2,2
)

On peut réduire le nombre de multiplications de matrices n/2 ×n/2 de 8 à 7 par le même type d'astuce que dans la multiplication de longs entiers.

analyse




File translated from TEX by TTH, version 3.05.
On 20 Sep 2005, 15:55.