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 16 Décembre 2003

Un algorithme de comptage probabiliste

par Marianne Durand (Projet Algo, INRIA)

Un algorithme de comptage probabiliste, ou comment compter le nombre d'éléments distincts dans un grand ensemble de données en disposant d'un espace mémoire très restreint.

Grace a des propriétés de mots binaires aléatoires comme la fréquence d'un préfixe de zéros de taille $k$, on peut estimer avec une précision de quelques pour cents le nombre d'éléments distincts dans un ensemble de grande taille (des milliers de Go) en utilisant un espace mémoire de 1 kbit.

Je présenterai l'algorithme, et montrerai de nombreux exemples d'applications. J'expliquerai les grandes lignes de l'analyse dans la mesure du temps restant.

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