Différences

Ci-dessous, les différences entre deux révisions de la page.

--- tc_info:td4-2018-2019 [2019/07/31 11:02] – créée edauce
+++ tc_info:td4-2018-2019 [2019/07/31 11:03] (Version actuelle) – edauce
@@ Ligne 1: / Ligne 1: @@
+{{tc_info:td_4-2pages.pdf |Le sujet}}
+===== Partie A =====
+<note tip>
+Soit  $U$  un “univers” dont les éléments sont appelés //clés//. Soit  $E$  un ensemble de clés. On suppose que l'on a une fonction  $h:U\to \{0,\ldots m-1\}$ , dite //fonction de hachage// (ou //hashcode//). Une //table de hachage// est un tableau  $T[0 \ldots m-1]$  tel que  $T[i]$  est une liste  contenant les éléments  $x$  de  $E$  tels que  $h(x)=i$ . Si deux éléments de  $E$  ont le même hashcode, on dit qu'on a //collision//.
+</note>
+==== Exercice 0 ====
+Donnez des algorithmes pour rechercher, insérer & supprimer un élément dans une table de hachage. Donnez leur complexité dans le cas le meilleur, le pire & en moyenne.
+Déduisez-en la valeur optimale (en ordre de grandeur) de  $m$  en fonction de  $n$ , ainsi qu'une contrainte sur la fonction de hachage.
+==== Exercice 1 ====
+On considère les deux fonctions de hachage suivantes :
+  * La //méthode de la division// :  $h(x) = x \: \mathrm{mod}\: m$ .
+  * La //méthode de la multiplication// :  $h(k) = E(m\cdot \mathrm{Frac}(x\cdot A))$ , où :
+    *   $A$  est un nombre de  $[0\ldots1]$
+    *  $E$  est la partie entière & //Frac// la partie fractionnaire  $(\mathrm{Frac}(x)=x-E(x))$
+Donnez, pour ces deux méthodes, des bonnes valeurs pour les paramètres  $m$  &  $A$ .
+==== Exercice 2 ====
+Dans le //hachage cryptographique//,  on veut en plus que, connaissant  $x$  (&  $h(x)$ ), il soit impossible (à moins de ressources en temps de calcul rédhibitoires) de construire  $y\ne x$  tel que  $h(y) = h(x)$ . Donnez des exemples d'applications du hachage cryptographique.
+==== Exercice 3 ====
+Il arrive souvent que l'on ne sache pas à l'avance combien d'éléments contient  $E$  & que l'on mette les éléments de  $E$  dans  $T$  l'un après l'autre sans savoir quand on s'arrêtera.
+Donnez une ``politique" efficace de gestion de la taille de  $T$ .
+==== Exercice 4 ====
+Soit  $S$  un ensemble de nombres à trier, on répartit  $S$  en une table de hachage tel que la fonction de hachage soit croissante ( $x\leq y \Longrightarrow h(x) \leq h(y)$ ). On trie chaque paquet, puis on concatène. On appelle ce tri le //tri par paquets//.
+  * Donnez une fonction de hachage simple & croissante.
+  * Quelle est la complexité de cet algorithme dans le cas le meilleur, le pire & en moyenne.
+===== Partie B =====
+<note tip>
+Un //dictionnaire// est une structure de données (python) qui se présente ainsi~:
+<code>
+D = {clé_1:valeur_1, clé_2:valeur_2, ..., clé_n:valeur_n}
+</code>
+Les clés pouvant être de (presque) n'importe que type (& pas seulement  l'ensemble  $\{0,...,$   $n-1\}$  comme avec une liste).
+  * On accède à ''valeur_i'', la valeur associée à ''clé_i''  par ''D[clé_i]''.
+  * L'opération ''D[clé_p]''  $\gets$  ''D[valeur_p]'',
+    * si ''clé_p'' n'est pas une clé de ''D'', ajoute cette nouvelle clé à ''D'' & lui associe la valeur ''valeur_p''
+    * si ''clé_p'' est déjà une clé de ''D'', elle change la valeur qui lui est associée en ''valeur_p''.
+</note>
+==== Exercice 5 ====
+Donnez une implémentation efficace des dictionnaires. Quelle est alors la complexité (dans le cas le meilleur, le pire & en moyenne) des fonctions de base (recherche, ajout d'un élément,...) sur un dictionnaire.
+==== Exercice 6 ====
+Utilisez un dictionnaire pour écrire un algorithme  qui supprime les doublons d'une liste. Donnez sa complexité (dans le cas le pire, le meilleur & en moyenne).
+==== Exercice 7 ====
+Utilisez un dictionnaire pour écrire un algorithme  qui compte le nombre d'occurrences de chaque mot d'un texte. Donnez sa complexité  (dans le cas le pire, le meilleur & en moyenne).
+===== Partie  C =====
+==== Exercice 8 ====
+** Table d'allocation **
+On considère un tableau  $T$  de taille  $n$  dans lequel
+  *  $p<n$  cases sont occupées. Chaque donnée  $d$  est indexée par l'adresse  $i<n$  donnant sa position dans le tableau & on connaît  sa taille  $m$  ( $d$  occupe  $m$  cases consécutives de  $T$ ).
+  * On suppose de plus
+    * que la //table d'allocation// des différentes cases du tableau est codé au format binaire dans un entier  $B$  de  $n$  bits :
+<code>
+  B=0010010100100...01
+</code>
+    * qu'il existe une fonction  $f(B,i)$  donnant le i $^{eme}$  bit de  $B$  ( $f(B,i)$  vaut 1 si la  i $^{eme}$  case de  $T$  est occupée, & 0 si elle est libre).
+Écrire un algorithme permettant d'insérer une donnée  $d$  dans le premier bloc de  $m$  cases disponible (pensez à mettre à jour la table d'allocation  $B$ ).
+Peut-on faire mieux en appliquant un pré-traitement à  $B$ ~?
+[[tc_info:td7-alt|Ancien sujet]]