%  Corrig\'e de l'\'epreuve d'Informatique de l'ESIM pos\'ee en 1999
%  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}

% Num\'erotation ups
\input upsnum.sty

\parindent=0pt

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


\begin{document}

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

\smallskip

\centerline{\underbar{Programmation en Caml}}

\bigskip
\bigskip

\hskip-1cm
{\bf Partie I - Enum\'erations d'ensembles }

\smallskip
Cette partie ne comporte que des questions de programmation.

\begin{verbatim}
                     (* Utilitaires demandes *)

let prem ens = match ens with 
      |  []   -> failwith "Erreur dans prem"
      | t::q  -> t ;;
 
let sp ens = match ens with 
      |  []   -> failwith "Erreur dans sp"
      | t::q  -> q ;;
      
let rec siem  i ens =  match ens with
      |  []   -> failwith "Erreur"
      | t::q  -> if i=1 then q else t::(siem (i-1) q) ;;
      
let rec ieme  i ens =  match ens with
      |  []   -> failwith "Erreur dans ieme"
      | t::q  -> if i=1 then t else ieme (i-1) q ;;
      
let rec ajout e lst_ens = match lst_ens with
      |  []   ->  []
      | t::q  -> (e::t)::(ajout e q) ;;
      
                     (* Determinations d'ensembles *)

let rec parties e =
    if e = [] then [[]]
    else let x = prem e and e_1 = sp e
        in let part = parties e_1
        in  part @ (ajout x part) ;;
                    
let rec combinaisons p e =
    if p > list_length e then [] 
    else if p=0 then [[]]
    else let x = prem e and e_1 = sp e  in
    combinaisons p e_1 @ (ajout x (combinaisons (p-1) e_1))
;;
 
let rec permutations e =
    let n = list_length e in
    if n= 1 then [[prem e]]
    else  
      let rec aux  i accu =       (* parcours de E *)
             if i=0 then accu
             else let x = ieme i e  and e_i = siem i e
             in aux (i-1) ((ajout x (permutations e_i)) @ accu)
      in aux n []    
;;        

let rec bijections e f =
    let n = list_length e and p = list_length f in
    if n <> p or n = 0 then  []
    else  let x = prem e  and e_1 = sp e in
    if n= 1 then [["("^x^","^(prem f)^")"]]
    else 
        let rec aux  i accu =              (* parcours de F *)
            if i=0 then accu
            else  let y = ieme i f  and f_i = siem i f 
                in let chaine = "("^x^","^y^")" 
                in aux (i-1) 
                   ((ajout chaine (bijections e_1 f_i)) @ accu)
         in aux n []    
;;        


let rec surjections e f =
    let n = list_length e and p = list_length f in
    if n < p or n = 0 or p = 0 then  []
    else  let x = prem e  and e_1 = sp e in
    if n= 1 then [["("^x^","^(prem f)^")"]]  (* car n=p=1 *)
    else 
        let rec aux  i accu =             (* parcours de F *)    
            if i=0 then accu           
            else  let y = ieme i f  and f_i = siem i f 
                in let chaine = "("^x^","^y^")" 
                in aux (i-1) 
                       ((ajout chaine (surjections e_1 f_i)) @
                       (ajout chaine (surjections e_1 f)) @ accu)
         in aux p []    
;;        

let rec nb_surjections n p =
    if n < p or n = 0 or p = 0 then  0
    else  
    if n= 1 then 1      (* car n=p=1 *)
    else let rec aux  i accu =
            if i=0 then accu
            else   aux (i-1) (nb_surjections (n-1) (p-1)
                             + nb_surjections (n-1) p + accu)
          in aux p 0    
;;  
\end{verbatim}

\hrule
 
 \bigskip
\bigskip

\hskip-1cm
{\bf Partie II -  Programmation dynamique : chemin de poids minimum }
      

\num{1}
Si on code un chemin allant de $D$ vers $A$ \`a l'aide de 0 et de 1,
    alors on obtient une suite de $n+p-2$ symboles, dont $n-1$ sont des 0.
    Le nombre de telles suites est \'egal au nombre 
\fbox{$C_{n+p-2}^{n-1}$} de combinaisons 
    de $p-1$ \'el\'ements dans un ensemble ayant $n+p-2$ \'el\'ements.   
 
\num{2}
On initialise d'abord la ligne d'indice $n$ et la colonne
d'indice $p$ des deux tableaux.\par
Pour remplir les cases suivantes, on a besoin d'avoir rempli
auparavant la case situ\'ee en dessous et la case situ\'ee \`a  droite.\par
On peut donc envisager un \underbar{remplissage
 par lignes} de bas en haut et de droite \`a gauche
(plus facile \`a programmer qu'un remplissage par diagonales).

 
\begin{verbatim}
let construire_tableaux =  
                                (* initialisations *)
     cout.(n).(p) <- M.(n).(p);
     for j = p-1 downto 0 do  
          choix.(n).(j)  <- 1;
           cout.(n).(j)  <- cout.(n).(j+1) + M.(n).(j); 
     done;        
     for i = n-1 downto 0 do 
           cout.(i).(p)  <- cout.(i+1).(p) + M.(i).(p);
     done ;  
                             (* remplissage par lignes *)
     for i = n-1 downto 0 do 
       for j = p-1 downto 0 do 
          if cout.(i+1).(j) < cout.(i).(j+1) 
             then cout.(i).(j) <- cout.(i+1).(j) + M.(i).(j)
             else begin
                     cout.(i).(j) <- cout.(i).(j+1) + M.(i).(j);
                    choix.(i).(j) <- 1;
                  end
       done
     done ;;
\end{verbatim}
\num{3}
On affiche les cases successives par lesquelles on passe
\`a l'aide d'une fonction locale {\tt affiche}.

\begin{verbatim}
  let affiche_chemin =
   let affiche  x y = 
      print_char `(`; print_int (x+1); 
      print_char `,`; print_int (y+1); print_string") "
   in
   affiche 0 0 ;
   let i = ref 0 and j = ref 0 in
     for k = 1 to n+p do
        if choix.(!i).(!j) = 0 then i := !i + 1 else j := !j + 1;
        affiche !i !j
     done;
   print_newline ()   ;;   
\end{verbatim}
\num{4}
  Le nombre de tests de contenus de cases est :\par

\hskip2cm \fbox{$(n-1)*(p-1)$} pour construire les deux tableaux
~avec $n=|x|$ et $p=|y|$.\par
\hskip2cm \fbox{$n+p-2$}~~      pour afficher le chemin optimal.   
\smallskip

\underbar{Remarque} : conform\'ement \`a l'annexe Caml fournie,
dans les fonctions qui pr\'e\`edent, $n$ et $p$ ont une signification diff \'erente
avec $n=|x|-1$ et $p=|y|-1$.

\bigskip

\hrule
\bigskip
\bigskip

\hskip-1cm
{\bf Partie III - Plus longue sous-suite commune \`a deux suites }  

\begin{verbatim}         
let est_sous_suite x y =                     (* iterative *)
   let n= string_length x and p = string_length y 
       and i = ref 0 and j =ref 0 in
   while (!i < n) && (!j < p) do
      if x.[!i] = y.[!j] then
           begin i := !i + 1; j := !j + 1 end
      else i := !i + 1
   done;
   !j = p  ;;    
                              
let rec est_sous_suite x y =      (* recursive terminale *)
   let n = string_length x and p = string_length y in
     if p = 0 then true else 
        if n = 0 then false else 
           if x.[0] = y.[0] 
             then est_sous_suite (sub_string x 1 (n-1))
                                 (sub_string y 1 (p-1))  
             else est_sous_suite (sub_string x 1 (n-1))  y ;;

let rec est_sous_suite x y =                         
     let n = string_length x and p = string_length y in
   
     let rec aux i j =             (* recursive terminale *)
       if j = p then true else     (* sans  sub_string    *)
          if i= n then false else
             if x.[i] = y.[j] 
                      then aux (i+1) (j+1) else aux (i+1) j
    in aux 0 0  ;;
 
\end{verbatim}
\underbar{Remarques} :

- la derni\`ere version n'est pas  r\'ecursive, mais utilise une
fonction locale {\tt aux}  r\'ecursive qui
a l'avantage de ne pas modifier $x$ et $y$
avec  la  fonction {\tt sub\_string} 
dont le co\^ut n'est pas n\'egligeable.

- le co\^ut en comparaisons de caract\`eres de ces trois fonctions 
est \'egal,
dans le pire des cas,  \`a  la longueur de $|x|$.
         
\num{2} 
\underbar{Algorithme na\"if de d\'etermination d'une {\tt plssc} de $X$ et $Y$}

 On suppose que par exemple $Y$ est de longueur $p$ inf\'erieure 
  ou \'egale \`a la longueur $n$ de $X$.

On construit une liste {\tt L} de toutes les sous-suites de $Y$
 en proc\'edant comme pour les parties d'un ensemble de la partie I.
On peut se d\'ebrouiller pour que cette liste {\tt L}  soit rang\'ee par
longueur d\'ecroissante.

  On examine successivement les sous-suites de $Y$ figurant dans la
 liste {\tt L}  en utilisant la fonction {\tt est\_sous\_suite}
 jusqu'\`a en trouver une  $Z$ qui
    soit aussi sous-suite de $X$ : alors  $Z$ est une {\tt plssc}
\`a $X$ et $Y$.

L'algorithme s'arr\^ete dans le pire des cas avec la sous-suite vide.
    
\smallskip
Si on n\'eglige le temps de construction de la liste {\tt L}, 
alors dans le pire des cas (celui o\`u $Z$ est vide),
    le nombre d'appels de la fonction {\tt est\_sous\_suite}
 est \'egal \`a $2^p$ (nombre de sous-suites de $Y$)
    et chaque appel n\'ecessite au plus $n=|X|$ comparaisons,
d'o\`u un co�t \'enorme  en $O(n\,2^p)$.
    
\smallskip
\num{3}
L'\'enonc\'e donne des conditions n\'ecessaires  sur $Z$ qu'il faut
exploiter pour expliciter $Z$.
\smallskip

\hskip-3mm $\star$ 
Si $X$ ou $Y$ est vide, alors $Z$ aussi.

\smallskip

On suppose maintenant $X$ et $Y$ non vides et on note $X1$ (resp. $Y1$) 
la suite $X$ (resp. $Y$) priv\'ee de son premier terme.

Supposons conna\"itre une {\tt plssc} $Z1$ de $X1$ et $Y1$.

\smallskip
\hskip-3mm $\star$ \underline{si $x_1=y_1$}, alors $Z=x_1.Z1$ est une {\tt plssc}
de $X$ et $Y$.

\smallskip
\hskip-3mm $\star$ \underline{si $x_1\ne y_1$},
 une premi\`ere approche qui d\'ecoule de l'\'enonc\'e
consisterait \`a d\'eterminer une {\tt plssc} de $X1$ et $Y$ d'une part
et une {\tt plssc} de $X$ et $Y1$ d'autre part et \`a prendre pour $Z$
la plus longue : cette m\'ethode utilise donc deux appels r\'ecursifs,
d'o\`u un co\^ut exponentiel en $O(2^{n+p})$ qui 
vient du fait que certains calculs sont effectu\'es plusieurs fois :
par exemple le calcul de la {\tt plssc} de $X_1$ et $Y_1$
intervient deux fois.

\smallskip

Remarquons plut\^ot qu'une {\tt plssc} $Z$ de $X$ et $Y$ est soit $x_1.Z1$, soit
$y_1.Z1$, soit $Z1$.

 Plus pr\'ecis\'ement :\par
\smallskip

\qquad 
\begin{tabular}{ll}
. $Z=x_1.Z1$ & si $x_1.Z_1$ est une sous-suite de $Y1$\\
. $Z=y_1.Z1$ & si $y_1.Z_1$ est une sous-suite de $X1$\\
 . $Z=Z1$ & sinon.
\end{tabular}

\begin{verbatim}
let rec plssc x y =
     if x = "" or y = "" then ""
     else
         let x_1 = sub_string x 1 (string_length x - 1)    
         and y_1 = sub_string y 1 (string_length y - 1)  in
         let z_1 = plssc x_1 y_1 in 
         if x.[0] = y.[0] then (char_for_read x.[0]) ^z_1
         else let xz = (char_for_read x.[0]) ^z_1 in
              if  est_sous_suite y xz then xz
              else let yz =  (char_for_read y.[0]) ^z_1 in
              if  est_sous_suite x yz then yz   
              else z_1 ;;           
\end{verbatim}

On n\'eglige le temps d'ex\'ecution de la fonction {\tt sub\_string}
qu'on peut ne pas utiliser dans {\tt est\_sous\_suite}, ainsi que celui de
 la concat\'enation de cha\"ines.

On suppose que $p=|Y|\le n=|X|$.

Chaque appel r\'ecursif se fait en supprimant un caract\`ere \`a $X$ et $Y$ :
il y a donc $p$ appels r\'ecursifs.\par
Chacun d'eux n�cessite une comparaison et appelle au plus 2 fois la fonction {\tt est\_sous\_suite}
avec des mots de longueurs successives $p-1,\ldots,1,0$ pour $Y$
et $n-1,\ldots, n-p$ pour $X$.

Le co\^ut en comparaisons de caract\`eres est donc major\'e par :

$$p+\displaystyle \sum_{k=1}^{p-1} k+ \sum_{k=n-p}^{n-1} k=n\,p=O(n\,p).$$

\bigskip

\num{5} \underbar{Programmation dynamique}.
\smallskip

On applique les formules fournies par l'\'enonc\'e en proc\'edant comme dans 
 la partie II.
\smallskip

{\it Bien que les deux tableaux soient initialis\'es avec la valeur 0
lors de leur d\'eclaration, on veillera cependant \`a bien
affecter avec 0 les cases qui doivent l'\^etre pour pouvoir
ex\'ecuter les fonctions suivantes plusieurs fois de suite
sans avoir besoin de recompiler \`a chaque fois.}

\newpage
\begin{verbatim}
let construire_tableaux x y =
   let n = string_length x  and  p = string_length y  in 
                    (* initialisations *)
   for j = 0 to p-1 do if y.[j] = x.[n-1] 
             then  begin 
                      cout.(n-1).(j) <- 1; 
                      choix.(n-1).(j) <- 0  
                   end
             else begin 
                      cout.(n-1).(j) <- 0; 
                      choix.(n-1).(j) <- -1
                   end                                         
   done;
   for i = 0 to n-2 do if x.[i] = y.[p-1] 
             then begin
                    cout.(i).(p-1) <- 1; 
                    choix.(i).(p-1) <- 0 
                  end
             else begin 
                    cout.(i).(p-1) <- 0; 
                    choix.(i).(p-1) <- 1 
                  end                                         
   done;
               (* remplissage ligne par ligne *)
   for i= n-2 downto 0 do 
       for j = p-2 downto 0 do
           if x.[i] = y.[j]  then 
              begin 
                   cout.(i).(j) <-  cout.(i+1).(j+1) + 1; 
                   choix.(i).(j) <- 0
              end
           else 
               if cout.(i+1).(j) >= cout.(i).(j+1) 
               then begin 
                         choix.(i).(j) <-  1;
                         cout.(i).(j) <- cout.(i+1).(j) 
                    end
               else begin 
                         choix.(i).(j) <- -1; 
                         cout.(i).(j) <- cout.(i).(j+1)
                    end
       done
   done ;;
   
 let plssc_1 x y =
   let n = string_length x  and  p = string_length y  
   and i = ref 0  and  j = ref 0  and z = ref "" in
   construire_tableaux x y;
   while !i < n  && !j < p do
     if choix.(!i).(!j) = 0 then
       begin   z := !z ^(char_for_read x.[!i]); 
               i := !i + 1;     j := !j +1 
       end
     else if choix.(!i).(!j) = 1 then i := !i + 1 else j := !j +1
   done;
   !z ;;
\end{verbatim}

\num{7}
Ici encore le co\^ut en nombre de comparaisons
de contenus de cases pour construire les deux tableaux est 
major\'e par $n\,p+(n-1)\,(p-1)$ et  celui
de lecture de la {\tt plssc} obtenue avec $n+p-2$ comparaisons.

Ainsi, si l'on ne tient compte que de ces comparaisons, 
cettte m\'ethode dite de {\sl programmation dynamique}
est \underbar{moins avantageuse} que celle du {\bf III.3} sans compter qu'elle est gourmande en m\'emoire
du fait qu'on utilise deux tableaux de taille $n\,p$ chacun
pour stocker beaucoup de valeurs dont peu interviennent dans la {\tt plssc}.\par

\bigskip
$$*+*+*+*+*+*+*+*+*+*$$
\end{document} 



          