Licence Info Algorithmique Avancée TD 6 : novembre 2006

Codage de structures complexes par des entiers

1. Les fonctions code et decode (décrites en cours et données ici en forme Exalgo) effectuent le codage et décodage pour arbres (binaires) d’une taille fixe. Pour traiter tous les arbres binaires jusqu’á la taille max, on peut décider d’ordonner tous ces arbres d’abord par leur taille et ensuite dans l’ordre utilisé dans ces fonctions Exalgo.

fonction code (ref racine: arbreptr): entier;
var i:entier;
var somme:entier;
debut /* code parmi ceux de la meme taille*/
si racine = null alors retourne 0 finsi;
/* compter ceux de la meme taille mais avec un sous-arbre gauche
plus petit*/
somme:=0;
pour i allant de 0 a taille(racine^.gauche)-1 par pas de 1 faire
        somme := somme+T[i]*T[taille(racine)-1-i]
finpour;
/*et enfin ceux avec les memes tailles des deux sous-arbres mais qui
precedent * "racine" dans l'ordre*/
somme := somme+code(racine^.gauche)*T[taille(racine^.droite)];
retourne somme+code(racine^.d)
fin
finfonction;
fonction decode(val n,c: entier): arbreptr;
/* n la taille, c le code*/
var racine: arbreptr;
var i: entier;
debut
i:=-1;
si n=0 alors retourne null finsi;
allouer(racine);
tantque c>=0 faire i:=i+1;c:=c-T[i]*T[n-1-i] fin tantque;
c:=c+T[i]*T[n-1-i]; /*i est la taille du sous-arbre gauche*/
racine^.gauche:=decode(i,c/T[n-1-i]);
racine^.droite=decode(n-1-i,c mod T[n-1-i]);
retourne racine
fin
finfonction;

(a) Quelle est dans cet ordre, parmi tous les arbres de taille 0 à max, la position de l’arbre de taille n et dont le code c parmi les arbres de cette taille a été établi par la fonction code vue en cours?

(b) Modifier le code Exalgo de façon à utiliser cet ordre.

2. Justifier la récurrence donnée dans les transparents de cours (mais pas traitée en cours) pour le nombre d’arbres de taille n avec racine et limitation du nombre de fils d’un noeud à 2, mais sans ordre sur les fils d’un noeud: G(n) = G(n − 1) + somme_{i=1}^{n/2−1}G(i) ∗ G(n − 1 − i) +

(si n impair)G((n − 1)/2) + ( \begin{matrix}G((n − 1)/2) \\ 2 \end{matrix} )

(à noter: arrondir vers le bas dans la division n/2)

3. Dans le cas d’arbres généraux (avec cette fois l’ordre des fils d’un noeud défini), on pourrait les ordonner d’abord par leur taille, ensuite par le nombre de sous-arbres de la racine et enfin par les codes des sous-arbres; donner les algorithmes de codage et décodage dans ce cas.

4. Décrire une méthode de codage et décodage des façons de choisir m objets parmi n. (Toujours avec les codes utilisés constituant une intervalle commençant à 0)