Introduction

• idee de base du cours: comment concevoir d’algorithmes efficaces (et savoir qu’ils sont corrects et efficaces ou savoir que c’est peu probable qu’un algorithme efficace existe);

• livre: Cormen, Leiserson, Rivest et Stein: Intro a l’algorithmique, Dunod, BU 681.31.01 COR;

• web: dept-info.labri.fr/~robson/AlgAv/

• langage: EXALGO (voir liens sur la page web)

Diviser pour régner:

• Résoudre un probleme en résolvant 2 ou plus problémes du même type

• Pas la même chose que la programmation structurée: c’est le programme qui divise, pas le programmeur

• Souvent donne algorithmes efficaces

• Souvent donne algorithmes élégants

• Parfois conflit entre ces deux

tri rapide

• Choisir un élément pivot du tableau (la méthode de base choisit le premier)

• Diviser le tableau en trois parties: ceux plus petits que le pivot, ceux égaux, ceux plus grands

• Appliquer la même méthode aux première et troisième parties

• Rapport avec arbre binaire de récherche Etant donné un ensemble de valeurs, en choisir une arbitrairement comme racine/pivot; diviser les autres en celles plus petites et celles plus grandes; appliquer le même processus aux deux parties (sauf si elles sont vides.)

tri par fusion

• Diviser les éléments en deux parties (de tailles équilibrées)

• Trier chaque partie

• Fusionner 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 • Si deux éléments, comparer les, sinon

• Diviser le tableau en deux parties (paires...)

• Trouver min et max de chaque partie

• Comparer les deux min et les deux max • Approx 3n/2 comparaisons

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. (Bx_{1} + y_{1}) ∗ (Bx_{2} + y_{2}) = B^{2}x_{1}x_{2} + B(x_{1}y_{2} + x_{2}y_{1}) + y_{1}y_{2}

Calculer x_{1}x_{2}, y_{1}y_{2} et (x_{1} + y_{1})(x_{2} + y_{2}) et soustraire.

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

analyse pour nombres de n

chiffres

• Considérer l’arbre de tous les appels de la fonction

• hauteur log_{2} n

• nombre d’appels multiplié par 3 à chaque niveau

• Aux feuilles: multiplication de chiffres

• nombre de multiplications 3^{log_{2} n} = n^{log_{2} 3} • Plus additions à chaque autre niveau:

• Nombre d’additions aussi O(n^{log_{2} 3})

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:

( \begin{matrix}A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2} \end{matrix} ) × ( \begin{matrix}B_{1,1} & B_{1,2} \\ B_{2,1} & B_{2,2} \end{matrix} ) =

( \begin{matrix}A_{1,1} B_{1,1} + A_{1,2} B_{2,1} & A_{1,1} B_{1,2} + A_{1,2} B_{2,2} \\ A_{2,1} B_{1,1} + A_{2,2} B_{2,1} & A_{2,1} B_{1,2} + A_{2,2} B_{2,2} \end{matrix} )

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

• Considérer l’arbre de tous les appels de la fonction

• hauteur log_{2} n

• nombre d’appels multiplié par 7 à chaque niveau

• Aux feuilles: multiplication d’éléments de base

• nombre de multiplications 7^{log_{2} n} = n^{log_{2} 7} • Plus O(n^{log_{2} 7}) additions