Sujet:
Contexte:
Les algorithmes classiques de géométrie algorithmique
sont généralement complexes et difficiles à mettre en oeuvre.
Une des réponses possible consiste à utiliser des algorithmes
plus simples, dont la complexité n'est pas optimale dans tous les
cas, mais seulement en moyenne sur
certains choix aléatoires fait par l'algorithme:
les algorithmes randomisés.
Contrairement à un algorithme classique qui déduit un résultat
à partir de certaines données de départ en suivant un chemin bien
déterminé, l'algorithme randomisé a le choix entre plusieurs chemins
pour parvenir à ses fins. L'intervention du hasard dans ce type
de méthodes réside dans la manière de choisir le chemin que va
finalement suivre l'algorithme.
L'analyse de l'algorithme est alors faite en moyenne sur les différents
chemins possibles. Aucune hypothèse n'est faite sur la répartition
des données.
Le comportement d'un algorithme incrémental (en ligne
(i.e. un algorithme où les données sont ajoutées une à une
et ou le résultat est mis à jour après chaque insertion)
dépends évidemment de l'ordre d'insertion des données.
Un moyen largement utilisé consiste à faire une analyse
randomisée des algorithmes incrémentaux, c'est à dire
que l'on suppose l'ordre d'insertion choisi aléatoirement
parmi tous les ordres possibles.
Choisir un ordre aléatoire sur n données
nécessite de connaître toutes ces données dès le début
de l'algorithme ce qui fait que l'algorithme n'est plus en ligne.
Travail demandé:
On s'interressera à l'étude de complexité d'algorithme randomisé
en ligne dans lesquels on cherche à démarrer l'algorithme avant de
connaître toutes les données. Une stratégie possible consiste à
intercaller un tampon mélangeur entre le processus qui
fournit les données et l'algorithme:
on range les k premières données dans le tampon pour l'initialiser,
puis à chaque étape on choisit aléatoirement une donnée dans le tampon
pour l'insérer dans notre algorithme, et on place dans le tampon
la donnée suivante.
Il est clair que si k=n on obtient un ordre aléatoire pour notre
algorithme et que si k=1 l'ordre est totalement imposé par l'extérieur.
Par contre pour des valeurs intermédiaires de k l'étude reste
à faire (et fait l'objet du stage).
Résultats :
Philippe Guigue poursuit en thèse dans le projet.
Pour plus d'informations, contacter
Olivier.Devillers
ou
Philippe Guigue
Retour aux autres stages
Stage effectué dans le projet PRISME