La délégation

Actualité complète

04/02/2010 Cycle de conférences mensuelles Jacques Morgenstern : " Théorie de l'information : modèles, algorithmes, analyse"

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.