TD17 : Structures de données aléatoires

Énoncé

Tables de hachage

EX 1.

$p$ premier.

0 < a < p\\ 0 ≤ b <p

Si $0 ≤ i, j ≤ p-1$, alors

ai+b ≠ aj +b \mod p

Par l’absurde : s’il y a égalité :

ai = aj \mod p \\ ⟹ i = j \mod p

car $a<p$ donc $a ∧ p = 1$, et

i = j \mod p

donc

i = j

car $i, j < p$

2.

h_{a,b}(x) = ((ax + b \mod p) \mod m) +1

Soient $u, v$ tq $0 ≤ u≠v < p$.

Mq $∃! (a,b)$ tq

ai+b = u \mod p \text{ et } aj+b = v \mod p

Supposons $v > u$.

On résout :

a(j-i) = v-u \mod p

Mais comme $j-i ≠0 \mod p$ (identifiants), $j-i$ est inversible dans $𝔽_p$, et

a = (v-u)(j-i)^{-1} \mod p

On en déduit l’existence d’un unique couple $(a,b)$ convenant.

3.

Mq

\vert \lbrace (a,b) \mid h_{a,b}(i) = h_{a,b}(j) \rbrace \vert ≤ \frac{p(p-1)}{m}

a).

Soit

𝜑 ≝ \begin{cases} ⟦1, p-1⟧ × ⟦0, p-1⟧ ⟶ ⟦0, p-1⟧ × ⟦1, p-1⟧ \\ (a,b) \mapsto (ai + b \mod p, a(j-i) \mod p) \end{cases}
h_{a,b}(i) = h_{a,b}(j) ⟹ 𝜑(a,b) ∈ \lbrace (u, km) \mid 0≤ u<p \text{ et } 0< km < p \rbrace ≝ A
\vert A \vert = p × \vert \lbrace km \mid 0 < km < p\rbrace \vert \\ ≤ \frac{p(p-1)}{m}

Il reste à montrer que $𝜑$ est injective (car on a alors $\vert \lbrace (a,b) \mid h_{a,b}(i) = h_{a,b}(j) \rbrace \vert = \vert \lbrace 𝜑(a,b) \mid h_{a,b}(i) = h_{a,b}(j) \rbrace \vert$)

Si $𝜑(a,b) = 𝜑(a’, b’) = (u,d)$

On pose

  • $u = ai+b \mod p = a’i+b’ \mod p$

  • $v = aj+b \mod p = a’j+b’ \mod p$

On a $v-u \mod p = v’ - u \mod p = d$ donc $v = v’ \mod p$ d’où $v = v’$.

Et d’après 2, on conclut que $(a,b) = (a’,b’)$.

4.

On en déduit que

q = \sum\limits_{ i < i' } \vert \lbrace (a,b) \mid h_{a,b}(i) = h_{a,b}(i') \rbrace \vert ≤ \frac{n(n-1)}{2} \frac{p(p-1)}{m}

5.

