Introduction

Diviser pour régner:

tri rapide

tri par fusion

minmax

Trouver le minimum et le maximum d'un tableau

multiplication de longs entiers

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

Addition est rapide (linéaire); multiplication lente

(Bx1+y1)*(Bx2+y2) B est une puissance de b.

=B2x1x2+B(x1y2+x2y1)+y1y2

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

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

L'algorithme de Strassen pour multiplication de matrices

Même idée: réduire le nombre de multiplications de matrices n/2 × n/2 de 8 à 7

analyse

(recurrence Pour les cas compliqués (différence entre niveaux non uniforme, aléatoire), dériver et résoudre une recurrence.

Algorithmes gloutons

arbre recouvrant de poids minimum

Dans un graphe où les arêtes ont un poids, trouver l'arbre qui relie tous les sommets avec somme des poids minimisée

Algorithme très glouton non optimal:
commencer avec un arbre d'un seul sommet et choisir toujours l'arête du poids minimum pour rajouter le prochain sommet

Algorithme glouton et optimal:
commencer avec n arbres chacun d'un seul sommet
choisir toujours l'arête du poids minimum qui relie deux arbres;
raison d'optimalite;
détails de la recherche de cette arête omis ici.

sac-a-dos continu

Remplir un containeur avec la charge de la plus grande valeur possible étant donné plusieurs matériaux, chacun avec une valeur/kilo et une quantité disponible
choisir toujours le matériau avec la meilleure rapport valeur:poids;
pourquoi optimale

Des cas où la méthode gloutonne n'est pas optimal

commentaires sur non existence d'algorithmes efficaces (connus) pour ces 3 derniers




File translated from TEX by TTH, version 3.05.
On 27 Jan 2004, 08:53.