Licence Info
Algorithmique Avancée
TD 6 : ?/11/05
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;


    1. 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?
      Réponse: c+ la somme pour i de 0 à n-1 du nombre d'arbres de taille i.
    2. Modifier le code Exalgo de façon à utiliser cet ordre. On ajoute:
      fonction codetous(ref racine: arbreptr): entier;
      var i,somme:entier;
      début
      somme:=0;
      pour i allant de 0 à taille(racine)-1 par pas de 1 faire
      somme:=somme+T[i]
      finpour;
      retourne somme+code(racine)
      finfonction;

      fonction decodetous(val n,c: entier): arbreptr;
      var i:entier;
      debut
      tant que T[i]<=c faire
      c:=c-T[n];
      n:=n+1
      fintantque;
      retourne decode(n,c)
      finfonction;

  2. Justifier la récurrence donnée dans les transparents de cours pour le nombre d'arbres de taille n avec racine et limitation du nombre de fils d'un noeud à 2: G(n) = G(n-1)
    + sommei=1 n/2 -1 G(i)*G(n-1-i) +
    (si n impair)G((n-1)/2) + (
    G((n-1)/2)
    2
    )
    (à noter: arrondir vers le bas dans la division n/2)
    Réponse:
  3. Dans le cas d'arbres généraux (avec 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.
    Réponse procédures C
  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)
    Réponse: On peut supposer que les n ``objets'' sont les entiers 1 à n; on les ordonne d'abord selon si n est parmi les m choisis ou non et ensuite récursivement; dans le code donné on représente la combinaison avant et après codage/décodage par un tableau T de m+1 entiers où les éléments T[1] à T[m] sont les m choisis rangés en ordre croissant.
    Un programme Exalgo qui contient les fonctions et un petit test:
    programme coeff;

    type vec : tableau 0..20 de entier;
    type tab : tableau 0..20 de vec;

    var binom: tab;
    var T:vec;

    procédure init();
    var i,j:entier;
    debut
    pour i allant de 0 à 20 par pas de 1 faire
    binom[i][0]:=1;
    binom[i][i]:=1;
    pour j allant de 1 à i-1 par pas de 1 faire
    binom[i][j]:=binom[i-1][j-1]+binom[i-1][j]
    finpour
    finpour
    finprocedure;

    fonction coder(ref T:vec; val n,m:entier):entier;
    debut
    selonque
    cas m=0: retourne 0
    cas T[m]=n: retourne coder(T,n-1,m-1)
    autrement: retourne binom[n-1][m-1]+coder(T,n-1,m)
    finselonque
    finfonction;

    procédure decoder(val c:entier; ref T:vec; val n,m:entier);
    début
    printf("decoder(%i,%i,%i)\n",c,n,m);
    si m=0 alors retourne finsi;
    si c<binom[n-1][m-1] alors
    T[m]:=n;
    decoder(c,T,n-1,m-1)
    sinon
    decoder(c-binom[n-1][m-1],T,n-1,m)
    finsi
    finprocedure;

    var i:entier;
    début
    init();
    pour i allant de 0 a binom[8][5]-1 par pas de 1 faire
    decoder(i,T,8,5);
    printf("vérification %i=%i\n",i,coder(T,8,5))
    finpour
    fin.




File translated from TEX by TTH, version 3.05.
On 22 Nov 2005, 17:04.

symboles bricolés pour netscape par sed