q = \sum\limits_{ (a,b) } \vert \lbrace (i, j) \mid i<j \text{ et } h_{a,b}(i) = h_{a,b}(j) \rbrace \vert ≥ \sum\limits_{ h∈H' } 1 ≥ \vert H' \vert

car si $(a, b)∈H’$, $vert \lbrace (i, j) \mid i<j \text{ et } h_{a,b}(i) = h_{a,b}(j) \rbrace \vert ≥ 1$ : il y au moins une collision.

Or

q ≤ \frac{n(n-1)}{2m} × p(p-1)

et comme $m=n^2$ :

q ≤ \frac{p(p-1)}{2}

avec $p(p-1) = \vert \lbrace (a,b) \mid 0 < a < p \text{ et } 0≤b<p \rbrace \vert$

D’où :

\vert H' \vert < 1/2 \vert H \vert

6.

Algo probabiliste :

Tirer de façon uniforme (a,b) et tester si (a,b)∉H' ((a,b) sans collision)
Avec une proba ≥ 1/2, on a une fonction sans collision

Mais il faut que m ≥ n^2

Espérance de $2$ pour trouver une fonction de hachage sans collision.


EX 2.

Avant :

Une table de taille $n^2$ pour stocker $n$ identifiants.

Maintenant :

h(id) ⟶ h_i \text{ en position } i \text{ dans la première table }\\ ⟶ \text{ position } h_i(id) \text{ dans la deuxième table }

La première table peut avoir des collisions, qui seront résolues dans la deuxième table.

1.

$H’‘⊆ H$, où $\vert H’’ \vert$ est le nombre de fonctions qui produisent au moins $n$ collisions.

Mq si $m=n$, alors

\vert H'' \vert ≤ 1/2 \vert H \vert

En effet :

q = \sum\limits_{ h∈H } \vert \lbrace (i, j) \mid i<j \text{ et } h(i)= h(j)\rbrace \vert ≥ \sum\limits_{ h∈H'' } n = n \vert H'' \vert

Or :

q ≤ \frac{n(n-1)}{2} \frac{p(p-1)}{m} ≤ \frac{(n-1)}{2} × p(p-1)

d’où :

\vert H'' \vert n ≤ \frac{(n-1)}{2} \vert H \vert

et le résultat s’ensuit.

2.

Soit $h∉H’’$ comme fonction de hachage primaire.

Soit $n_i$ le nombre d’identifiants tq

h(id) = i

NB : cela correspond au nombre d’identifiants qui vont être envoyés en position $i$ dans la première table. Donc grosso modo, (comme il va falloir les séparer dans la deuxième table) la somme des $n_i$ va être la taille de la deuxième table.

Le nombre de collisions sur $i$ vaut :

\frac{n_i(n_i-1)}{2}

c’est le nombre de paires $(id,id’)$ telles que $h(id) = h(id’) = i$.

Comme $h∉H’’$, on a strictement moins de $n$ collisions, d’où :

\sum\limits_{ i } \frac{n_i(n_i-1)}{2} < n

3.

On prend pour chaque table de hachage secondaire la fonction de hachage de l’exercice précédent.

Pour la première table, on applique une fonction $h_{a,b}$ avec $<n$ collisions. Avec $m=n$, on prend $h_{a,b}∉H’’$.

Pour la deuxième table, on applique une fonction $h_{a,b}$ avec $<n_i$ sans collisions (pour tout $i$).

Quelle est la taille de stockage ?

\sum\limits_{ i } n_i^2 = 2 \sum\limits_{ i } \frac{n_i(n_i -1)}{2} + \sum\limits_{ i } n_i \\ ≤ 2 n + n = 3n

Arbres binaires de recherche

1.

$id_i$ et $id_j$ seront comparés ssi un des deux est le premier à être inséré dans

ID(i,j) ≝ \lbrace id_i, id_{i+1}, \ldots, id_j \rbrace

Supposons que $id_i$ ou $id_j$ est inséré en premier parmi les $ID(i,j)$.

Soit $id_𝛼$ le parent commun de $id_i$ et $id_j$ le plus proche (sachant que si $id_i$ est descendant de $id_j$ alors $id_j$ est le parent le plus proche).

Raisonnons par l’absurde et supposons que $𝛼 ∉ \lbrace i, j \rbrace$.

  digraph {
    rankdir=TB;
    id_𝛼 -> id_i, id_j[style="dotted"];

  }

Notons qu’en faisant un parcours infixe de l’arbre, on a les identifiants dans l’ordre croissant : $id_i < id_𝛼 < id_j$, et on a inséré $id_𝛼$ avant $id_i$ et $id_j$ ⟶ contradiction.

Réciproquement :

on montre que si $id_i$ et $id_j$ ont été comparés, alors l’un des deux a été inséré en premier parmi les éléments de $ID(i,j)$.

En faisant un parcours infixe : on voit premier innséré entre les deux est le premier inséré parmi les éléments de $ID(i,j)$.

2.

p_m = \frac{1}{n} \sum\limits_{ i=1 }^n p(i)

Mq

p_m = 1 + \frac 1 n \sum\limits_{ i < j } X_{i,j}

En effet : $p(i)-1$ est le nombre de comparaisons nécessaires pour insérer $i$.

Donc

\sum\limits_{ i=1 }^n (p(i) -1) = \sum\limits_{ i<j } X_{i,j} \\ ⟹ \sum\limits_{ i=1 }^n p(i) = \sum\limits_{ i<j } X_{i,j} + n

3.

Calculons $E(X_{i,j})$.

P(X_{i,j} = 1) = P(id_i \text{ est le premier élément de } Id(i,j) \text{ à être inséré}) \\ + P(id_j \text{ est le premier élément de } Id(i,j) \text{ à être inséré}) \\ = \frac{1}{j-i+1} + \frac{1}{j-i+1}

(car on a une loi uniforme sur $Id(i,j)$)

Donc

E(X_{i,j}) = 1 × P(X_{i,j} = 1) = \frac{2}{j-i+1}

4.

Donc

E(p_m) = 1 + \frac 1 n \sum\limits_{ i < j } E(X_{i,j}) \\ = 1 + \frac 2 n \sum\limits_{ i < j } \frac{1}{j-i+1} \\ = 1 + \frac 2 n \sum\limits_{ k=2 }^n \frac{(n+1-k)}{k} \\ = 1 + \frac 2 n \sum\limits_{ k=1 }^n \frac{(n+1-k)}{k} - 2\\ = -1 + \frac 2 n \sum\limits_{ k=1 }^n \frac{(n+1-k)}{k} \\ = -1 + \frac{2(n+1)}{n} \sum\limits_{ k=1 }^n \frac{1}{k} - 2\\ = -3 + 2 \Big(\frac{1}{n}+1 \Big) \sum\limits_{ k=1 }^n \frac{1}{k}

Or :

\ln(n+1) ≤ H_n ≤ 1 + \ln(n)

6.

La complexité d’une recherche fructueuse correspond au nombre de comparaisons que l’on fait en moyenne, c’est-à-dire :

E(p_m) \sim 2 \ln(n)

7.

Pour la recherche infructueuse, cela correspond à l’ajout d’un identifiant ⟶ identique à la recherche fructueuse de $id_i$ et $id_{i+1}$ avec $id_i < id_{i+1}$ (il y a un ajout de 1 en plus par rapport à la recherche fructueuse).

8.

On pose $p_n ≝ p_{max}$ pour $n$ identifiants, et $f_n ≝ 2^{p_n}$ (profondeur exponentielle).

On note $f_{n,i}$ la profondeur exponentielle d’un arbre où $id_i$ est le premier identifiant inséré.

On montre que

f_{n,i} = 2^{1+\max (p_{i-1}, p{n-i})}

En effet :

  digraph {
    rankdir=TB;
    A[label="ABR sur {1, ⋯, i-1}"];
    B[label="ABR sur {i+1, ⋯, n}"];
    id_i -> A, B;
  }
f_{n,i} = 2^{1+ \max(p_{i-1}, p_{n-i})} ≤ 2(2^{p_{i-1}} + 2^{p_{n-i}})

car $2^{\max(a,b)} ≤ 2^a + 2^b$ comme $2^{\max(a,b)}$ est l’un des deux termes positifs.

E(f_n) = \frac 1 n \sum\limits_{ i=1 }^n E(f_{n,i}) ≤ \frac 1 n

(probabilités totales)

et :

E(f_n) ≤ \frac 1 n \sum\limits_{ i=1 }^n 2(E(f_{i-1}) + E(f_{n-i})) \\ ≤ \frac 1 n \sum\limits_{ i=1 }^{n} 2(E(f_{i-1}) + E(f_{n-i})) \\ ≤ \frac 4 n \sum\limits_{ i=1 }^{n-1} E(f_i)

10.

On le par réc forte sur $n$ :

  • Pour $n=2$ : petit calcul immédiat

  • Pour $n$ :

    E(f_n) ≤\frac 4 n \sum\limits_{ i=1 }^{n-1} E(f_i) ≤ \frac 4 n \sum\limits_{ i=1 }^{n-1} (i^3 + 1) \\ ≤ \frac 4 n \sum\limits_{ i=1 }^{n-1} i^3 + \frac 4 n (n-1) \\ ≤ n(n-1)^3 + \frac 4 n (n-1) ≤ n^3 +1

11.

Par Jensen :

E(p_n) = E(\log f_n) ≤ \log E(f_n) \\ ≤ \log (n^3+1) ≤ \log (2n^3) ≤ \log 2 + 3 \log (n) = 3 \log (n) + 1

Leave a comment