Différences

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

--- tc_info:td4 [2019/04/30 13:30] – [Exercice 4] 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]]