Séminaire du 9 décembre 2002, Marianne Durand

Un algorithme de comptage probabiliste

Les algorithmes de comptage probabilistes estiment le nombre d'\'el\'ements diff\'erents dans un ensemble de taille tr\`es grande, en une seule passe, et en utilisant un espace m\'emoire tr\`es r\'eduit. On pr\'esente ici une am\'elioration de l'algorithme de comptage probabiliste de Flajolet-Martin. Cet algorithme est bas\'e sur la taille des s\'equences initiales de 0 dans la repr\'esentation binaire des \'el\'ements. L'erreur obtenue est d'environ 3\% avec une m\'emoire auxilliaire de seulement 10~kbits. L'analyse de cet algorithme fait intervenir des maximums de variables al\'eatoires g\'eom\'etriques et la transformation de Mellin.