Comment compter avec le hasard ?
Philippe Flajolet
INRIA-Rocquencourt
Tue, Nov. 18th 2008, 11:00
Salle Claude Itzykson, Bât. 774, Orme des Merisiers
Grâce à quelques algorithmes probabilistes simples, il s'avère possible de déterminer ``au vol'' et avec très peu de mémoire auxiliaire certaines caractéristiques quantitatives de flux massifs de données. Les algorithmes correspondants reposent de manière cruciale sur une analyse de modèles discrets. On donnera un aperçu d'algorithmes fondamentaux relatifs au comptage et à la détermination de la cardinalité (nombre de valeurs différentes), ainsi qu'à la boucle d'analyse-conception qui met en jeu des méthodes de la combinatoire analytique (fonctions génératrices et transformation de Mellin, notamment). Quelques applications à la gestion de réseaux et à la classification de documents seront également évoquées.
Contact : Loic BERVAS

 

Retour en haut