tc_info:td4

Différences

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

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision		 Révision précédente
tc_info:td4 [2019/04/30 13:28] – [Exercice 0] edaucetc_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]]