Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 9 Novembre 2004

Comment compter par tirages à pile ou face

par Philippe Flajolet (INRIA Rocquencourt, Académie des Sciences, médaillé du CNRS)

Cette conférence présente quelques axes de développement d'une algorithmique cohérente et générique d'estimation rapide de caractéristiques essentielles des volumes massifs de données. Il s'agit d'utiliser une mémoire très limitée et un tout petit nombre d'instructions par élément traité. Cette algorithmique est par nature probabiliste (étant fondée sur le hachage) mais elle ne se s'autorise pratiquement aucune hypothèse statistique a priori quant aux types de données auxquels elle s'applique. Les problèmes traités concerneront le comptage approximatif, le comptage probabiliste du nombre d'éléments différents, l'échantillonnage des domaines, ainsi que l'estimation des "moments des fréquences". L'analyse de ces algorithmes, nécessaire à leur validation, met en jeu des méthodes parfois sophistiquées de la combinatoire analytique dont il sera donné au passage un bref aperçu.

Références: http://algo.inria.fr/flajolet/Publications/publist.html Voir: Counting by coin tossings, 2004

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr