%  Corrig\'e de l'\'epreuve d'Informatique de l'ESIM pos\'ee en 2000
%  en langage Caml

% par Daniel GENOUD - Lyc\'ee La Martini\`ere-Monplaisir - LYON
% email : Daniel.Genoud@ac-lyon.fr

% LaTeX 2.09


\documentstyle[a4]{article}

\input upsnum.sty
\input emlines.sty
\voffset=-38truemm 
\hoffset=-15truemm   
\textwidth 16cm        \columnsep 10pt          \columnseprule 0pt
\textheight = 56\baselineskip \advance\textheight by \topskip



% Num\'erotation ups

\parindent=0pt

\def\num#1{\medskip \hskip-6mm{{\bf #1})~}}


\begin{document}

\centerline{\fbox{{\bf 
CORRIG\'E DE L'\'EPREUVE D'INFORMATIQUE DE L'ESIM - 2000}}}

\bigskip


\centerline{\underbar{Programmation en Caml}}

\bigskip
\bigskip

\hskip-1cm
{\large\bf Partie I - Parcours en escalier dans un tableau}
\bigskip

\num 1
On remplit d'abord la premi\`ere colonne avec les puissances de 2.

On d\'eduit ensuite chaque colonne de la pr\'ec\'edente en la multipliant par 3.

\begin{verbatim}
 let remplir n =
   let m= make_matrix (n+1) (n+1) 1 in   
            (* m.(0).(0) est initialise' a` 1 *)
  
            (* premie`re colonne *)
   for i=1 to n do m.(i).(0) <- 2 * m.(i-1).(0) done; 
 
            (* colonnes suivantes *)
   for j=1 to n do
         for i=0 to n do m.(i).(j) <- 3 * m.(i).(j-1) done done;
   m;;
\end{verbatim} 



\num 2 Le nombre de multiplications est \'egal \`a
 $~(n+1)^2-1=\,\underline{n^2+2\,n}$.

\num 3
On utilise la r\`egle donnant le PGCD lorsque les deux nombres sont factoris\'es en produit de nombres premiers.

\begin{verbatim}
 let pgcd m i j k l =
    let p = min i k and q = min j l in m.(p).(q);;
   
\end{verbatim} 

\num 4 
On cherche le plus grand \'el\'ement inf\'erieur ou \'egal \`a $p$
sur chaque ligne (s'il existe).

Sur la ligne d'indice 0, on part de la droite, 
jusqu\`a trouver un \'el\'ement $m_{0,j_0}\le p$.

A l'entr\'ee de la premi\`ere boucle et \`a la sortie de chaque boucle index\'ee par $i_0$,
$~(i,j)$ est la position du plus grand des \'el\'ements $\le p$
situ\'es sur les lignes d'indice allant de 0 \`a $i_0$
(invariant de boucle).

Quand on passe de $(i_0,j_0)$ \`a $(i_0+1,j_0-1)$,
il est inutile de de comparer $m_{i_0+1,j_0-1}$
\`a $m_{i,j}$ :

en effet  $m_{i_0+1,j_0-1}=\displaystyle \frac{2}{3}\,m_{i_0,j_0}\le
\frac{2}{3}\,m_{i,j} < m_{i,j}$, ce qui \'economise un test.

Lorsqu'on est dans  la colonne d'indice $0$
et que l'\'etape suivante conduit \`a $j=-1$, il n'y a alors
plus rien faire dans les lignes suivantes.



\begin{verbatim}
 let pgm m p =
       let n =(vect_length m) -1 in
       let i = ref(0) and j = ref(n) and j0 = ref(n) in
       while m.(0).(!j0) > p do j0 := !j0 - 1 done;
       j := !j0;                  (* ligne d'indice 0 *)

       for i0=1 to n do           (* lignes suivantes *)
          if !j0 >= 0  && m.(i0).(!j0) > p  
          then  j0 := !j0 -1      (* pas de mise a` jour de i et j *)
          else if !j0 >= 0 &&  m.(!i).(!j) < m.(i0).(!j0) then
              begin i := i0; j := !j0 end   
       done;
       (!i, !j,  m.(!i).(!j)) ;;  
\end{verbatim}

\smallskip
\num 5 Appelons curseur le couple $(i_0,j_0)$ : celui-ci
a trois sortes de d\'eplacements possibles :
\smallskip


\centerline{$\longleftarrow$ sur la premi\`ere ligne d'indice 0,
~~ $\swarrow~$ ou $~\downarrow~$ ensuite.}

\smallskip

Le d\'eplacement vertical utilise deux comparaisons, les deux autres une seule.
\smallskip

\hskip-2mm
- S'il n'y a pas de d\'eplacement horizontal sur la premi\`ere ligne,
alors \`a chaque boucle on descend si possible d'une ligne, ce qui 
donne au plus $2\,n$ comparaisons
~(majorant  atteint lorsque $p=m_{n,n}$).

\smallskip
\hskip-2mm 
- S'il n'y a eu d'abord $p$  d\'eplacements horizontaux
 sur la premi\`ere ligne, alors ensuite, chaque d\'eplacement vertical
du curseur est automatiquement suivi d'un d\'eplacement oblique car :


\centerline{si $~m_{i_0,j_0}\le p$ ~et $~m_{i_0,j_0+1}> p~$ et
$~m_{i_0+1,j_0}\le p$,
~alors $~m_{i_0+2,j_0}=4\,m_{i_0,j_0} > 3\,m_{i_0,j_0}=m_{i_0,j_0+1}>p$.}

Il y a donc au plus $n-p$ d\'eplacements obliques et
$\big\lceil\displaystyle \frac{n-p}{2}\big\rceil$
d\'eplacements verticaux du curseur,
d'o\`u un nombre de comparaisons major\'e par :
~$p + (n-p) + 2\,\big\lceil\displaystyle \frac{n-p}{2}\big\rceil=
n+(n-p+1)\le 2\,n$ ~car $p\le1$.


\medskip


Au total, il y a \underline{au plus $2\,n$ comparaisons}
 mettant en jeu un \'el\'ement de la matrice $M$.

\bigskip
\bigskip
     
\hskip-1cm
{\large\bf Partie II - Codage de mots en partie commune }

  
\begin{verbatim}
let creer_branche m = 
   let n = string_length m in
   let rec aux i = 
   (* i est un indice de position, ce qui evite de couper m *)
         if i = n then noeud(`.`,nil,nil)
         else noeud(m.[i],aux (i+1),nil)
   in aux 0 ;;      
               
let etete m =    (* suppression du premier caracte`re d'une chaine *)
     sub_string  m 1 (string_length m - 1) ;;
 
let rec placer m a = 
   if m="" then a 
   else match a with
         |         nil  -> creer_branche m
         | noeud(c,g,d) -> if c = m.[0]  
                           then noeud(c,placer (etete m) g, d)
                           else noeud(c, g, placer m d) ;;              

let rec inserer m a = 
   if m="" then a 
   else match a with
       |         nil  -> creer_branche m
       | noeud(c,g,d) -> if c = m.[0]  
                         then noeud(c,inserer(etete m) g, d)
                         else if c < m.[0]
                              then noeud(c, g, inserer m d)
                              else noeud(m.[0], creer_branche(etete m), a) ;; 
           (* on tient compte cette fois de l'ordre alphabe'tique *)

let affiche a =    
    let rec parcours  aa accu = match aa with 
         |          nil -> ()
         | noeud(c,g,d) -> if c=`.` 

             (* accu contient le mot lu sur le chemin allant
                de la racine au noeud actuellement visit\'e *)
              
                    then begin 
                           print_string accu; 
                           print_newline(); parcours d accu 
                         end
                    else begin
                           parcours g (accu^(string_of_char c));    
                           parcours d accu
                         end
    in parcours a "";;                            
   
 let present m a =    
    let rec parcours  aa accu = match aa with 
        |          nil -> false
        | noeud(c,g,d) -> 
           if c=`.`            
           then m=accu || parcours d accu                           
           else parcours g (accu^(string_of_char c)) || parcours d accu
     in parcours a "";;                            
    
let saisir () = 
   let mot = ref ("") in
      while !mot <> "fin" do 
          mot := read_line();
          if !mot <> "fin" then dico := inserer !mot !dico 
      done ;;
\end{verbatim}                        

 \bigskip
\bigskip
     
\hskip-1cm
{\large\bf Partie III - Expressions pr\'efix\'ees bien form\'ees}
\bigskip
  
\num{1}   Tout mot bien form\'e $u=(u_1,\ldots, u_n)$ est \underbar{de longueur impaire}          
car n\'ecessairement $u_n=-1$ et $\displaystyle \sum_{i=1}^{n-1}u_i=0$,

 ce qui montre que le
pr\'efixe $u'=(u_1,\ldots, u_{n-1})$ contient autant de $-1$ que de 1,
donc $n-1$ est pair.

\num 2
V\'erifions que $w$ satisfait \`a la CNS {\bf (1)}.

\hskip-2mm.
La somme des \'el\'ements de $w$ est \'egale \`a
$~1+\displaystyle\sum_{i=1}^nu_i+\sum_{j=1}^mv_j=1-1-1=-1$.

\hskip-2mm.
Montrons que $~\forall\,k\in[\![1,m+n]\!],~W_k=
\displaystyle\sum_{i=1}^k w_i\ge 0$ :

\quad- c'est \'evident si $k=1$ ~car $~W_1=w_1=1$.

\quad- c'est vrai si $1\le k\le n$ ~car $~W_k=1+
\displaystyle\sum_{i=1}^{k-1}u_i\ge1+0=1.$

\quad- c'est vrai si $ k= n+1$ ~car $~W_{n+1}=1+
\displaystyle\sum_{i=1}^{n}u_i=1-1=0$.

\quad- c'est vrai si $n+2\le k\le n+m$ ~car $~W_k=
W_{n+1}+\displaystyle\sum_{i=n+2}^{k}w_i=\sum_{j=1}^{k-n-1}v_j\ge0~$
puisque $1\le k-n+1\le m-1$.

\num 3
\underbar{R\'eciproque}
Puisque $w$ est bien form\'e de longueur $n>1$,
n\'ecessairement $\,n\ge 3,~w_1=1,~w_n=-1\,$ et $\,W_{n-1}=0$.

\smallskip
\underbar{Forme n\'ecessaire de $\ell$} ~(unicit\'e).

L'\'etude faite au {\bf 2)} montre que d'une part
 $~W_{\ell+1}=\displaystyle \sum_{i=1}^{\ell+1} w_i=0~$
et d'autre part que
 $~\forall\,k\in[\![1;\ell]\!],~
W_{k+1}=\displaystyle \sum_{i=1}^{k+1} w_i\ge1$.

Ainsi l'indice $p=\ell+1$
est n\'ecessairement \'egal \`a
$\,{\rm Min}\big\{k\in[\![2,n-1]\!]~/~W_k=0\big\}$.

\smallskip

\underbar{Synth\`ese} ~(existence).

Comme $W_{n-1}=0$, on peut consid\'erer 
$\,p={\rm Min}\{k\in[\![2,n-1]\!]~/~W_k=0\}$.

Posons  $~\ell=p-1,~~u=(w_2,\ldots,w_p)$ ~et~ 
$v=(w_ {p+1},\ldots,w_n)$. ~(Remarque : $|u|\ge1$ et $|v|\ge1$).

\quad . \underline{$u$ est bien form\'e} car $~\forall\, k\in[\![2;p-2]\!],
~\displaystyle\sum_{i=2}^k w_i=W_k-W_1\ge 1-1=0~$ car $W_k\ge1$ (puisque $k<p$)
et $\displaystyle\sum_{i=2}^pw_i=W_p-W_1\ge 0-1=-1$.


\quad . \underline{$v$ est bien form\'e} car $~\forall\, k\in[\![p+1;n-1]\!],
~\displaystyle\sum_{i=p+1}^k w_i=W_k-W_p=W_k\ge0~$ 
et $\displaystyle\sum_{i=p-1}^nw_i=W_n-W_p=-1+0=-1$.


\num{4-5-6-7}
\begin{verbatim}
let est_bien_forme u =
    let n = u.(0) and i = ref (1) and s = ref (0)  in
    while (!s >=0) && (!i <= n) do
      s := !s + u.(!i);
      i := !i + 1;
    done;
    (!i > n) && (!s = -1) ;;
  
let construire u v =
    let m =  u.(0) and n = v.(0) in
    let w = make_vect (m+n+2) 1 in
      w.(0) <- m+n+1;
      for i = 1 to m do w.(i+1)   <- u.(i) done;
      for j = 1 to n do w.(j+m+1) <- v.(j) done;
      w;;
    
let fusion l1 l2 = 
    let rec aux  u ll = match ll with 
       |   []  -> []
       | v::q  -> (construire u v)::(aux u q) in
    let rec parcours liste = match liste with
       |   []  -> []
       | u::q  -> (aux u l2)@(parcours q) in
    parcours l1;; 

  let enumere p = 
    let t = make_vect (p+1) [] in
    t.(0) <- [[|1;-1|]];
    for k=1 to p do
      for i=0 to k-1 do t.(k) <- t.(k)@fusion (t.(i)) (t.(k-1-i))
      done
    done;
    t;;  
\end{verbatim}      

Notons $F$ l'ensemble des mots bien form\'es.

La question {\bf 2)} a montr\'e que si $u\in F$ et $v\in F$, alors
$w=1uv\in F$.

La question {\bf 3)} a montr\'e que si $w\in F$ et $|w|>1$,
alors $u$ se d\'ecompose de fa\c con unique en $w=1uv$
avec $u\in F$ et $v\in F$.

Ainsi on obtient une liste de tous les mots de $F$ de longueur $2k+1$
en r\'eunissant les listes r\'esultat  de la ``fusion"
d'une liste des mots de longeur $2*i+1$ et d'une 
liste des mots de longeur $2*j+1$ pour tous les couples $(i,j)$
d'entiers $\ge 0$ tels que $i+j=k-1$, ce que 
r\'ealise la fonction {\tt enumere}.

\num 8
Soit $u=(u_1,\ldots,u_n)$ de sorte que $~\displaystyle\sum_{j=1}^nu_j=-1$.
~Notons $~U_k=\displaystyle\sum_{j=1}^ku_j$.

\smallskip
\underbar{Forme n\'ecessaire de $i$} (unicit\'e)

Supposons $(u_{i+1},\ldots,u_n,u_1,\ldots,u_i)$ bien form\'e.

$\forall\, k\in[\![1;i-1]\!],~0\le \displaystyle\sum_{j=i+1}^nu_j+U_k
=U_n-U_i+U_k=-1+U_k-U_i$,
~donc $\,U_i<U_k$.

$\forall\, k\in[\![i+1;n]\!],~0\le \displaystyle\sum_{j=i+1}^ku_j
=U_k-U_i$, ~donc $\,U_i\le U_k$.

Ainsi $~i={\rm Min}\{k\in[\![1,n]~/~U_k$ est minimum$\,\}$.

\smallskip
\underbar{Synth\`ese} (existence)

Posons $~i={\rm Min}\{k\in[\![1,n]~/~U_k$ est minimum$\,\}$
~et v\'erifions que $v=(u_{i+1},\ldots,u_n,u_1,\ldots,u_i)$ est bien form\'e.
\smallskip

\quad . Si $i+1\le k\le n$, alors $\displaystyle\sum_{j=i+1}^ku_j=
U_k-U_i\ge0$.

\quad . Si $1\le k\le i$, alors $\displaystyle\sum_{j=i+1}^nu_j+
\sum_{j=1}^ku_j=U_n-U_i+U_k=U_k-U_i-1\ge 1-1=0$
~car $U_k-U_i\ge 0$ et $U_k\ne U_i$ par d\'efinition de $i$ puisque $k<i$.

\quad . $\displaystyle\sum_{j=1}^nv_j=\sum_{j=1}^nu_j=-1$.

    
\num 9
Le nombre de fa\c cons de placer les $k$ symboles {\bf 1}
dans une suite de $2k+1$ \'el\'ements est \'egal \`a $C_{2k+1}^k$.


Parmi les $2k+1$ mots se d\'eduisant par permutation circulaire,
il y en a un et un seul qui est bien form\'e.

Ainsi ~\fbox{ $C_k=\displaystyle \frac{C_{2k+1}^k}{2k+1}$ }

\smallskip

Cela donne notamment $C_1=1,~C_2=2,~C_3=5$.

\smallskip

\underbar{Remarque} : $C_k$ est le nombre (dit de Catalan)
d'arbres binaires localement complets ayant $k$ noeuds internes et $k+1$ feuilles,
ce qui est normal car \`a tout mot bien form\'e est associ\'e un tel arbre et 
r\'eciproquement.

\bigskip
\bigskip

\centerline{$*$ ~FIN~ $*$}



\end{document} 



          