% LaTeX 

%               CORRIGE : INFORMATIQUE  ENS 97                     

%     Par   Daniel GENOUD  - Lyc\'ee La Martini\`ere-Monplaisir  - LYON
%  email :  Daniel_Genoud@lyc-69.ac-lyon.fr     jusqu'en Janvier 98
%   puis :  Daniel_Genoud@ac-lyon.fr  

% Merci de me contacter pour corriger des erreurs possibles
% ou proposer des am\'eliorations.

% Le programme Caml complet se trouve \`a la fin du source TeX

% Il est m\^eme possible d'obtenir le code LaTeX des arbres dessin\'es
% dans la partie III avec la fonction <<dessin_latex>> qui convertit
% les instructions graphiques en des commandes LaTeX \`a r\'ecup\'erer
% en effectuant du copier-coller avec son \'editeur favori.

% Ces commandes sont comprises par LaTeX sous l'environnement "picture"
% \`a condition de rajouter soit-m\^eme l'ent\^ete (voir des exemples plus bas)

% Pour compiler ce fichier, il faut disposer de <<emlines.sty>>

\documentstyle[12pt]{article}

% Mise en page

\voffset=-46truemm
\hoffset=-26truemm   
\textwidth 18.5cm     \columnsep 10pt      \columnseprule 0pt
\textheight = 50\baselineskip \advance\textheight by \topskip
\parindent=0cm

\font\bfsl=cmbxsl10 
\def\Sum{\displaystyle\sum}
\def\Frac{\displaystyle\frac}
\def\flg{\leftarrow}
\begin{document}

\input emlines.sty




\centerline{\fbox{{\bf ~OPTION INFORMATIQUE - ENS 97 : CORRIG\'E~}}}
\bigskip
\bigskip

\def\q#1{\medskip\par\hskip-8mm{\bf Question #1}\par\smallskip}






\centerline{{\bf  Premi\`ere partie : \'epaisseur d'un arbre binaire strict}}

\bigskip

\hskip-8mm\underbar{Remarques sur les arbres binaires stricts}
~(ie ~localement complets) :\par
\smallskip
\hskip-4mm$\star$ dans la d\'efinition de la hauteur d'un arbre binaire donn\'ee
par l'\'enonc\'e \`a la page 4, il ne faut pas compter la feuille.
Ainsi, c'est le nombre maximum d'ar\^etes travers\'ees pour aller
de la racine \`a une feuille.\par


\hskip-4mm$\star$ Ici on ne consid\`ere pas d'arbre vide.\par
La hauteur $h$ d'un arbre binaire strict est donc toujours $\ge1$.\par
La racine est toujours un noeud interne.\par
Le nombre $n_f$ de feuilles est \'egal \`a $n_i+1$ o\`u
$n_i$ d\'esigne le nombre de noeuds internes.\par
\smallskip



\q1

\hskip-4mm$-$ Pour $k=2$, il y a 7 ar\^etes d'\'epaisseur 2 dont
4 issues de noeuds de bi\'epaisseur $(1,2)$,
donc $R_{2,1}=4/7$ et 3 issues de noeuds de
bi\'epaisseur $(1,1)$, donc $R_{2,2}=3/7$.\par
\smallskip
\hskip-4mm$-$ Pour $k=3$, il y a 2 ar\^etes d'\'epaisseur 3 dont
aucune issue de noeuds de bi\'epaisseur $(1,3)$, donc $R_{3,1}=0$,
une issue d'un noeud de bi\'epaisseur $(2,3)$, d'o\`u $R_{3,2}=1/2$
et une  issue d'un noeud de
bi\'epaisseur $(2,2)$, donc $R_{3,3}=1/2$.\par
La matrice de ramification est donc $~\pmatrix{
    1    &   0 &  0  \cr
     4/7   &  3/7  & 0   \cr
      0  & 1/2   &  1/2  \cr}$



\q2
\underbar{La somme des \'el\'ements d'une ligne est toujours \'egale \`a {\bf1}}.\par
\smallskip
En effet, c'est \'evident pour la premi\`ere ligne.\par
Pour $k\ge2$, ~$\Sum_{i=1}^k R_{k,i}=\Frac{1}{N_t(k)}\,
\Big(N_t(k-1,k-1)+\Sum_{i=1}^{k-1}N_t(i,k)\Big)=1$ ~car pour calculer
$N_t(k)$, on effectue le total des noeuds de bi\'epaiseur$(1,k),(2,k),\ldots,(k-1,k)$,
ce qui donne $\Sum_{i=1}^{k-1}N_t(i,k)$ et des $N_t(k-1,k-1)$
noeuds de bi\'epaisseur $(k-1,k-1)$.\par

\q3
Le fait qu'un arbre binaire strict de hauteur $h$ soit {\bf parfait}
 si et seulement si toutes les feuilles sont \`a une hauteur $h$
est ``\'evident".\par
Pour le ``montrer" comme le demande l'\'enonc\'e, on
peut r\'ediger une r\'ecurrence sur $k$ .....\par
\smallskip
Dans un tel arbre, il y a $2^h$ feuilles et $2^h-1$ noeuds internes.\par
\smallskip
On v\'erifie facilement par r\'ecurrence que, dans un arbre parfait,
tous les noeuds ont une bi\'epaisseur de la forme $(k-1,k-1)$
avec $2\le k\le h$ et que l'\'epaisseur de cet arbre est $h+1$.\par
Ainsi $N_t(k)=N_t(k-1,k-1)$ : il en r\'esulte que la matrice de ramification
est la ~\fbox{matrice unit\'e $I_{h+1}$.}


\q4
On v\'erifie facilement par r\'ecurrence que pour un {\bf peigne}
de hauteur $h$ (et qui est de taille $n=h$) :
\par
\qquad - il y a $h$ noeuds internes (avec la racine)\par
\qquad - le noeud interne le plus \'eloign\'e de la racine
a pour bi\'epaisseur $(1,1)$\par
\qquad - les autres noeuds ont pour bi\'epaisseur $(1,2)$.\par
\smallskip
L'\'epaisseur d'un arbre-peigne est donc toujours \'egale \`a $2$.\par
$R_{2,1}=\Frac{h-1}{h}~$ et $~R_{2,2}=\Frac{1}{h}$,
d'o\`u la matrice $~\pmatrix{
    1    &  0  \cr
     (h-1)/h   & 1/h   \cr}$.\par
\smallskip
\underbar{Remarque} : si $h=1$, il s'agit \`a la fois un arbre parfait
 et un peigne, ce qui donne $I_2$ dans les deux cas.\par

\q5
L'\'epaisseur $e$ d'un arbre est $\le h+1$.\par
~Intuitivement :
\par
\hskip-2mm
- plus un arbre de hauteur $h$ est effil\'e, plus son \'epaisseur est petite.\par
\hskip-2mm
- lorsque les coefficients $R_{i,k}$ pour $i=1,2\ldots$ sont non nuls,
alors l'arbre est tr\`es d\'es\'equilibr\'e,
le cas optimum $e=2$ caract\'erisant les arbres dans lesquels chaque noeud interne a
au moins une feuille pour fils ~(cf ~Question {\bf 6}).\par
\smallskip

\hskip-2mm
- au contraire, si l'\'epaisseur $e$ est ``voisine" de $h+1$, alors 
en m\^eme temps la matrice est assez ``creuse" : l'arbre est assez 
\'equilibr\'e, donc touffu,
le cas optimum $e=h+1$ caract\'erisant l'arbre parfait.

\q6
$n$ d\'esigne la {\bf taille} de l'arbre qui repr\'esente dans ce probl\`eme
le nombre de noeuds internes.\par
Quand on remonte l'arbre en partant d'une feuille pour rejoindre la racine,
les ar\^etes parcourues ont une \'epaisseur croissante.\par
L'\'epaisseur d'une ar\^ete qui n'aboutit pas \`a une feuille est au moins
\'egale \`a $2$.\par
Par cons\'equent ~\fbox{$\lambda(n)=2$}~ puique ce minimum est atteint
pour un arbre peigne de hauteur $h=n$.\par
\medskip
Cherchons le nombre $\mu_n$ d'arbres de taille $n$ d'\'epaisseur $2$.\par
$\mu_1=1$ et si $n\ge1$, $\mu_n=2\,\mu_{n-1}$ car les deux fils
de la racine sont une feuille (soit plac\'ee \`a gauche, soit \`a droite)
et un arbre d'\'epaisseur $2$ de taille $n-1$
(soit plac\'e \`a droite, soit \`a gauche).\par
Il y a donc \fbox{$\mu_n=2^{n-1}$} arbres de taille $n$ d'\'epaisseur $2$ :
ce sont tous les arbres {\bf d\'eg\'en\'er\'es} de taille $n$.\par
\underbar{Remarque} : tous ces arbres de formes assez diff\'erentes ont 
cependant la m\^eme matrice de ramification.

\q7
Notons $e$ (au lieu de $h$ comme le propose l'\'enonc\'e) l'\'epaisseur
d'un arbre ($h$ d\'esignant la hauteur).\par

Notons $N_e$ \underbar{l'ensemble des valeurs $n$ possibles} pour la taille d'un arbre
d'\'epaisseur $e\ge2$ et ~$\alpha_e=\min N_e$.\par
\smallskip
On a d\'ej\`a $~N_2=[\![1;\infty[~$ et $\alpha_2=1$ en prenant des arbres d\'eg\'en\'er\'es.\par
\smallskip
Si $e\ge3$ et si {\tt A} est un arbre d'\'epaisseur $e$ de taille $n$,
alors les deux fils {\tt A1} et {\tt A2} de la racine sont des arbres
de taille respective $n_1$ et $n_2$, d'\'epaisseur respective $e_1$ et $e_2$
v\'erifiant :\par
\quad $n=1+n_1+n_2$ et $~e=\cases{e=e_1+1& si $e_1=e_2$ ~ cas (1)\cr
e=\max\{e_1,e_2\}& si $e_1\ne n_2$ ~cas (2)\cr} $\par
\smallskip
Dans le premier cas , ~$n\in 1+N_{e-1}+N_{e-1}$~
et dans le second : $n\in 1+N_e+\displaystyle\bigcup_{k=2}^{e-1}N_k$.\par
\smallskip
Le premier cas permet d'imaginer que l'on a $\,\alpha_e=1+2\,\alpha_{e-1}\,$
(suite arithm\'etico-g\'eom\'etrique) et donc que $\,\alpha_e=2^{e-1}-1\,$
et que toutes les valeurs $n$ sup\'erieures \`a $\alpha_e$ sont possibles.\par
\smallskip
Conjecturons donc que ~\fbox{$N_e=[\![2^{e-1}-1;\infty[$}.
~C'est d\'ej\`a vrai pour $e=2$.\par

D\'emontrons par r\'ecurrence (forte) sur $e$ cette \'egalit\'e
 (par double inclusion).\par
\smallskip

Supposons que $~\forall\, k\in[\![2;e-1]\!],~N_k=[\![2^{k-1}-1;\infty[$.\par

\hskip-3mm$\star$ Tout d'abord si $n\in N_e,$ alors dans le cas (1), $n\ge 1+2\,\alpha_{e-1}=\alpha_e=2^{e-1}$
sinon, dans le cas  (2), $~n > 1+\alpha_e$.
On aboutit donc dans les deux cas \`a $\,n\in[\![\alpha_e;\infty[$.\par
\smallskip
\hskip-3mm$\star$  R\'eciproquement, soit $n$ un entier $\ge\alpha_e=2^{e-1}$.
On cherche \`a d\'ecomposer $n$ par exemple en $n=1+n_1+n_2$ avec $n_1$ et $n_2$ dans $N_{e-1}$
pour se ramener au cas (1) si c'est possible.\par
Prenons $n_1=2^{e-2}-1$ et $n_2=n-n_1-1$. ~Ainsi d\'ej\`a $n_1\in N_{e-1}$.\par
D'autre part, $~n_2\ge(2^{e-1}-1)-(2^{e-2}-1)-1=2^{e-2}-1$, donc $n_2\in N_{e-1}$.\par
Par d\'efinition de $N_{e-1}$, il existe deux arbres {\tt A1} et {\tt A2}
d'\'epaisseur $e-1$ de taille respective $n_1$ et $n_2$.\par
Les deux arbres dont la racine a pour fils {\tt A1} et {\tt A2} ont
pour \'epaisseur $e$ et pour taille $1+n_1+n_2=n$, ce qui prouve que
$n\in N_e$.\par
\smallskip
\underbar{Remarque} : l'arbre de taille minimum d'\'epaisseur $e\ge2$
est l'arbre parfait de hauteur $h=e-1$ dont le nombre de noeuds
internes est $\alpha_e=2^{e-1}-1$.


\newpage
\q8
Une structure de donn\'ees Caml permettant de d\'ecrire les 
arbres ``squelettiques" \'etudi\'es dans cette partie {\bf I} est par exemple :\par
\smallskip
\hskip 1cm\tt 
type arbre\_1 = | F         \hskip5.1cm                   (* Feuille *)\par
\hskip4cm      ~| N of arbre\_1 * arbre\_1 ;;  (* Noeud   *)\par
\rm
\smallskip
Pour impl\'ementer l'exemple donn\'e \`a la figure {\bf5}, on d\'eclare alors :\par
\quad{\tt
let exfig5 = N(N(N(F,F),N(N(N(F,N(F,F)),F),F)),N(F,N(F,F))) ;;}\par

\smallskip
On constate que l'encombrement m\'emoire est \underbar{proportionnel}
au nombre de noeuds.\par
\smallskip
Cela ne d\'epend pas du langage utilis\'e, car on peut obtenir une bijection
entre la repr\'esentation Caml pr\'ec\'edente et un \underbar{codage} sur l'alphabet
form\'e des deux caract\`eres {\tt (} et {\tt )}.\par

\smallskip
$\star$ L'arbre r\'eduit \`a un noeud est cod\'e {\tt ()}.\par
$\star$ Si {\tt u} est le code de {\tt Ag} et {\tt v} celui de {\tt Ad}, alors le code de l'arbre
dont la racine a pour fils gauche {\tt Ag} et pour fils droit {\tt Ag}
est cod\'e par le mot {\tt (uv)}.\par
Ainsi le code de l'arbre de la figure {\bf5} est obtenu \`a partir de la repr\'esentation Caml
en supprimant les lettres {\tt N}, {\tt F} et la virgule, ce qui donne :
{\tt ((()(((()))))(()))}.\par
\smallskip
Inversement, si tout mot ``bien parenth\'es\'e" repr\'esente effectivement un arbre,
(ce qu'on peut montrer par induction structuelle)
son \'ecriture Caml n'est pas imm\'ediate car il faut pouvoir s\'eparer
 l'arbre gauche et l'arbre droit.\par

\q9
~\vskip-13mm~
\begin{verbatim}
 let val i j = if i=j then i+1 else max i j;;
 let rec epaisseur a = match a with
      | F      -> 1
      | N(g,d) -> val (epaisseur g) (epaisseur d) ;;
\end{verbatim}

La fonction {\tt val} co\^ute soit une comparaison et une addition enti\`ere, soit 
deux comparaisons.\par
Le calcul de l'\'epaisseur d'un arbre de taille $n$ s'effectue avec $n$
appels \`a la fonction {\tt val}, d'o\`u un \underbar{co\^ut lin\'eaire}.

\q{10}
On part d'un r\'eel al\'eatoire $x\in${\tt [}$0,1${\tt [}.\par
Consid\'erons la fonction $r1$ d\'efinie sur {\tt [}$0,1${\tt [} par
$r1(x)=\cases{2\,x & si $x<0.5$\cr 2\,x-1& sinon\cr}$\par

On v\'erifie facilement que $r1$ est aussi \`a valeurs dans {\tt [}$0,1${\tt [}.\par
Cette fonction ``d'inspiration dichotomique" permet de construire
une suite $(x_n)$ d\'efinie par $x_0=x$ et $x_{n+1}=r1(x_n)$ \`a laquelle
est associ\'ee une suite bool\'eenne $(b_n)$ d\'efinie par :\par
\hskip3cm $b_n=$ {\tt true} si $x_n<0.5$ ~et~ $b_n= ${\tt false} si $x_n\ge0.5$.\par
\smallskip
Ainsi pour mettre un noeud {\tt N(F,F)} \`a la place d'une feuille {\tt F}
dans un arbre de taille $n-1$ pour obtenir un arbre de taille $n$, on proc\`ede comme suit :
partant de la racine, si $b_0=${\tt true}, alors on continue avec le fils
 gauche, sinon avec le fils droit, puis on recommence en examinant le bool\'een $b_1$
et cela tant que l'on n'a pas atteint une feuille.
\smallskip
La fonction Caml {\tt r1} ci-dessous appliqu\'ee \`a $x_n$ renvoie
le couple $(b_n,x_{n+1})$, ce qui \'evite de faire deux fois le test 
``$x_n<0.5$ ?"

\begin{verbatim}
let r1 x = if x < 0.5 then (false, 2. *. x) else (true,  2. *. x -. 1.0);;
                      
let construit_arbre_1 n = let s = ref(N(F,F)) in
  let rec insere a x  = match a with
        | F -> N(F,F)
        | N(g,d) -> let (test, y) = r1 x in
                         if test then  N(insere g y, d)  else  N(g, insere d y)
  in for i=2 to n do let x= random__float 1.0 in s := insere !s x  done;
     !s;;
\end{verbatim}
\underbar{Complexit\'e} :\par
La complexit\'e $C_k$ pour passer d'un arbre de taille $k-1$ \`a un arbre
de taille $k$ d\'epend de la forme de l'arbre et de sa hauteur $h_{k-1}$.\par
Le pire des cas est un de ceux \'evoqu\'es \`a la question {\bf6} d'un arbre
d\'eg\'en\'er\'e pour lequel $C_k=k-1$.\par
Ainsi dans le pire des cas conduisant \`a un arbre d\'eg\'en\'er\'e de taille $n$,
on a :\par
\hskip 3cm$~C_n=1+2+\cdots+(n-1)=\Frac{n\,(n-1)}{2}$.\par

\smallskip
Un cas int\'eressant (mais est-ce le meilleur ?) est celui qui produit \`a chaque \'etape un arbre \'equilibr\'e
(dans lequel toutes les feuilles sont \`a la hauteur $h-1$ ou $h$) :
on a alors $C_k\equiv_{k\to\infty}\log_2k$, d'o\`u
$~C_n\sim\Sum_{k=2}^n\log_2k\equiv_{n\to\infty}n\,\log_2n$
 ~{\it (en comparant avec une int\'egrale)}.

\q{11}
L'algorithme propos\'e peut-\^etre traduit en Caml de la fa\c{c}on suivante :
\begin{verbatim}
let r2 k = 2 + random__int (k-1);;  (* r\'esultat dans [[2;k]] *)

let rec cree_arbre_1 e =
      if e=2 then N(F,F)
      else let i = r2 e in
           if i < e then let a1 = cree_arbre_1 i 
                         and a2 = cree_arbre_1 e in N(a1,a2)
                    else let  b = cree_arbre_1 (e-1) in N(b,b)
      ;;     
\end{verbatim}
Th\'eoriquement, cet algorithme peut boucler ind\'efiniment du fait de l'appel r\'ecursif avec le m\^eme 
param\`etre $e$ que celui de la fonction initiale.\par
La probabilit\'e $p_n$ d'obtenir la valeur $k$ apr\`es $n$
appels {\tt r2(k)} est \'egale \`a $\Big(\Frac{1}{k-1}\Big)^n$ : elle tend 
donc vers $0$ avec $n$ ( mais sans \^etre \'egale \`a 0).\par
En pratique, l'algorithme s'arr\^ete ``presque toujours", mais peut conduire \`a des arbres de taille
quelconque, parfois tr\'es grande, conform\'ement au r\'esultat de la question {\bf 7}.

\q{12}
Dans ce qui pr\'ec\`ede, on a tenu compte uniquement de l'\'epaisseur $e$
de l'arbre \`a construire sans se pr\'eoccuper de la matrice de ramification
en faisant intervenir une unique fonction {\tt r2}.\par
Si l'on admet qu'on puisse construire des fonctions al\'eatoires 
{\tt r2$_k$} d\'ependant de chaque ligne de la matrice, alors la m\'ethode pr\'ec\'edente
qui est \underbar{probabiliste, donc non d\'eterministe}
conduira \`a l'obtention d'un arbre \underbar{d'\'epaisseur \'egale \`a $e$}, mais
dont la matrice de ramification sera seulement ``voisine" de la matrice donn\'ee \`a l'avance.\par
Les formes arborescentes obtenues seront tr\'es vari\'ees,  ce qui est normal
puisque des arbres de m\^eme \'epaisseur peuvent avoir la m\^eme matrice de
 ramification, ce qui explique qu'on ait recours \`a une m\'ethode al\'eatoire
pour  constuire l'un d'eux, ou du moins un qui s'en rapproche.\par
Cependant les diff\'erentes solutions obtenues en appliquant plusieurs fois de suite cette
m\'ethode pour une matrice de ramification donn\'ee seront toutes plut\^ot
effil\'ees si la matrice est bien remplie inf\'erieurement,
ou toutes plut\^ot touffues si la matrice est creuse.

\bigskip

\hskip-5mm
\underbar{{\bf Compl\'ement}} : 

Le programme suivant (non demand\'e) permet de calculer la matrice de
ramification de n'importe quel arbre binaire strict et de v\'erifier les r\'eponses
des questions {\bf1,~3} et {\bf4}.\par
\sl Les fractions sont repr\'esent\'ees par des couples d'entiers.\par
\rm

\newpage

\begin{verbatim}
let matrice a = 
  let e = epaisseur a in    (* premier parcours n\'ecessaire pour *) 
                            (* initialiser les matrices         *)
  let v = make_vect e 0 and m = make_matrix e e 0 in
     let rec parcours aa = match aa with
        | F        -> 1;
        | N(g,d)   -> let i = parcours g and j = parcours d in
                if i <= j then  m.(i-1).(j-1) <- m.(i-1).(j-1) + 1 
                          else  m.(j-1).(i-1) <- m.(j-1).(i-1) + 1;
                let k = val i j in v.(k-1) <- v.(k-1) + 1;
                k;                             
     in parcours a;
     
     let r = make_matrix e e (0,0) in   
         r.(0).(0) <- (1,1);      (* fractions repr\'esent\'ees par des couples *)
         for k=1 to e-1 do 
            r.(k).(k) <-  (m.(k-1).(k-1) , v.(k));
            for i=0 to k-1 do r.(k).(i) <- if m.(i).(k)= 0 then (0,0)
                                           else (m.(i).(k),v.(k)) done
         done;
         r;;

(* matrice exfig5;;            -->     - : (int * int) vect vect =
 [|[|1, 1; 0, 0; 0, 0|]; [|4, 7; 3, 7; 0, 0|]; [|0, 0; 1, 2; 1, 2|]|] *)

let rec parfait_1 h = if h=1 then N(F,F) else let s = parfait_1 (h-1) in N(s,s);;
  
let rec peigne_1 h = if h=1 then N(F,F) else  N(F, peigne_1 (h-1));;

(* matrice (parfait_1 3) ;;    -->    - : (int * int) vect vect =
 [|[|1, 1; 0, 0; 0, 0; 0, 0|]; [|0, 0; 4, 4; 0, 0; 0, 0|];
   [|0, 0; 0, 0; 2, 2; 0, 0|]; [|0, 0; 0, 0; 0, 0; 1, 1|]|]           *)

(* matrice (peigne_1 5) ;;     -->
- : (int * int) vect vect = [|[|1, 1; 0, 0|]; [|4, 5; 1, 5|]|]        *)
\end{verbatim}
\bigskip
\smallskip

\centerline{{\bf  Deuxi\`eme partie : une application de la notion d'\'epaisseur}}
\par
\bigskip
\rm
Les registres servent d'une part \`a stocker les r\'esultats
de l'\'evaluation de sous-expressions.\par
D'autre part, un terme figurant dans une expression n'est mis dans un registre qu'au moment
pr\'ecis o\`u il intervient dans une op\'eration.\par

\q{13}\begin{tabular}{llllll}
$R_0\flg a~; $& $R_1\flg b~; $& $R_2\flg c~;$ 
&$ R_1\flg R_1-R_2~;$ &  $R_2\flg d~;$ & $ R_3\flg e~;$ \\
$ R_2\flg R_2-R_3~; $&$  R_1\flg R_1*R_2~; $&$ R_0\flg R_0+R_1.$&
\end{tabular}

\smallskip
On a donc utilis\'e 4 registres.
\smallskip
\q{14}\begin{tabular}{llllll}
$R_0\flg e~; $& $R_1\flg d~; $& $R_0\flg R_1-R_0~;$ 
&$ R_1\flg c~;$ &  $R_2\flg b~;$ & $ R_1\flg R_2-R_1~;$ \\
$ R_0\flg R_0*R_1~; $&$  R_1\flg a~; $&$ R_0\flg R_0+R_1.$&
\end{tabular}

\smallskip
On a donc utilis\'e 3 registres.
\smallskip

\q{15} On \'evalue d'abord le 2$^e$ terme en appliquant l'associativit\'e \`a gauche
($*$ et $/$ \'etant de m\^eme priorit\'e).\par

\hskip-4mm
\begin{tabular}{lllllll}
$R_0\flg b~; $& $R_1\flg c~; $& $R_0\flg R_0-R_1~;$ 
&$ R_1\flg d~;$ &  $R_2\flg e~;$ & $ R_1\flg R_1-R_2~;
$ & $ R_0\flg R_1*R_2~;$ \\
$ R_1\flg f~; $&$  R_2\flg g~; $&$ R_1\flg R_1+R_2~;$
&$ R_0\flg R_0/R_1~; $&$  R_1\flg a~;$& $R_0\flg R_0+R_1.$
\end{tabular}

\smallskip
On a donc utilis\'e 3 registres.

\q{16}

\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(113.50,82.00)
\put(50.00,8.00){\circle{7.00}}
\put(70.00,8.00){\circle{7.00}}
\put(90.00,8.00){\circle{7.00}}
\put(110.00,8.00){\circle{7.00}}
\put(57.00,18.00){\framebox(6.00,6.00)[cc]{$-$}}
\put(97.00,18.00){\framebox(6.00,6.00)[cc]{$+$}}
\put(30.00,21.00){\circle{7.00}}
\put(10.00,21.00){\circle{7.00}}
\put(17.00,34.00){\framebox(6.00,6.00)[cc]{$-$}}
\put(77.00,34.00){\framebox(6.00,6.00)[cc]{$/$}}
\put(47.00,55.00){\framebox(6.00,6.00)[cc]{$*$}}
\put(20.00,58.00){\circle{7.00}}
\put(32.00,76.00){\framebox(6.00,6.00)[cc]{$+$}}
\put(38.00,76.00){\vector(2,-3){10.00}}
\put(47.00,55.00){\vector(-3,-2){23.00}}
\put(53.00,55.00){\vector(3,-2){23.00}}
\put(77.00,34.00){\vector(-3,-2){13.00}}
\put(83.00,34.00){\vector(3,-2){13.00}}
\put(97.00,18.00){\vector(-2,-3){4.00}}
\put(103.00,18.00){\vector(1,-2){3.67}}
\put(63.00,18.00){\vector(2,-3){4.00}}
\put(57.00,18.00){\vector(-2,-3){4.00}}
\put(23.00,34.00){\vector(2,-3){6.00}}
\put(17.00,34.00){\vector(-2,-3){6.00}}
\put(20.00,58.00){\makebox(0,0)[cc]{a}}
\put(10.00,21.00){\makebox(0,0)[cc]{b}}
\put(30.00,21.00){\makebox(0,0)[cc]{c}}
\put(50.00,8.00){\makebox(0,0)[cc]{d}}
\put(70.00,8.00){\makebox(0,0)[cc]{e}}
\put(90.00,8.00){\makebox(0,0)[cc]{f}}
\put(110.00,8.00){\makebox(0,0)[cc]{g}}
\put(32.00,76.00){\vector(-2,-3){10}}

\emline{125.00}{7.00}{1}{125.00}{18.00}{2}
\emline{125.00}{18.00}{3}{170.00}{78.00}{4}
\emline{164.00}{70.00}{5}{158.00}{78.00}{6}
\emline{148.00}{48.00}{7}{140.00}{58.00}{8}
\emline{140.00}{58.00}{9}{143.00}{68.00}{10}
\emline{140.00}{58.00}{11}{130.00}{61.00}{12}
\emline{125.00}{18.00}{13}{117.00}{27.00}{14}
\emline{135.00}{31.00}{15}{127.00}{40.00}{16}
\emline{127.00}{40.00}{17}{129.00}{49.00}{18}
\emline{127.00}{40.00}{19}{117.00}{42.00}{20}
\put(158.00,74.00){\makebox(0,0)[cc]{1}}
\put(169.00,74.00){\makebox(0,0)[cc]{1}}
\put(159.00,59.00){\makebox(0,0)[cc]{2}}
\put(142.00,51.00){\makebox(0,0)[cc]{2}}
\put(144.00,62.00){\makebox(0,0)[cc]{1}}
\put(133.00,57.00){\makebox(0,0)[cc]{1}}
\put(143.00,38.00){\makebox(0,0)[cc]{3}}
\put(130.00,43.00){\makebox(0,0)[cc]{1}}
\put(120.00,39.00){\makebox(0,0)[cc]{1}}
\put(129.00,34.00){\makebox(0,0)[cc]{2}}
\put(132.00,24.00){\makebox(0,0)[cc]{3}}
\put(118.00,21.00){\makebox(0,0)[cc]{1}}
\put(128.00,13.00){\makebox(0,0)[cc]{3}}
\end{picture}

\smallskip
\q{17} On peut d\'efinir un type Caml d'expression infix\'ee de la fa\c{c}on suivante :\par
\smallskip
\tt
 type Expression = | Var of char | Oper of Expression * char * Expression ;;\par
\rm
\smallskip
A toute expression $Expr$, on associe un arbre de la fa\c{c}on suivante :\par
\hskip-3mm$\bullet$
 si $Expr$ est une variable, 
alors c'est l'arbre r\'eduit \`a {\tt F}.\par
\hskip-3mm$\bullet$ 
si $Expr$ est de la forme $Expr1* \omega *Expr2$, alors c'est l'arbre
$A=N(A1,A2)$ o\`u $A1$ (resp . $A2$) est l'arbre associ\'e \`a $Expr1$ (resp. $Expr2)$.\par
\smallskip
On peut alors \'etablir par {\bf induction structurelle} que la strat\'egie optimale
d'\'evaluation de $Expr$ utilise un {\bf nombre de registres
\'egal \`a l'\'epaisseur de l'arbre associ\'e.}
\par
\smallskip

\hskip-3mm$\bullet$ 
C'est vrai si $Expr$ est une variable en convenat qu'une feuille est d'\'epaisseur $1$
comme sur les sch\'emas.\par
\smallskip
\hskip-3mm$\bullet$ 
Supposons que $Expr$ est de la forme $Expr1* \omega *Expr2$.\par
Notons $A1$ et $A2$ les arbres associ\'es \`a $Expr1$ et $Expr2$ respectivement,
 $n_1$ et $n_2$ leus \'epaisseurs.\par
L'hypoth\`ese de r\'ecursion est que que $n_1$
(resp. $n_2$) est \'egal au nombre total de registres utilis\'es
(avec la strat\'egie optimale) pour l'\'evaluation de $Expr1$
(resp. $Expr2$).\par
\smallskip
$\star$ si $n_1<n_2$ (n\'ecessairement $n_2\ge2$), alors on commence par \'evaluer $Expr2$,
ce qui utilise $n_2$ registres et on stocke le r\'esultat dans $R_1$.
Puis on \'evalue $Expr1$ \`a l'aide des registres $R_2,\ldots,R_{n_1+1}$, le r\'esultat
\'etant plac\'e dans $R_2$.
\par
Il a donc fallu $\max\{n_2,n_1+1,2\}=n_2$ registes pour \'evaluer $Expr$.\par
Or l'\'epaisseur de l'arbre $A$ associ\'e \`a $Expr$ est aussi dans ce cas $n=n_2$.\par
\smallskip
$\star$ si $n_2<n_1$, r\'esultat analogue en commen\c{c}ant par \'evaluer $Expr1$.\par
\smallskip
$\star$ si $n_1=n_2$,
alors on commence par exemple, comme Caml, par \'evaluer $Expr2$,
ce qui utilise $n_2$ registres et on stocke le r\'esultat dans $R_1$.
Puis on \'evalue $Expr1$ \`a l'aide des registres $R_2,\ldots,R_{n_1+1}$, le r\'esultat
\'etant plac\'e dans $R_2$.
\par
Il a donc fallu $n_1+1$ registes pour \'evaluer $Expr$.\par
Or l'\'epaisseur de l'arbre $A$ associ\'e \`a $Expr$ est aussi dans 
ce cas $n=n_1+1$.\par

  
\bigskip
\hskip-5mm
\underbar{{\bfsl Compl\'ement}} :

Caml \'evaluant les arguments de ces fonctions de droite \`a gauche, il peut
\^etre utile de se ramener \`a un arbre dans lequel chaque fils droit ait une
\'epaiseur sup\'erieure ou \'egale \`a celle de son fils gauche.\par
C'est ce que r\'ealise la fonction ci-dessous :

\begin{verbatim}
let optimise a =
       let rec parcours aa = match aa with
        | F        -> (1,F);
        | N(g,d)   -> let (i,ag) = parcours g and (j,ad) = parcours d in
                       let k = val i j in 
                              if i <= j then (k,N(ag,ad)) else (k,N(ad,ag)) 
     in let (e,a') = parcours a in a'
   ;;

(* optimise exfig5;;         -->          - : arbre_1 =
 N (N (F, N (F, F)), N (N (F, F), N (F, N (F, N (F, N (F, F))))))      *)
\end{verbatim}


\newpage
\centerline{{\bf  Troisi\`eme partie : codages d'arbres binaires}}
\par
\bigskip
\sl Je me demande encore \`a quoi peut bien servir la d\'efinition de mot
\underbar{bien emboit\'e} donn\'e par l'\'enonc\'e, car il ne \underbar{caract\'erise} pas
les codes d'arbres binaires obtenus dans cette partie.\par
Certes, tout code est un mot bien emboit\'e, mais la r\'eciproque est fausse
car, par exemple, {\tt [a][a]} n'est pas le code d'un arbre.\par
Il semble qu'il y ait une erreur d'\'enonc\'e \`a la question $20$
o\`u il fait prendre les $x_i$ dans $\Sigma^+$.
\smallskip
Dans la	 suite, on ne tient pas compte de quel cot\'e de l'axe les branches sont dessin\'ees.
\rm\par

\smallskip
On peut d\'efinir un autre type d'arbre Caml pour \'ecrire les algorithmes
\'etudi\'es dans cette troisi\`eme partie o\`u cette fois un noeud peut \^etre
de degr\'e 0 (``feuille") ou 1 si l'un des fils est ``vide".\par
Le codage d'un tel arbre ne pose pas de probl\`eme, en convenant
que le fils gauche \'eventuel est une branche et que le fils droit
est situ\'e sur l'axe. \par

\begin{verbatim}
type arbre_3 =  | V       (* Vide *)
                | F       (* Feuille *) 
                | N of arbre_3 * arbre_3;;

let rec code_arbre a = match a with
     |     V    -> "" 
     |     F    -> "a"
     | N(V,f2)  ->  "a"  ^ (code_arbre f2)
     | N(f1,f2) ->  "a[" ^ (code_arbre f1) ^ "]" ^ (code_arbre f2)   
  ;;  
\end{verbatim}
             
\q{18}
C'est bien s\^ur ~{\tt aa[aa]aa[a[a]a]a[aaa]aa}.\par
\smallskip
\q{19} Plusieurs r\'eponses sont possibles pour caract\'eriser les branches.\par
\smallskip
\hskip-3mm{\bf 1)} Sachant que {\tt u} repr\'esente le codage de 
l'arbre (donc est correct), quand on extrait un sous-mot
de la forme {\tt [w]}, pour que {\tt w} repr\'esente une branche,
il faut et il suffit que {\tt w} contienne \underbar{autant} 
de crochets droits que de crochets gauches.

\smallskip
\hskip-3mm{\bf2)} Si on veut \^etre plus pr\'ecis 
(ce qui servira pour la question {\bf20}), on peut donner 
la caract\'erisation suivante :\par
$\quad\star$ tout crochet (gauche et droit) figurant dans {\tt w}
est \underbar{pr\'ec\'ed\'e et suivi} d'un {\tt a}.\par
$\quad\star$ 
tout pr\'efixe de {\tt w} contient un nombre de crochets gauches
\underbar{sup\'erieur ou \'egal} \`a celui des crochets\par
\qquad droits.\par
$\quad\star$ {\tt w} contient \underbar{autant} de crochets gauches et droits.
\par
\smallskip
\sl L'int\'er\^et de cette caract\'erisation est de pouvoir servir
\`a l'analyse syntaxique des mots de $\Sigma^*_E$.
\rm
\smallskip
\q{20} Consid\'erons l'\'enonc\'e ${\cal E}_k$ suivant :\par
``Toute branche contenant $k$ noeuds internes admet un codage $ [w]$
qui se d\'ecompose sous la forme :\par
$ [w]=[x_1[\alpha_1]x_2\ldots [\alpha_n]x_{n+1}]$
~o\`u les $x_i\in$\fbox{$\Sigma^+$} et les $[\alpha_i]$ sont eux-m\^emes des 
codages de branches."\par
\smallskip
\underbar{Remarque} : \par
l'unicit\'e d'une telle d\'ecomposition provient de la deuxi\`eme
caract\'erisation donn\'ee \`a la question {\bf19}.\par


\smallskip

Si $k=1$, alors il s'agit d'un arbre parfait de hauteur 1 qui est cod\'e 
: $a[a]a$, donc ${\cal E}_1$ est vrai.\par
\smallskip
Supposons les \'enonc\'es ${\cal E}_1,\ldots,{\cal E}_{k-1}$ vrais.\par
Consid\'erons une branche $b$ ayant $k$ noeuds internes.
~Deux cas se pr\'esentent :\par
\hskip-3mm
$\star$ si la racine de $b$ est un noeud de degr\'e $1$,
alors le fils unique $b_1$ de $b$ est une branche contenant $k-1$
noeuds internes, qui se code en
$[w_1]=[x_1[\alpha_1]\ldots[\alpha_n] x_{n+1}]$, et $b$
admet alors pour codage $[w]=[aw_1]=[ax_1[\alpha_1]\ldots[\alpha_n] x_{n+1}]$.\par
\par
\smallskip
\hskip-3mm
$\star$ si la racine de $b$ est un noeud de degr\'e $2$,
alors chaque fils $b_1$ et $b_2$  de $b$ est une branche contenant 
au plus $k-2$ noeuds internes, l'axe de $b$ contenant par exemple 
 celui de $b_2$.\par
D'apr\`es l'hypoth\`ese de r\'ecurrence, $b_1$ se code 
avec $[w_1]=[x_1[\alpha_1]\ldots[\alpha_p] x_{p+1}]$ et $b_2$ avec \par
$[w_2]=[y_1[\beta_1]\ldots[\beta_q] y_{q+1}]$.\par
Alors $b$ est cod\'e par $[w]=[a[w_1]w_2]=[a[w_1]y_1[\beta_1]\ldots[\beta_q] y_{q+1}]$.\par
\par
\smallskip
\q{21}
Il s'agit des mots commen\c{c}ant par un {\tt a}, se terminant par un {\tt a}
et dans lesquels deux caract\`eres \# sont toujours s\'epar\'es par au moins un {\tt a}.\par
Une expression rationnelle de ce langage est $~a\,(a\,+\,\#a)^*$
et un AFD le reconnaissant est :\par
\bigskip

\unitlength=1mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(75.00,22.00)
\put(33.00,13.00){\circle{6.00}}
\put(65.00,13.00){\circle{6.00}}
\put(24.00,13.00){\vector(1,0){5.00}}
\put(68.00,13.00){\vector(1,0){7.00}}
\put(36.00,15.00){\vector(1,0){26.00}}
\put(62.00,11.00){\vector(-1,0){26.00}}
\put(67.00,15.00){\vector(0,1){5.00}}
\put(67.00,20.00){\vector(-1,0){4.00}}
\put(63.00,20.00){\vector(0,-1){3.00}}
\put(48.00,17.00){\makebox(0,0)[cc]{a}}
\put(65.00,23.00){\makebox(0,0)[cc]{a}}
\put(48.00,8.00){\makebox(0,0)[cc]{\#}}
\end{picture}

~\vskip-13mm~

\q{22}
$w_1=a[a]a$ est le code de l'arbre parfait de hauteur $1$.\par
Si $w_{n-1}$ est le code  de l'arbre parfait de hauteur $n-1$,
alors le code de celui de hauteur $n$ est 
~\fbox{$w_n=a{\tt [}w_{n-1}{\tt ]}w_{n-1}$.}
\smallskip
On v\'erifie facilement par r\'ecurrence que $|w_n|=2^{n+2}-3$.\par
On peut convenir que l'arbre parfait de hauteur 0 (c'est une feuille)
existe est est cod\'e par $a$.\par
\smallskip
Il est facile de programmer le calcul de $w_n$ :\par
\begin{verbatim}
let rec cree_code_parfait n =
  if n=0 then "a"
         else let s = cree_code_parfait (n-1) in "a[" ^ s ^ "]" ^ s
  ;;
\end{verbatim}

Pour tester si un mot $w$ est le codage d'un arbre parfait,
on peut proc\'eder r\'ecursivement de la fa\c{c}on suivante :
\par
- si $|w|=1$, alors $w$ est parfait si et seulement si $w="a"$.\par
- sinon soit $m$ la longueur de $w$. On forme $p=\lfloor (m-3)/2\rfloor$
et on extrait le sous-mot $u$ commen\c{c}ant \`a l'indice 2 et se terminant
\`a l'indice $(p+1)$ et le sous-mot $v$ commen\c{c}ant \`a l'indice $(p+3)$ et se terminant
\`a l'indice $(m-1)$.\par
Alors $w$ est parfait si et seulement si \par
\qquad . $w$ commence par "$a${\tt[}" \par
\qquad . le caract\`ere d'indice $p+2$ est un crochet droit\par
\qquad . les deux sous-mots $u$ et $v$ sont \'egaux \par
\qquad . $v$ est un mot parfait ~~{\it (un seul appel r\'ecursif)}.\par
\smallskip
En voici une impl\'ementation en Caml
 (sans utiliser la fonction {\tt sub\_string}) :
\begin{verbatim}
let test_code_parfait w =
  let rec  egal i  k  p = (p = 0) || (w.[i]=w.[k] && egal (i+1) (k+1) (p-1) )
  in let rec aux i j =
       if i=j then w.[i]=`a`else  let p = (j-i-2) / 2 in
          w.[i]=`a`     &&  w.[i+1]= `[`       && w.[i+p+2]= `]` &&
          p = j-i-p-2   &&  egal (i+2) (i+p+3) p && aux (i+p+3) j  
  in aux 0 (string_length w -1) 
  ;;    
\end{verbatim}

\q{23}
Les codes caract\'erisant les arbres peignes sont les mots de la forme
$a[a]a[a]a\ldots[a]a$, le nombre de couples de crochets \'etant \'egal \`a la hauteur de l'arbre.\par
Une expression rationnelle de ce langage est $a\,({\tt[}a{\tt]}a)^*$
et un AFD le reconnaissant est :.\par
\smallskip

\unitlength=1mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(94.00,35.16)
\put(47.00,9.00){\circle{6.00}}
\put(83.00,9.00){\circle{6.00}}
\put(47.00,32.00){\circle{6.00}}
\put(83.00,32.00){\circle{6.00}}
\put(34.00,32.00){\vector(1,0){9.00}}
\put(86.00,32.00){\vector(1,0){8.00}}
\put(51.00,32.00){\vector(1,0){28.00}}
\put(79.00,9.00){\vector(-1,0){28.00}}
\put(47.00,12.00){\vector(0,1){16.00}}
\put(83.00,28.00){\vector(0,-1){15.00}}
\put(64.00,34.00){\makebox(0,0)[cc]{a}}
\put(64.00,12.00){\makebox(0,0)[cc]{a}}
\put(85.00,22.00){\makebox(0,0)[cc]{{\tt [}}}
\put(49.00,21.00){\makebox(0,0)[cc]{{\tt ]}}}
\end{picture}

~\vskip-17mm~

\q{24}
\sl Les codages de formes arborescentes contenant un nombre variable
de crochets emboit\'es ne sont pas reconnaissables par automate fini.\par
\rm
\smallskip
Un algorithme it\'eratif permettant de dire si un mot $w$ est le code d'une forme arborescente
consiste \`a lire $w$ de gauche \`a droite en v\'erifiant que :\par
- chaque crochet est \underbar{pr\'ec\'ed\'e et suivi} d'au moins un $a$.\par
- tout pr\'efixe de $w$ contient \underbar{au moins autant} de crochets 
gauches que de crochets droits.\par
- $w$ contient \underbar{autant} de crochets 
  gauches que de crochets droits.\par
\smallskip
Dans les deux fonctions Caml qui suivent, l'une it\'erative, l'autre r\'ecursive,
$i$ repr\'esente l'indice courant de parcours dans la cha\^{\i}ne et
$c$  l'exc\'edent de crochets gauches.\par
\underbar{Remarque} : Si l'on attribue les poids $0,~1,~-1$ 
respectivement \`a $a,~{\tt[},~{\tt]}$, alors $c$
est le poids du pr\'efixe de $w$ de longueur $i-1$, ce qui fournit un invariant de boucle.\par


\begin{verbatim}
let test_code_iter w =
    let n = string_length w and i = ref 0 and  c = ref 0 in
    while !i < n-1  do match (w.[!i], w.[!i+1]) with
    
            | `a`,`a`  ->  i:= !i+1
            | `a`,`[`  ->  c := !c+1; i:= !i + 2;
            | `a`,`]`  ->  if !c = 0 then failwith "Il manque un ["
                           else begin c := !c-1; i := !i+2 end
            | `a`,_    ->  failwith "Caract\`ere non autoris\'e "
            |    _     ->  failwith "Il manque un a"
    done;
    if w.[n-1] <> `a` then failwith "Il manque le a final"
                      else !c = 0 ;;                        

let test_code_rec1 w =
  let n = string_length w in
  let rec aux i c =
           (i= n  &&  c=0) 
        || (i=n-1 &&  c=0 &&  w.[i] = `a` )
        || match (w.[i], w.[i+1]) with
               | `a`,`a`  ->  aux (i+1) c
               | `a`,`[`  ->  aux (i+2) (c+1)
               | `a`,`]`  ->  if c=0 then failwith "Il manque un ["
                              else aux (i+2) (c-1)
               | `a`,_    ->  failwith "Caract\`ere non autoris\'e "
               |    _     ->  failwith "Il manque un a"    
  in aux 0 0  ;;
\end{verbatim}

Une autre fa\c{c}on de programmer r\'ecursivement qui \'evite le compteur $c$ 
consiste \`a lire la cha\^{\i}ne de droite \`a gauche.\par
\begin{verbatim}
let test_code_rec2 w =
  let i = ref (string_length w - 1) in
  let rec aux () =
     if !i < 0 then failwith " Incorrect"
     else if !i = 0 then w.[0]=`a` 
          else match (w.[!i-1], w.[!i]) with
                | `a`,`a`  ->  i := !i-1; aux()
                | `]`,`a`  ->  i := !i-2; aux();aux()
                | `[`,`a`  ->  i := !i-2; aux()
                | `_`,`a`  ->  failwith "Caract\`ere non autoris\'e "
                |    _     ->  failwith "Il manque un a"    
  in aux ()
  ;;
\end{verbatim}

En adaptant l'une des fonctions pr\'ec\'edentes, on obtient facilement la forme 
arborescente associ\'ee \`a un mot $w$ (``correct") donn\'e.

\begin{verbatim}
let arbre_du_code w =
  let i = ref (string_length w - 1) in
  let rec aux a2 =
      if !i < 0 then  failwith "Incorrect"
      else if !i = 0 then if w.[0]=`a` then a2
                     else failwith "Erreur"
           else match (w.[!i-1], w.[!i]) with
                | `a`,`a`  ->  i := !i-1;  aux  (N(V,a2))
                | `]`,`a`  ->  i := !i-2; let b=aux F in aux (N(b,a2))
                                  
                | `[`,`a`  ->  i := !i-2; a2
                | `_`,`a`  ->  failwith "Caract\`ere non autoris\'e "
                |    _     ->  failwith "Il manque un a"    
  in aux F 
  ;;
\end{verbatim}
\q{25}
Plusieurs conventions de dessins d'arbres peuvent \^etre choisies,
l'\'enonc\'e n'en ayant fix\'e aucune.\par
Si l'on observe l'exemple propos\'e \`a la figure 10, on remarque 
que les branches sont dispos\'ees alternativement \`a gauche et \`a droite de l'axe.
\par
En outre, dans une branche plac\'ee \`a gauche par exemple, la premi\`ere
sous-branche est elle aussi plac\'ee \`a gauche.\par
Ce sera le r\^ole des bool\'eens {\tt sens} et {\tt first} de permettre
d'appliquer cette convention.\par
\par
Toutes les ar\^etes sont repr\'esent\'ees par des vecteurs de longueurs ``presque \'egales" 
dans $8$ directions (tous les $45^o$) stock\'ees dans un tableau 
{\tt dir} d\'efini en variable globale.\par
\smallskip
La fonction Caml {\tt mod} ne donnant pas le r\'esultat escompt\'e pour les entiers n\'egatifs,
la fonction {\tt modulo} ci-dessous renvoie un reste positif ou nul.

\smallskip
La fonction {\tt dessine} permet de dessiner un arbre,
la racine \'etant plac\'ee en $(x_0,y_0)$ avec le facteur d'\'echelle entier $k$.\par
 
\begin{verbatim}
let dir = [|(0,10);(7;,7);(10,0);(7,-7);
            (0,-10);(-7,-7);(-10,0);(-7,7)|];;

let rec modulo x n = if x >=0 then x mod n else modulo (x+n) n;;

#open "graphics";;
open_graph "";;

let dessine a k x0 y0 =                 (*  k = facteur entier d'\'echelle    *)
  clear_graph();                        (* (x0,y0) = position de la racine  *)
  tortue a x0 y0 0 true true where      (*  celle-ci \'etant plac\'ee en bas    *)
  
   rec tortue aa x y i sens first = match aa with
      |    V     -> ()
      |    F     -> moveto x y ; 
                    let (dx,dy)=dir.(modulo i 8) in lineto (x+k*dx) (y+k*dy)
      | N(f1,f2) -> moveto x y ; 
                     let (dx,dy)=dir.(modulo i 8) in 
                     let x1=x+k*dx and y1=y+k*dy in
                         lineto x1 y1;
                         fill_circle x1 y1 2;
                         tortue f2 x1 y1 i (not sens) true;
                     if first then 
                        if sens then tortue f1 x1 y1 (i-1)  sens  true
                                else tortue f1 x1 y1 (i+1)  sens  true
                                          
                              else
                        if sens then tortue f1 x1 y1 (i+1) (not sens) false
                                else tortue f1 x1 y1 (i-1) (not sens) false
                                           
   ;;  
\end{verbatim}



\unitlength=1mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(100.00,70.00)
\emline{15.00}{10.00}{1}{15.00}{20.00}{2}
\put(15.00,20.00){\circle*{1.00}}
\emline{15.00}{20.00}{3}{15.00}{30.00}{4}
\put(15.00,30.00){\circle*{1.00}}
\emline{15.00}{30.00}{5}{15.00}{40.00}{6}
\put(15.00,40.00){\circle*{1.00}}
\emline{15.00}{40.00}{7}{15.00}{50.00}{8}
\put(15.00,50.00){\circle*{1.00}}
\emline{15.00}{50.00}{9}{15.00}{60.00}{10}
\emline{15.00}{50.00}{11}{22.00}{57.00}{12}
\emline{15.00}{40.00}{13}{8.00}{47.00}{14}
\emline{15.00}{30.00}{15}{22.00}{37.00}{16}
\emline{15.00}{20.00}{17}{8.00}{27.00}{18}
\put(15.00,5.00){\makebox(0,0)[cc]{Peigne : h=4}}

\emline{70.00}{10.00}{1}{70.00}{20.00}{2}
\put(70.00,20.00){\circle*{1.00}}
\emline{70.00}{20.00}{3}{70.00}{30.00}{4}
\put(70.00,30.00){\circle*{1.00}}
\emline{70.00}{30.00}{5}{70.00}{40.00}{6}
\put(70.00,40.00){\circle*{1.00}}
\emline{70.00}{40.00}{7}{70.00}{50.00}{8}
\emline{70.00}{40.00}{9}{63.00}{47.00}{10}
\emline{70.00}{30.00}{11}{77.00}{37.00}{12}
\put(77.00,37.00){\circle*{1.00}}
\emline{77.00}{37.00}{13}{84.00}{44.00}{14}
\emline{77.00}{37.00}{15}{87.00}{37.00}{16}
\emline{70.00}{20.00}{17}{63.00}{27.00}{18}
\put(63.00,27.00){\circle*{1.00}}
\emline{63.00}{27.00}{19}{56.00}{34.00}{20}
\put(56.00,34.00){\circle*{1.00}}
\emline{56.00}{34.00}{21}{49.00}{41.00}{22}
\emline{56.00}{34.00}{23}{56.00}{44.00}{24}
\emline{63.00}{27.00}{25}{53.00}{27.00}{26}
\put(53.00,27.00){\circle*{1.00}}
\emline{53.00}{27.00}{27}{43.00}{27.00}{28}
\emline{53.00}{27.00}{29}{46.00}{20.00}{30}
\put(70.00,5.00){\makebox(0,0)[cc]{Parfait : h=3}}

\emline{140.00}{10.00}{1}{140.00}{20.00}{2}
\put(140.00,20.00){\circle*{1.00}}
\emline{140.00}{20.00}{3}{140.00}{30.00}{4}
\put(140.00,30.00){\circle*{1.00}}
\emline{140.00}{30.00}{5}{140.00}{40.00}{6}
\put(140.00,40.00){\circle*{1.00}}
\emline{140.00}{40.00}{7}{140.00}{50.00}{8}
\put(140.00,50.00){\circle*{1.00}}
\emline{140.00}{50.00}{9}{140.00}{60.00}{10}
\emline{140.00}{50.00}{11}{147.00}{57.00}{12}
\emline{140.00}{40.00}{13}{133.00}{47.00}{14}
\put(133.00,47.00){\circle*{1.00}}
\emline{133.00}{47.00}{15}{126.00}{54.00}{16}
\emline{133.00}{47.00}{17}{123.00}{47.00}{18}
\emline{140.00}{30.00}{19}{147.00}{37.00}{20}
\put(147.00,37.00){\circle*{1.00}}
\emline{147.00}{37.00}{21}{154.00}{44.00}{22}
\put(154.00,44.00){\circle*{1.00}}
\emline{154.00}{44.00}{23}{161.00}{51.00}{24}
\emline{154.00}{44.00}{25}{154.00}{54.00}{26}
\emline{147.00}{37.00}{27}{157.00}{37.00}{28}
\put(157.00,37.00){\circle*{1.00}}
\emline{157.00}{37.00}{29}{167.00}{37.00}{30}
\emline{157.00}{37.00}{31}{164.00}{30.00}{32}
\emline{140.00}{20.00}{33}{133.00}{27.00}{34}
\put(133.00,27.00){\circle*{1.00}}
\emline{133.00}{27.00}{35}{126.00}{34.00}{36}
\put(126.00,34.00){\circle*{1.00}}
\emline{126.00}{34.00}{37}{119.00}{41.00}{38}
\put(119.00,41.00){\circle*{1.00}}
\emline{119.00}{41.00}{39}{112.00}{48.00}{40}
\emline{119.00}{41.00}{41}{109.00}{41.00}{42}
\emline{126.00}{34.00}{43}{126.00}{44.00}{44}
\put(126.00,44.00){\circle*{1.00}}
\emline{126.00}{44.00}{45}{126.00}{54.00}{46}
\emline{126.00}{44.00}{47}{133.00}{51.00}{48}
\emline{133.00}{27.00}{49}{123.00}{27.00}{50}
\put(123.00,27.00){\circle*{1.00}}
\emline{123.00}{27.00}{51}{113.00}{27.00}{52}
\put(113.00,27.00){\circle*{1.00}}
\emline{113.00}{27.00}{53}{103.00}{27.00}{54}
\emline{113.00}{27.00}{55}{106.00}{34.00}{56}
\emline{123.00}{27.00}{57}{116.00}{20.00}{58}
\put(116.00,20.00){\circle*{1.00}}
\emline{116.00}{20.00}{59}{109.00}{13.00}{60}
\emline{116.00}{20.00}{61}{116.00}{10.00}{62}
\put(140.00,5.00){\makebox(0,0)[cc]{Parfait : h=4}}


\end{picture}
\bigskip
\bigskip

$$*+*+*+*+*+*+*+*$$




\end{document}
                                (*  ENS  97  *)
                      
(*******************************   PARTIE I  *******************************)

type arbre_1 = | F                          (* Feuille *)
               | N of arbre_1 * arbre_1 ;;  (* Noeud   *)

let exfig5 = N(N(N(F,F),N(N(N(F,N(F,F)),F),F)),N(F,N(F,F)));;


let r1 x = if x < 0.5 then (false, 2. *. x)
                      else (true,  2. *. x -. 1.0);;
                      
let construit_arbre_1 n =
  let s = ref(N(F,F)) in
  let rec insere a x  = match a with
        | F -> N(F,F)
        | N(g,d) -> let (test, y) = r1 x in
                         if test then  N(insere g y, d) 
                                 else  N(g, insere d y)
  in for i=2 to n do let x= random__float 1.0 in
                  s := insere !s x  done;
     !s;;


let val i j = if i=j then i+1 else max i j;;


let rec epaisseur a = match a with
      | F      -> 1
      | N(F,F) -> 2
      | N(g,d) -> val (epaisseur g) (epaisseur d)
      ;;


let matrice a = 
  let e = epaisseur a in    (* premier parcours ncessaire pour *) 
                            (* initialiser les matrices         *)
  let v = make_vect e 0 and m = make_matrix e e 0 in
     let rec parcours aa = match aa with
        | F        -> 1;
        | N(g,d)   -> let i = parcours g and j = parcours d in
                if i <= j then  m.(i-1).(j-1) <- m.(i-1).(j-1) + 1 
                          else  m.(j-1).(i-1) <- m.(j-1).(i-1) + 1;
                let k = val i j in v.(k-1) <- v.(k-1) + 1;
                k;                             
     in parcours a;
     
     let r = make_matrix e e (0,0) in   
         r.(0).(0) <- (1,1);      (* fractions reprsentes par des couples *)
         for k=1 to e-1 do 
            r.(k).(k) <-  (m.(k-1).(k-1) , v.(k));
            for i=0 to k-1 do r.(k).(i) <- if m.(i).(k)= 0 then (0,0)
                                           else (m.(i).(k),v.(k)) done
         done;
         r;;

let rec parfait_1 h = if h=1 then N(F,F) 
                             else let s = parfait_1 (h-1) in N(s,s);;
  
let rec peigne_1 h = if h=1 then N(F,F) else  N(F, peigne_1 (h-1));;

let r2 k = 2 + random__int (k-1);;  (* rsultat dans [[2;k]] *)

let rec cree_arbre_1 e =
      if e=2 then N(F,F)
      else let i = r2 e in
           if i < e then let a1 = cree_arbre_1 i 
                         and a2 = cree_arbre_1 e in N(a1,a2)
                    else let  b = cree_arbre_1 (e-1) in N(b,b)
      ;;     
      

(******************************   PARTIE II   ******************************)


let optimise a =
       let rec parcours aa = match aa with
        | F        -> (1,F);
        | N(g,d)   -> let (i,ag) = parcours g and (j,ad) = parcours d in
                       let k = val i j in 
                              if i <= j then (k,N(ag,ad)) else (k,N(ad,ag)) 
     in let (e,a') = parcours a in a'
   ;;


     
(******************************   PARTIE III  ******************************)


type arbre_3 =  | V                          (* Vide    *)
                | F                          (* Feuille *)
                | N of arbre_3 * arbre_3;;   (* Noeud   *)
             
let rec cree_arbre_3 n =
  let s = ref(V) in
  let rec insere aa  = match aa with
        |       V  -> F
        |       F  -> N(V,F)
        | N(f1,f2) -> if random__int 2 = 0 then N(insere f1, f2)
                                           else N(f1, insere f2) 
  in for i=1 to n do s := insere !s done;
  !s;; 
 
let rec parfait_3 h = if h=0 then F else let s = parfait_3 (h-1) in N(s,s);;
  
let rec peigne_3 h  = if h=0 then F else  N(F, peigne_3 (h-1));;

let rec code_arbre a = match a with
     |     V    -> "" 
     |     F    -> "a"
     | N(V,f2)  ->  "a"  ^ (code_arbre f2)
     | N(f1,f2) ->  "a[" ^ (code_arbre f1) ^ "]" ^ (code_arbre f2)   
  ;;  
  

let rec cree_code_parfait n =
  if n=0 then "a"
         else let s = cree_code_parfait (n-1) in "a[" ^ s ^ "]" ^ s
  ;;

let test_code_parfait w =
  let rec  egal i  k  p = (p = 0) || (w.[i]=w.[k] && egal (i+1) (k+1) (p-1) )
  in let rec aux i j =
       if i=j then w.[i]=`a`else  let p = (j-i-2) / 2 in
          w.[i]=`a`     &&  w.[i+1]= `[`       && w.[i+p+2]= `]` &&
          p = j-i-p-2   &&  egal (i+2) (i+p+3) p && aux (i+p+3) j  
  in aux 0 (string_length w -1) 
  ;;    
 
 
let test_code_iter w =
    let n = string_length w and i = ref 0 and  c = ref 0 in
    while !i < n-1  do match (w.[!i], w.[!i+1]) with
    
            | `a`,`a`  ->  i:= !i+1
            | `a`,`[`  ->  c := !c+1; i:= !i + 2;
            | `a`,`]`  ->  if !c = 0 then failwith "Il manque un ["
                           else begin c := !c-1; i := !i+2 end
            | `a`,_    ->  failwith "Caractre non autoris "
            |    _     ->  failwith "Il manque un a"
    done;
    if w.[n-1] <> `a` then failwith "Il manque le a final"
                      else !c = 0 ;;                        

let test_code_rec1 w =
  let n = string_length w in
  let rec aux i c =
           (i= n  &&  c=0) 
        || (i=n-1 &&  c=0 &&  w.[i] = `a` )
        || match (w.[i], w.[i+1]) with
               | `a`,`a`  ->  aux (i+1) c
               | `a`,`[`  ->  aux (i+2) (c+1)
               | `a`,`]`  ->  if c=0 then failwith "Il manque un ["
                              else aux (i+2) (c-1)
               | `a`,_    ->  failwith "Caractre non autoris "
               |    _     ->  failwith "Il manque un a"    
  in aux 0 0
  ;;


let test_code_rec2 w =
  let i = ref (string_length w - 1) in
  let rec aux () =
     if !i < 0 then failwith " Incorrect"
     else if !i = 0 then w.[0]=`a` 
          else match (w.[!i-1], w.[!i]) with
                | `a`,`a`  ->  i := !i-1; aux()
                | `]`,`a`  ->  i := !i-2; aux();aux()
                | `[`,`a`  ->  i := !i-2; aux()
                | `_`,`a`  ->  failwith "Caractre non autoris "
                |    _     ->  failwith "Il manque un a"    
  in aux ()
  ;;



let arbre_du_code w =
  let i = ref (string_length w - 1) in
  let rec aux a2 =
      if !i < 0 then  failwith "Incorrect"
      else if !i = 0 then if w.[0]=`a` then a2
                     else failwith "Erreur"
           else match (w.[!i-1], w.[!i]) with
                | `a`,`a`  ->  i := !i-1;  aux  (N(V,a2))
                | `]`,`a`  ->  i := !i-2; let b=aux F in aux (N(b,a2))
                                  
                | `[`,`a`  ->  i := !i-2; a2
                | `_`,`a`  ->  failwith "Caractre non autoris "
                |    _     ->  failwith "Il manque un a"    
  in aux F 
  ;;
  
  

let dir = [|(0,10);(7;,7);(10,0);(7,-7);
            (0,-10);(-7,-7);(-10,0);(-7,7)|];;

let rec modulo x n = if x >=0 then x mod n else modulo (x+n) n;;

#open "graphics";;
open_graph "";;


let dessine a k x0 y0 =                 (*  k = facteur entier d'chelle    *)
  clear_graph();                        (*  (x0,y0) = position de la racine *)
  tortue a x0 y0 0 true true where      (*  celle-ci tant place en bas    *)
  
   rec tortue aa x y i sens first = match aa with
      |    V     -> ()
      |    F     -> moveto x y ; 
                    let (dx,dy)=dir.(modulo i 8) in lineto (x+k*dx) (y+k*dy)
      | N(f1,f2) -> moveto x y ; 
                     let (dx,dy)=dir.(modulo i 8) in 
                     let x1=x+k*dx and y1=y+k*dy in
                         lineto x1 y1;
                         fill_circle x1 y1 2;
                         tortue f2 x1 y1 i (not sens) true;
                     if first then 
                        if sens then tortue f1 x1 y1 (i-1)  sens  true
                                else tortue f1 x1 y1 (i+1)  sens  true
                                          
                              else
                        if sens then tortue f1 x1 y1 (i+1) (not sens) false
                                else tortue f1 x1 y1 (i-1) (not sens) false
                                           
   ;;  

(* La fonction ci-dessous cre les instructions graphiques pour 
   les incorporer dans un fichier LaTeX sous l'environnement picture.
   Il restera  complter l'entte avec les paramtres voulus
   et le \end{picture} final.                                             *)


let dessin_latex a k x0 y0= 
  let p=ref 1 in
  let print_line x y x1 y1 =
           print_newline();
           print_string "\emline{";
           print_int x;  print_string ".00}{";
           print_int y;  print_string ".00}{";
           print_int !p; print_string "}{";
           print_int x1; print_string ".00}{";
           print_int y1; print_string ".00}{";
           print_int (!p+1); print_string "}"; p:= !p+2   
  in let print_circle x y  =
           print_newline();
           print_string "\put(";
           print_int x; print_string ".00,";
           print_int y; print_string ".00){\circle*{1.00}}"
  
  in let  rec tortue aa x y i sens first = match aa with
      |    V     -> ()
      |    F     -> let (dx,dy)=dir.(modulo i 8) in 
                            print_line x y (x+k*dx) (y+k*dy)
      | N(f1,f2) -> let (dx,dy)=dir.(modulo i 8) in 
                     let x1=x+k*dx and y1=y+k*dy in
                         print_line x y x1 y1;
                         print_circle x1 y1 ;
                         tortue f2 x1 y1 i (not sens) true;
                     if first then 
                        if sens then tortue f1 x1 y1 (i-1)  sens  true
                                else tortue f1 x1 y1 (i+1)  sens  true
                                          
                              else
                        if sens then tortue f1 x1 y1 (i+1) (not sens) false
                                else tortue f1 x1 y1 (i-1) (not sens) false
                                           
   in tortue a x0 y0 0 true true ;
   print_newline ()
  ;;  

dessin_latex (peigne_3 4) 1 15 10;;

dessin_latex (parfait_3 3) 1 70 10;;

dessin_latex (parfait_3 4) 1 140 10;;


(*                              FIN                                  *)
