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);
- langage: approx C;
- livre: Cormen, Leiserson, Rivest et Stein: Intro a l'algorithmique,
Dunod, BU 681.31.01 COR;
- web: www.labri.fr/ robson/AlgAv/
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 (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
tri par fusion
- Diviser les éléments en deux parties (équilibrés)
- Trier chaque partie
- Fusionner
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
- Approx 3n/2 comparaisons
- Comparer les deux min et les deux max
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
- Considérer l'arbre de tous les appels de la fonction
- Considérer le temps à chaque niveau pour diviser et
fusionner
- Souvent hauteur de l'arbre proportionnelle à logn
- Si travail à un niveau inférieur* à celui du
niveau précédent, le travail à la racine domine
- Si supérieur*, le travail au niveau des feuilles domine (entiers,
Strassen)
- Si constant, multiplier par hauteur (tris)
(recurrence Pour les cas compliqués (différence entre niveaux
non uniforme, aléatoire), dériver et résoudre une recurrence.
Algorithmes gloutons
- Des algorithmes qui trouvent une ßolution" entre plusieurs possibles
qui sont comparables selon un critere global;
- a chaque etape choisir selon les informations locales;
- pas forcement evident si la methode gloutonne trouve la meilleure;
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
- sac-a-dos discret: des objets qu'on ne peut pas découper;
exemple de non optimalite;
- coloration de graphes: on veut colorier les sommets d'un graphe avec
le plus petit nombre de couleurs possible sujet à la règle que
deux sommets reliés par une arête doivent recevoir des couleurs
différentes;
exemple de non optimalite;
- commis voyageur: Etant donné une carte avec les distances (coûts)
entre des paires de villes, trouver le chemin le moins coûteux qui
passe par chaque ville une seule fois (et retourne au point de départ)
exemple de non optimalite;
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.