L'Inria Sophia Antipolis - Méditerranée en
collaboration avec le laboratoire I3S (CNRS/UNSA), l'Ecole
Doctorale STIC (Université de Nice-Sophia Antipolis), vous
invitent au cycle de conférences "Colloquium Jacques
Morgenstern", le 11
février 2010 à 11 h, intitulée : "
Théorie de
l’information : modèles, algorithmes,
analyse" par Brigitte Vallée (Université de
Caen, France).
Cette conférence aura lieu à l'Ecole Polytechique de
Nice-Sophia Antipolis (site des Templiers) -
Amphithéâtre Ouest). Plan
Résumé/ Abstract :
Tout étudiant d’un cours d’algorithmique de base
apprend que la complexité moyenne de l’algorithme
QuickSort est en O(n log n), celle de QuickSelect est en O(n) et
celle de RadixSort est en O(n log n). De tels énoncés
ont le mérite d’être simples, mais leur
simplicité est trompeuse, car ils sont fondés sur des
hypothèses spécifiques à chaque algorithme :
pour les deux premiers algorithmes, le coût unitaire est la
comparaison entre clés, tandis que, pour le
troisième, le coût unitaire est la comparaison entre
symboles.
Ces études souffrent donc de deux inconvénients
majeurs : il n’est pas possible de comparer réellement
ces algorithmes entre eux, car les mesures de coût sont
différentes. Ensuite, la mesure de coût adoptée
pour analyser QuickSort ou QuickSelect est peu réaliste,
dès que les clés ont une structure complexe, ce qui
est le cas dans le contexte des bases de données ou de la
langue naturelle, par exemple.
Pour effectuer une analyse réaliste, il faut donc
d’abord travailler en théorie de l’information
pour définir un cadre adapté. En théorie de
l’information, une source est un mécanisme
aléatoire qui produit des symboles d’un alphabet
donné. On construit ici un modèle de source
très général, qui prenne en compte la
possibilité de corrélations importantes entre
symboles émis. Les clés considérées par
l’algorithme sont alors des mots produits
(indépendamment) par la même source.
Il faut ensuite considérer un coût unitaire qui
soit le même pour tous les algorithmes : c’est la
comparaison entre symboles, et le coût de l’algorithme
est donc le nombre total de comparaisons effectuées entre
symboles.
Nous revisitons ainsi, dans un tel modèle, à la
fois unifié et réaliste, l’analyse probabiliste
de trois principaux algorithmes : QuickSort, QuickSelect, et les
algorithmes de dictionnaire fondés sur la structure de
tri.
Cet exposé est fondé sur des travaux communs avec
Julien Clément, James Fill, et Philippe Flajolet.