Implémentation de Tableaux associatifs - Corrige

def lc_get(t, c, defaut ) :
    for couple in t :
        if couple[0] == c :
            return couple[1]
    return defaut

La complexité de la fonction est linéaire en le nombre de clés.

def lc_del(t, c ) :
    for i in range(len(t)) :
        if t[i][0] == c :
            t.pop(i)
            return True
    return False

La complexité de la fonction est linéaire en le nombre de clés. Au pire des cas toutes les clés sont parcouru et la fonction pop ( $\mathtrm O(n) ) est appelée au plus une fois.

Implémenter une fonction lc_set qui prend en entrée un tableau associatif, une clé et une valeur et qui :

• modifie la valeur associée à la clé si la clé est déjà présente dans le tableau.
• ajoute le couple (clé,valeur) dans le tableau si la clé n’est pas présente.

Donnez la complexité de l’opération et prouvez sa correction.

def lc_set(t, c, v ) :
    for i in range(len(t)) :
        if t[i][0] == c :
            t[i] = (c,v) # Attention un tuple est immutable
            return False # Premier point de sortie
    t.append((c,v))
    return True # Deuxième point de sortie

La complexité de la fonction est linéaire en le nombre de clés. Pour la correction :

1. On rappel la pré-condition et post-condition :
   • Pré-condition : t est un tableau associatif et c appartient au domaine de clé.
   • Post-condition : t est toujours un tableau associatif et (c,v) est dans t.
2. On note qu’il y a deux point de sortie de la fonction qui correspondent aux deux cas à traiter :
   • Cas 1. c est une clé de t.
   • Cas 2. c n’est pas une clé de t.
3. Le cas d’une sortie dans la boucle correspond au cas 1. Si on sort de la fonction par le premier point de sortie, la condition t[i][0] = c= est vérifiée et c est dans t. L’exécution de t[i] = (c,v) garanti qu’à la sortie, (c,v) est dans t. t est toujours un tableau associatif car la clé c apparaît toujours une seule fois dans t à l’indice i.

4. Le cas d’une sortie hors de la boucle correspond au cas 2. Intuitivement, si on sort de la boucle, on peut en conclure que la condition t[i][0] = c= est fausse pour tout i et que c n’est pas dans le tableau associatif. On prouve ceci formellement grâce à l’invariant de boucle suivant :

   \[ \forall j < i, t[j][0] \neq c \]

   En effet, l’invariant est vrai avant d’entrée dans la boucle. S’il est vrai au début du tour de boucle i :

   • Soit t[i][0] = c= et on met fin à la fonction
   • Soit t[i][0] ! c=, on atteint la fin de la boucle et au début du tour i+1 on a bien \(\forall j < i+1, t[j][0] \neq c\).

   On en conclut que l’ajout de (c,v) dans t préserve la propriété d’unicité des clés et que t reste un tableau associatif. La post-condition est donc vérifiée.

1. On note \(\mathcal K\) l’ensemble de clés. \(\mathbb N = \mathcal F(\mathbb N) \subseteq \mathcal F(\mathcal K) \subseteq \mathbb N\)

2. On note \(\Sigma^*\) l’ensemble des chaînes de caractère et \(\Sigma^{50}\) l’ensemble des chaînes de caractères de tailles 50. On remarque que \(\mathcal F(s)\) convertir en base 10 le nombre écrit en base 256 obtenu en remplaçant chaque caractère par son code ASCII entre 0 et 255. Donc \(\mathcal F\) est injective sur \(\Sigma^{*}\) et surjective de \(\Sigma^{50}\) sur \(\{ 0 = \mathcal F(""), \dots, \mathcal F(\mathtt{chr}(255) * 50 ) \}\).

   \(\mathcal F( \{ 0, \dots, 2^{64} \} \cup \Sigma^{50}) = \{ 0, \dots, \max(2^{64}, \sum_{i = 0}^{50 - 1} 255 * 256^i ) \}\). Or \(\sum_{i = 0}^{50 - 1} 255 * 256^i < 256^{50} = (2^{8})^{50} = 2^{200}\), donc \(\mathcal F(\{ 0, \dots, 2^{64} \} \cup \Sigma^{50}) = \{ 0, \dots, 2^{200} \}\).

