Différences

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

--- tc_info:td4 [2019/04/30 14:01] – [Partie B] edauce
+++ tc_info:td4 [2019/07/31 10:51] (Version actuelle) – edauce
@@ Ligne 1: / Ligne 1: @@
+{{tc_info:td_4-2pages.pdf |Le sujet}}
+===== Partie A =====
+===== 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]]