Return to search

Combinatoire analytique et algorithmique des ensembles de données.

Cette thèse traite d'algorithmique des ensembles de données en adoptant le point de vue de la combinatoire analytique. On traite ici de trois problèmes qui illustrent cette approche: les listes à sauts associées à de l'analyse asymptotique bivariée, le hachage à essai aléatoire avec pagination et le comptage probabiliste. Les listes à sauts sont une structure de données intermédiaire entre les skiplists et les arbres binaires de recherche. L'étude de cette structure a donné lieu à un problème d'asymptotique bivariée avec coalescence de singularités. Le hachage avec essai aléatoire est un algorithme qui gère les collisions d'une table de hachage. Dans le contexte étudié qui est celui de la pagination, on obtient la moyenne, ainsi que tous les moments successifs du coût de construction. Les algorithmes de comptage probabilistes originaux Loglog et Super Loglog permettent d'estimer le cardinal d'un ensemble en utilisant un kilooctet de mémoire avec une précision d'environ 3%.

Identiferoai:union.ndltd.org:CCSD/oai:pastel.archives-ouvertes.fr:pastel-00000810
Date30 April 2004
CreatorsDurand, Marianne
PublisherEcole Polytechnique X
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.0015 seconds