Techniques algorithmiques

Algorithmes randomisés

Les algorithmes randomisés sont des algorithmes qui effectuent des choix aléatoires au cours de leur déroulement.

Contrairement aux algorithmes probabilistes (dits de Monte Carlo) les algorithmes randomisés (encore appelés algorithmes de Las Vegas) fournissent la solution exacte d'un problème déterministe et ne font aucune hypothèse statistique sur les données traitées. Seule leur complexité dépend des choix aléatoires effectués et s'analyse en moyenne. En conférant aux situations défavorables un poids statistique négligeable, la randomisation conduit à des algorithmes simples et efficaces, notamment en géométrie.

La randomisation est aussi devenue une méthode de preuve permettant d'établir certains résultats combinatoires. Enfin, et ce n'est pas le moindre des paradoxes, la dérandomisation d'algorithmes randomisés permet, dans certains cas, d'établir des algorithmes déterministes optimaux.

Le projet Prisme s'est plus particulièrement spécialisé dans les algorithmes randomisés incrémentaux et a développé la méthode du graphe d'influence. Le graphe d'influence est une structure de données qui retrace l'histoire de la construction d'un objet. L'utilisation d'une telle structure conduit à des algorithmes semi-dynamiques capables d'insérer en ligne des données qui ne sont pas connues au départ. Pour la plupart des problèmes fondamentaux, on peut même obtenir un algorithme dynamique traitant non seulement les insertions mais aussi les suppressions de données.

Une autre utilisation de techniques randomisées a récemment été développée pour la recherche de voisins dans des espaces de très grandes dimensions en algorithmique moléculaire.

Algorithmes adaptatifs

Les algorithmes adaptatifs sont des algorithmes dont la complexité est fonction de la valeur effective de certains paramètres significatifs (la taille de l'objet calculé, par exemple) et non de la valeur de ces paramètres dans le pire des cas.

Pour la plupart des problèmes géométriques, la taille du résultat est très variable non seulement en fonction du nombre de données traitées mais aussi en fonction du jeu de données lui-même. Par exemple, l'enveloppe convexe d'un ensemble de n points en dimension d est un polytope dont le nombre de faces peut varier de (d+1) ! (pour un (d+1)-simplexe) à $\Omega (n^ { \lfloor {\frac{d+1}{2}} \rfloor }) $ (pour un polytope maximal à n sommets) ; le nombre d'intersections d'un ensemble de n segments du plan peut varier de 0 à n (n-1) / 2. Pour ces exemples, il est donc particulièrement intéressant de disposer d'algorithmes adaptatifs dont la complexité dépend de la taille du résultat. Dans d'autres problèmes, ce sont d'autres paramètres qui peuvent jouer un rôle crucial. La contribution du projet Prisme dans ce domaine concerne essentiellement les problèmes d'enveloppes convexes d'objets plans et de percement (ou, par dualité, de couverture).


Last modified: Mon Nov 29 11:09:29 MET 1999 Monique Teillaud Thèmes Accueil PRISME English