Exercice 6 (TP): construction d'un arbre de décision binaire 


__________________________________________________________________________


Le but de cet exercice est d'étudier une variante du jeu du "pendu"


1. Charger la base de noms d'animaux grâce à la commande

exec("animaux.dat");

Ce fichier définir une matrice "noms". Afficher le contenu de la matrice
et calculer le nombre de mots qu'elle contient (valeur à stocker dans la 
variable "n").


2. Le but du jeu est le suivant: vous choisissez le nom d'un animal, 
et le programme doit essayer de le deviner le plus rapidement possible
en posant uniquement des questions de type :

          "Ce mot contient-il la lettre xxxx ?"

où xxxx est remplacé par une des 26 lettres de l'alphabet (on joue sans 
les accents et on interdit les noms composés).

Si le programme est sûr de trouver la solution en au plus p questions, 
quelle est la relation entre n et p ? En déduire une valeur numérique
minimale pour p.


3. Expliquer ce que contient la matrice "mat" après exécution des commandes
scilab suivantes:

mat=zeros(35,n);
for i=1:n
  c = str2code(noms(i));
  mat(c,i) = 1;
end

(on pourra utiliser la commande "help str2code" pour commencer...)


4. Calculer, sous la forme d'un vecteur à 35 colonnes h(i), la proportion
de mots qui contiennent (au moins une fois) la lettre i. Quelle est la
lettre la plus représentée ?


5. Calculer, pour tout i, l'entropie de la partition des mots en deux
ensembles, les mots qui contiennent la lettre i et les autres. Il n'est
pas nécessaire de faire une boucle, une seule formule suffit à partir 
du vecteur h. Pour calculer l'entropie, on utilisera des expressions du 
type log(t^t) plutôt que du type t*log(t) pour contourner le problème de 
la non définition du logarithme en t=0.   


6. En déduire la 1ère question que doit poser le programme pour maximiser 
l'information gagnée en moyenne.
(utiliser la fonction max dans sa syntaxe [m,k] = max(A), voir la doc
avec "help max")

7. Écrire une fonction [A,B,i]=partage(I), qui prend en entrée un
vecteur ligne I de booléens, et qui renvoie l'indice i de la lettre 
associée à la question la plus informative pour le sous-ensemble de 
mots mat(:,I), ainsi que les vecteurs de booléens A et B associés à 
la partition de ce sous-ensemble (réponse oui pour A, non pour B).


8. Expliquer ce qu'affichent les commandes suivantes:

I=([1:n]>0);
[A,B,i]=partage(I);code2str(i),sum(A),sum(B)
[C,D,j]=partage(A);code2str(j),sum(C),sum(D)
[E,F,k]=partage(B);code2str(k),sum(E),sum(F)


9. Utiliser la fonction suivante pour jouer avec l'ordinateur...

function joue()
  printf("\nChoisissez le nom d''un animal...\n\n");
  n = size(mat,'c')
  I = ([1:n]>0)
  while sum(I)>1 do
    [A,B,i]=partage(I)
    printf("Ce mot contient-il la lettre %c ? [o/n] \n",code2str(i))
    c = scanf("%s")
    if c=='o' then I=A, else I=B, end
  end
  printf("L''animal est un(e) %s\n\n",noms(I))
endfunction

joue()


10. Utiliser la fonction suivante pour construire et afficher l'arbre de 
décision optimal associé au jeu:

function arbre(I,str)
  if (sum(I)>1) then
    [A,B,i]=partage(I);
    arbre(A,str+'| ');
    printf("%s%c (%i,%i)\n",str,code2str(i),sum(A),sum(B));
    arbre(B,str+'| ');
  else
    printf("%s -> %s\n",str,noms(I));
  end
endfunction

I=([1:n]>0);
arbre(I,' ')


En modifiant un peu la fonction arbre, calculer 

- la profondeur maximale de l'arbre 

- les mots les plus défavorables (i.e. qui nécessitent le plus grand 
nombre de questions)

- le nombre moyen de questions nécessaires pour trouver la solution 
en suivant cet arbre. A quoi faut-il comparer ce nombre et à quoi est 
due la différence ?