• 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)

• 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

• 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.)

• Diviser les éléments en deux parties (de tailles équilibrées)
• Trier chaque partie
• Fusionner

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 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₁+y₁)*(Bx₂+y₂)
=B²x₁x₂+B(x₁y₂+x₂y₁)+y₁y₂

Calculer x₁x₂, y₁y₂ et (x₁+y₁)(x₂+y₂) et soustraire.

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

• Considérer l'arbre de tous les appels de la fonction
• hauteur log₂ n
• nombre d'appels multiplié par 3 à chaque niveau
• Aux feuilles: multiplication de chiffres
• nombre de multiplications 3^{log₂ n} = n^{log₂ 3}
• Plus additions à chaque autre niveau:
• Nombre d'additions aussi O(n^{log₂ 3})

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.

• Considérer l'arbre de tous les appels de la fonction
• hauteur log₂ n
• nombre d'appels multiplié par 7 à chaque niveau
• Aux feuilles: multiplication d'éléments de base
• nombre de multiplications 7^{log₂ n} = n^{log₂ 7}
• Plus O(n^{log₂ 7}) additions