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 12 Décembre 2000

Hachage non uniforme: Apparition et taille des composantes geantes

par Jean-François Marckert (Universite de Versailles)

Le problème du hachage peut se modéliser par un problème de parking où $m$ voitures se garent sur $n$ places numérotées de $1$ à $n$. La voiture $v_i$ choisit la place $k$ avec probabilité $p_k$. Si la place $k$ est déjà occupée, la voiture $v_i$ se garera sur la première place libre parmi les places suivantes $k+1, k+2, ...$ (avec la convention $n+1=1$).

Quand les probabilités $p_k$ sont toutes égales, ce problème est le problème de parking uniforme (usuel). Il correspond exactement en informatique au hachage linéaire standard.

Ici, on s'intéresse au cas non uniforme : les probabilités ne sont plus toutes égales, et certaines places sont plus "souvent" choisies que d'autres.

On étudie plus particulièrement la taille des blocs (places successives occupées) dans le parking lorsque les nombres $m$ et $n$ de voitures et de places grandissent tous deux, tout en restant proportionnels $m=\alpha\, n$ avec $0 <\alpha <1$.

On montre alors qu'il existe une fonction de seuil pour l'apparition d'un bloc géant (de l'ordre de $n$). On compare ces résultats à ceux du cas uniforme.

On montre que le déplacement total des voitures pour le remplissage du parking est de l'ordre de $n^2$ (contre $n^{3/2}$ pour le cas uniforme). Ceci fournit donc, entre autres, une analyse en moyenne et dans le pire des cas du problème du hachage lineaire.

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