Les tables de dispersions Flashcards

Question

Preuve du Théorème du Sondage Quadratique

Answer 1

Stratégie : Nous allons démontrer que les ⎡𝑵/𝟐⎤ premières positions sondées sont toutes distinctes. ⇒ (Si c’est le cas, un des sondages trouvera nécessairement une case vide puisqu’il y a en au moins ⎡𝑵/𝟐⎤ qui sont vides parmi N) 1) Poser 2 sondages le i-ème et j-ième - avec i < j sans perte de généralité - et 0 ≤ i,j ≤ ⎡𝑵/𝟐⎤ - 1 = ⎣𝑵/𝟐⎦ (car N est impair) 2) Si les 2 sondages pouvaient être identiques alors ( h(x) + i² ) mod N = ( h(x) + j² ) mod N ⇒ i² mod N = j² mod N ⇒ (j² - i²) mod N = 0 ⇒ (j – i) (j + i) mod N = 0 ⇒ (j – i) (j + i) doit être un multiple de N Impossible car N est premier et i,j ≤ ⎣𝑵/𝟐⎦. CQFD

Answer 2

f(i) = i * h’(x) hi(x) = ( h(x) + f(i) ) mod N h'(x) ne doit jamais être = 0

Answer 3

h'(x) = R - c(x) mod R Où R est un nombre premier plus petit que N

Answer 4

Pour 2 valeurs hachant au même index, le double hachage ne produit généralement pas la même séquence de sondage subséquente. ⇒ il produit moins de sondage que le sondage quadratique. Mais cela se fait au prix d’un temps d’exécution plus lent (dû au calcul de h’(x)) par sondage. ⇒ En pratique, il n’y a pas toujours un gain de performance.

Answer 5

En fait, il existe toujours plusieurs séquences de clés qui ont la propriété de hacher toutes vers le même index. - Donc, toute fonction h possède ce cas le plus défavorable qui produira un temps d’exécution en Θ(n) pour les recherches, insertions et suppressions. - Peu importe la méthode utilisée pour résoudre les collisions.

Answer 6

Une famille H de fonctions hachant ses clés dans une table de N indexes est dite universelle si pour toute paire (x,y) de clés distinctes, le NOMBRE de fonctions h de H telle que h(x) = h(y) est au plus |H|/N.

Answer 7

..au plus de (|H|/N)/|H| = 1/N | Avec une distribution uniforme sur H

Answer 8

* est ≤ λ lorsque x n’est pas parmi les n clés, | * est ≤ 1 + λ lorsque x est parmi les n clés.

Answer 9

Pour toute variable aléatoire X non négative dont l’espérance E X = μ, et pour tout entier t > 0, on a: Pr(X ≥ t) ≤ μ/t.

Answer 10

On est en situation de hachage parfait lorsque les recherches de clés s’effectuent en O(1) en pire cas.

Answer 11

1- lorsque la distribution des clés stockées dans la table est statique. 2- en choisissant aléatoirement notre fonction de hachage dans une famille universelle de fonctions de hachage

Answer 12

- Pour n éléments èa stocker. - Une table primaire de n alvéoles. - Chaque alvéoles pointent sur une table secondaire distincte de nj^2 alvéoles (nj = nombres de clés hachant en j sur la primaire)

Answer 13

Si on stocke n clés dans une table de hachage primaire de taille n via une fonction de hachage tirée aléatoirement dans une classe universelle, alors l’espérance de la somme des tailles des tables secondaires sera < 2n

Answer 14

n(n-1)/(2N)

Answer 15

Considérons d’abord que les clés sont des entiers non signés. - Soit N la taille de la table (pas nécessairement un nombre premier ici). - Soit P (avec P > N) un nombre premier assez grand, pour que toutes les clés possibles aient une valeur comprise dans {0, 1, …, P-1}. - Pour tout nombre a dans {1, ..., P-1} et b dans {0,1, ..., P-1}, soit ha,b défini tel que pour toute clé x, on a: - ha,b(x) = ( (a x + b) mod P ) mod N - Comme il y a P-1 valeurs possibles pour a et P valeurs possibles pour b, cette famille H(P,N) possède P(P-1) fonctions de hachage.