3. Le seul cas pour lequel il y a collision est pour une chaîne \(s\) et l’entier \(\mathcal F(s)\). La fonction de hachage n’est pas parfaite.
4. L’ensemble des index générés par \(\mathcal F\) est infini, on ne peut pas l’utiliser comme fonction de hachage. Si on borne l’ensemble des clés possibles, le nombre de case à allouer dans le tableau reste très grand.

5. def hash(k) :
       if type(k) == int :
           return k
       sum = 0
       for c in reversed(k) :
           sum = sum*256 + ord(c)
       return sum
   

6. \(\mathrm O(1)\)
7. \(\mathrm O(|k|)\)

On considère l’ensemble des fonctions de hachages suivant : \[\forall n \in \mathbb N, \cal F_n(k) = \cal F(k) \, \% \, n \]

1. \(\{ 0, n-1 \}\)
2. \(\{ 0, n-1 \}\)

3. On note donc que \(\forall 0 \leq i < n\,A, \mathbb P(\mathcal F(u) = i) = \frac 1 {n\,A}\). On pose \(E_i = \{ i + q\, n, 0 \leq q \leq A-1\}\) pour tout \(0 \leq i \leq n-1\).

   \begin{align*} \forall u, v \in \mathcal U, \, \mathbb P(\mathcal F_n(u) = \mathcal F_n(v)) & = \sum_{i = 0}^{n-1} \mathbb P(\mathcal F_n(u) = i \cap \mathcal F_n(v) = i ) \\ & = \sum_{i = 0}^{n-1} \mathbb P(\mathcal F_n(u) = i) \, \mathbb P(\mathcal F_n(v) = i | \mathcal F_n(u) = i ) \\ & = \sum_{i = 0}^{n-1} \mathbb P(\mathcal F_n(u) = i) \, \mathbb P(\mathcal F_n(v) = i) \\ & = \sum_{i = 0}^{n-1} \mathbb P(\mathcal F(u) \in E_i ) \, \mathbb P(\mathcal F(v) \in E_i) \\ & = \sum_{i = 0}^{n-1} \frac {|E_i|^2} {n^2\,A^2} \\ & = \frac {n \,A^2} {n^2 \, A^2} \\ & = \frac {1} {n} \\ \end{align*}
4. Oui, la fonction est rapide à calculer et le nombre d’index s’adapte pour les différentes valeur de n.

5. def hashn(k, n) :
       return hash(k) % n
   

6. \(\mathrm O(1)\)
7. \(\mathrm O(|k|)\)

def th_get(assoc, cle, defaut) :
    T, m, n = assoc
    h = hashn(cle,n)
    return lc_get(T[h],cle,defaut)

La complexité de th_get est la plus grande complexité entre le calcul de l’index de la clé, \(\mathrm O(|cle|)\) et la plus grande taille de liste de couple dans le tableau, \(\mathrm O(\max(|T[i]|, 0 \leq i \leq |T|))\). Au pire des cas, c’est toutes les clés du tableau, \(\mathrm O(|T|)\).

1. 1. \(\sum_{i = 0}^{n-1} k_i = m\)
   2. Si deux clés on la même image par \(\mathcal F_n\), i, alors la recherche de ces clé consiste en une recherche linéaire parmi les clés de l’alvéole \(i\) de la table. La complexité est en \(\mathrm O(k_i)\).
   3. D’après l’énoncé, \(p_i = \frac 1 n\) donc \(\mathcal C(\cal T) = \mathrm O (\frac m n)\).
2. On note que \(\mathcal C(\cal T) = \frac m n\) est indépendant de \(\mathcal T\). Donc : \[\cal C(m) = \sum_{ \cal T \in \mathbb T_m} \frac 1 {|\mathbb T_m|} \cal C(\cal T) = \mathrm O (\frac m n \sum_{ \cal T \in \mathbb T_m} \frac 1 {|\mathbb T_m|}) = \mathrm O (\frac m n) \]

On note \(n_m\) le \(n\) utilisé pour une table remplie avec \(m\) éléments. On rappelle que le facteur de remplissage est égal à \(\frac m {n_m}\). Supposons qu’il existe \(\tau\) un réel tel que \(\forall m \in \mathbb N, \frac m {n_m} \leq \tau\) alors \(\cal C(m) = \mathrm O(\frac m {n_m}) = \mathrm O(\tau) = \mathrm O (1)\).