\documentclass{tpcaml}
% \includeversion{prof}
% \excludeversion{eleve}
% \includeversion{eleve}
% \excludeversion{prof}

\Newassociation{corrige}{Sol}{soltp01spe}
\renewcommand{\Sollabel}[1]{\textbf{\large Question #1}}
\Newassociation{corrigese}{Solse}{soltp01spe}
\renewcommand{\Solselabel}[1]{\textbf{\large Sujet d'étude #1}}
\Opensolutionfile{soltp01spe}

\title{TP 1 : révisions}

\begin{document}

\maketitle

\titre{Itération}
\begin{Ex}[Décomposition en produit de facteurs premiers]
  Écrivez une fonction \texttt{dec\_fac\_prem :\ int -> unit} qui écrit
  la décomposition en produit de facteurs premiers de l'argument, sous
  la forme :
  \begin{center}
    \texttt{510510 = 2 * 3 * 5 * 7 * 11 * 13 * 17}
  \end{center}
  \begin{corrige}:
    
    On va tester la divisibilité du nombre à factoriser avec $2$ et
    tous les nombres impairs $d$ inférieurs ou égaux à la racine
    carrée de ce qui reste.. En effet, si ceux-ci ne sont pas
    premiers, leurs facteurs ont déjà été éliminés de $n$. On
    s'arrêtera lorsque $n=1$ ou lorsque $n>d^2$. Voir le programme
    \ref{decfacprem}.

    \begin{programme}%
      \caption{Décomposition en produit de facteurs premiers}
      \label{decfacprem}
let dec\_fac\_prem n =
  let facprem = make\_vect 10 (0, 0) (* tableau (facteur * exposant) *)
  and m = ref n (* pour pouvoir le diviser *)
  and u = ref 0 (* puissance du facteur courant *)
  and r = ref 0 (* nombre de facteurs *)
  and facteur m p = (* cherche la plus grande puissance de p divisant n *)
    let k = ref 0 (* au depart, c'est 0 *) in
      while (!m mod p = 0) do (* tant qu'on peut diviser *)
        m := !m / p; (* on ne se prive pas *)
        k := !k + 1 (* et on augmente l'exposant *)
      done;
      !k; (* enfin, on renvoie l'exposant cherche *)
  in
    u := facteur m 2; (* on commence par le seul premier pair *)
    if (!u <> 0) then (* si 2 est facteur *)
      begin 
        facprem.(0) <- (2, !u); (* on le range avec son exposant *)
        r := 1 (* et on passe à la case suivante *)
      end; 
    for i = 1 to int\_of\_float(sqrt(float\_of\_int(!m))) / 2 do
      u := facteur m (2 * i + 1);      (* puis tous les entiers impairs *)
      if (!u <> 0) then (* jusqu'a racine de m *)
        begin 
          facprem.(!r) <- (2 * i + 1, !u); (* memes operations que pour 2 *)
          r := !r + 1
        end
    done;
    print\_newline (); (* on passe a l'affichage : changement de ligne *)
    if !r = 0 then (* on n'a pas trouve de facteurs *)
      begin 
        print\_string ("Le nombre ");
        print\_int n;
        print\_string (" est premier.") (* donc n est premier *)
      end
    else (* sinon *)
      begin 
        print\_int n;
        print\_string (" = ");
        print\_int (fst facprem.(0));
        if (snd (facprem.(0)) > 1) then (* si la puissance n'est pas 1 *)
          begin
            print\_string ("\^");
            print\_int (snd (facprem.(0))) (* on l'affiche *)
          end;
        u := 1; (* deuxieme case du tableau *)
        while (fst (facprem.(!u)) <> 0) do (* tant qu'il reste des facteurs *)
          print\_string (" * ");
          print\_int (fst (facprem.(!u))); (* on les affiche *)
          if (snd (facprem.(!u)) > 1) then
            begin
              print\_string ("\^");
              print\_int (snd (facprem.(!u))) (* avec leurs exposants *)
            end;
          u := !u + 1 (* puis on passe au facteur suivant *)
        done;
        if !m <> 1 then (* s'il reste un facteur *)
          begin
            print\_string (" * "); (* il est forcement premier *)
            print\_int !m;  (* on l'affiche *)
          end;
      end;
    print\_newline ();; (* enfin, on passe a la ligne pour faire joli *)
    \end{programme}
    Remarquez que le code du programme est très documenté. Les
    commentaires peuvent servir à raconter des bêtises, mais ils sont
    essentiellement utiles pour rendre clair un code qui ne l'est
    pas. Vous devez savoir qu'on fait beaucoup de fautes de
    frappes. L'interpréteur (ou le compilateur) corrigera les erreurs
    de syntaxes, mais il n'est pas conçu pour détecter les failles de
    raisonnement. Un petit commentaire illustrant le fonctionnement
    permet de corriger la plupart de ces erreurs.
  \end{corrige}
\end{Ex}
\begin{Ex}[Crible d'Eratosthène]
  \begin{enumerate}
  \item Un entier naturel $n$ étant donné, on veut tous les nombres
    premiers qui lui sont inférieurs ou égaux.
    
    On utilise pour cela la méthode du crible d'Eratosthène :
    \begin{itemize}
    \item On écrit tous les nombres de $2$ à $n$.
    \item On cherche le premier nombre non rayé (au départ $2$), et on
      raye tous ses multiples.
    \item On recommence l'étape précédente jusqu'à ce qu'on ait
      exploré toute la table. Les nombres non barrés sont alors les
      nombres premiers inférieurs à $n$.
    \end{itemize}
    Écrivez une fonction \texttt{crible :\ int -> unit} qui écrit à
    l'écran tous les nombres premiers inférieurs ou égaux à
    l'argument.
  \item En constatant que mis à part $2$, tous les nombres premiers sont
    impairs, et que si $p$ est premier, le premier multiple de $p$
    non déjà rayé est $p^2$, améliorez la fonction précédente.
  \item \textbf{Application graphique}

    Cet question relève plutôt du sujet d'étude. Comptez au moins une
    heure et demi pour la mise au point.
    
    La \emph{spirale d'Ulam} est un tableau dans lequel les nombres
    entiers sont écrits en escargot, et dont les nombres premiers sont
    noircis (voir figure ci-dessous). Les alignements constatés
    correspondent à des valeurs de polynômes à coefficients entiers.
    \begin{center}
      \epsfbox{tp01spe.1}
    \end{center}
    Écrivez une fonction utilisant la bibliothèque graphique, et
    traçant une telle figure.
  \end{enumerate}
  \begin{corrige}:
    \begin{enumerate}
    \item Voici un programme qui imprime le résultat du crible. Vous
      trouverez en commentaires des instructions permettant de
      contrôler le bon fonctionnement du programme... ou de corriger
      un dysfonctionnement (beaucoup plus fréquent, d'après la célèbre
      loi de Murphy) (voir le programme \ref{eratos}
      ).
    
    \begin{programme}%
      \caption{Crible d'Eratosthène (avec contrôle du fonctionnement)}
      \label{eratos}
(* Crible d'Eratosthène *)
let eratosthene = function n ->
  let crible = make\_vect (n+1) true
  and r = int\_of\_float(sqrt(float\_of\_int n))
  and compte = ref 0
  in
    begin
      for i = 2 to r do
        if crible.(i) then (* Si i n'a pas été rayé (il est premier) *)
          begin            (* on raye tous les multiples de i *)
            (* print\_string("je raye les multiples de ");
               print\_int(i);
               print\_newline(); *)
            let j = ref (i * i) (* à partir de i\^{}2 *)
            and pasfini = ref true 
            in
              while !pasfini do
                crible.(!j) <- false;
                (* print\_int(i);
                   print\_string("  "); *)
                compte := !compte + 1;
                j := !j + i;
                pasfini := (n >= !j); (* et ce jusqu'à ce que j *)
              done;                   (* soit supérieur à n *)
              (* print\_newline(); *)
          end
      done;
      for i = 2 to n do
        if crible.(i) then
          begin
            print\_int(i);
            print\_string("  ");
          end
      done;
      print\_newline();
      (* print\_string(" j'ai rayé ");
         print\_int(!compte);
         print\_string(" nombres.");
         print\_newline(); *)
    end;;
      \end{programme}
    \item Le programme précédent tient compte des remarques de cette
      question.
    \item Le programme \ref{ulam} utilise les capacités graphiques de
      l'interface graphique. A priori, si j'ai correctement lu la
      documentation, il doit tourner sans problèmes sous Windows.
      \begin{programme}%
        \caption{spirale d'Ulam : la fonction crible}
        \label{crible} 
\verb+#+open "graphics";;
open\_graph " 501x501+50+50";;

let eratosthene = function n ->
  let crible = make\_vect (n+1) true
  and r = int\_of\_float(sqrt(float\_of\_int n))
  and compte = ref 0
  in
    begin
      for i = 2 to r do
        if crible.(i) then (* Si i n'a pas été rayé (il est premier) *)
          begin            (* on raye tous les multiples de i *)
            (* print\_string("je raye les multiples de ");
               print\_int(i);
               print\_newline(); *)
            let j = ref (i * i) (* à partir de i\^2 *)
            and pasfini = ref true 
            in
              while !pasfini do
                crible.(!j) <- false;
                (* print\_int(i);
                   print\_string("  "); *)
                compte := !compte + 1;
                j := !j + i;
                pasfini := (n >= !j); (* et ce jusqu'à ce que j *)
              done;                   (* soit supérieur à n *)
              (* print\_newline(); *)
          end
      done;
      crible;
    end;;
      \end{programme}

      \begin{programme}%
        \caption{spirale d'Ulam : la fonction de tracé}
        \label{ulam} 
let ulam () =
  let u = ref 250
  and v = ref 250
  and n = ref 1
  and crible = eratosthene 251001
  in
    for i = 1 to 250 do
      u := !u + 1;
      n := !n + 1;
      if crible.(!n) then plot !u !v;
      for j = 1 to (2 * i - 1) do
        n := !n + 1;
        v := !v + 1;
        if crible.(!n) then plot !u !v;
      done;
      for j = 1 to (2 * i) do
        n := !n + 1;
        u := !u - 1;
        if crible.(!n) then plot !u !v;
      done;
      for j = 1 to (2 * i) do
        n := !n + 1;
        v := !v - 1;
        if crible.(!n) then plot !u !v;
      done;
      for j = 1 to (2 * i) do
        n := !n + 1;
        u := !u + 1;
        if crible.(!n) then plot !u !v;
      done;
    done;;
      \end{programme}
      
      Il utilise une version modifiée du crible d'Eratosthène (le
      programme \ref{crible}). L'effet est joli, mais on pourrait
      l'améliorer en dessinant des points plus gros, ou bien en
      changeant la forme de la spirale. Les alignements diagonaux
      correspondent aux valeurs prises par des polynômes à
      coefficients entiers (lesquels ?).
    \end{enumerate}
  \end{corrige}
\end{Ex}
\titre{Récursion}
\begin{Ex}
  \begin{enumerate}
  \item Écrivez un programme calculant $\Cnp n p$ pour $n$ et $p$
    entiers naturels en utilisant la formule de Pascal : $$\Cnp n p =
    \Cnp{n-1}{p} + \Cnp{n-1}{p-1}$$
    
    Déterminez le nombre d'appels récursifs provoqués par le calcul de
    $\Cnp n p$ à l'aide de ce programme (vous pourrez éventuellement
    vérifier votre résultat en ``traçant'' l'exécution du programme, à
    la main ou avec la directive \texttt{trace}).
  \item Essayez d'améliorer ce programme de calcul des combinaisons,
    en trouvant d'autres formules de récurrence.
  \end{enumerate}
  \begin{corrige}:
    \begin{enumerate}
    \item Le programme \ref{combrec}, récursif, exploite directement la
      formule.
      \begin{programme}%
        \caption{Calcul des combinaisons, première version}
        \label{combrec}
let rec binome(n, p) =
  if ((p = 0) or (p = n)) then 1
  else binome(n - 1, p) + binome(n - 1, p - 1);;
      \end{programme}

      Notons $T(n,p)$ le nombre d'appels à la fonction
      \texttt{binome}. On a :
      $$T(n,0) = T(n,n) = 1\quad\text{et}\quad T(n,p) = 1 + T(n-1,p)
      + T(n-1,p-1)\text{ si }0<p<n$$
      En posant alors $T'(n,p)=T(n,p)+1$, on obtient :
      $$T'(n,0) = T'(n,n) = 2\quad\text{et}\quad T'(n,p) = T'(n-1,p) +
      T'(n-1,p-1)\text{ si }0<p<n$$
      Ainsi, $T'(n,p) = 2\Cnp n p$, et
      donc \fbox{$T(n,p) = 2\Cnp n p-1$}. La fonction fait donc à peu
      près deux fois plus de calculs que le résultat qu'elle renvoie.
      On pourrait donc faire le calcul avec l'horloge interne de
      l'ordinateur. Vous pouvez vérifier ce résultat avec la directive
      \texttt{trace "binome"}, ou en mettant à jour une variable
      globale dans le corps de la fonction.
    \item On va plutôt utiliser cette récurrence simple : $\Cnp n p =
      \frac{n}{p}\Cnp{n-1}{p-1}$. D'où le nouveau programme
      \ref{combrapide}, linéaire en $p$ :
      \begin{programme}%
        \caption{Calcul des combinaisons, deuxième version}
       \label{combrapide}
let rec binome\_rapide(n,p) =
  match p with
    | 0 -> 1
    | \_ -> (n * binome\_rapide(n-1, p-1)) / p;;
      \end{programme}
  
      Vous constaterez que ce nouveau programme n'est pas entièrement
      satisfaisant : comme on calcule d'abord \mbox{\texttt{n *
          binome(n-1, p-1)}} avant de diviser par \texttt{p}, il se
      peut que le résultat déborde du cadre des entiers (ce qui,
      rappelons le, ne provoque pas d'arrêt du programme). On ne peut
      se permettre de diviser d'abord par \texttt{p}, ne sachant pas
      si la division va ``tomber juste''.

      Il est clair que ce programme exécute exactement $p$ appels à la
      fonction \texttt{binome}.
    \end{enumerate}
  \end{corrige}
\end{Ex}
\newpage
\begin{Ex}
  \begin{enumerate}
  \item Un maire soucieux des problèmes de circulation dans sa ville
    dont le plan est donné ci-dessous souhaite calculer le nombre de
    chemins reliant $A$ et $B$, sachant que des sens interdits
    n'autorisent que les mouvements vers le nord et vers l'est (les
    routes diagonales sont impraticables dans cette question). Écrivez
    un programme récursif pour l'aider.
  \item Le maire décide d'ouvrir les routes diagonales, en autorisant
    la circulation vers le nord-est (un chemin autorisé est dessiné en
    gras sur la figure précédente). Écrivez un programme tenant
    compte de cette nouvelle règle.
    \begin{center}
      \epsfbox{tp01spe.2}
    \end{center}    
  \end{enumerate}
  \begin{corrige}:
    \begin{enumerate}
    \item Soit $N(n,p)$ le résultat cherché. Compte tenu des sens
      uniques, on a :
      $$N(0,p) = N(n,0) = 1\quad\text{et}\quad N(n,p) = N(n-1,p) +
      N(n,p-1)$$
      Constatons immédiatement, au vu de l'exercice précédent, que la
      méthode récursive, si elle donne un texte de programme très
      court, n'est \textbf{absolument pas efficace}. On fait en effet
      très souvent des calculs déjà faits (voir programme \ref{ville}
      \begin{programme}%
        \caption{Nombre de chemins, première règle}
        \label{ville}
let Nchemins\_0(n,p) =
  if (n=0) or (p=0) then 1
  else 
;;
      \end{programme}
      Pour ne pas faire plusieurs fois les mêmes calculs, on va
      stocker les résultats intermédiaires dans une colonne, comme
      dans le programme \ref{villerapide}.
      \begin{programme}%
        \caption{Nombre de chemins, première règle}
        \label{villerapide}
let Nchemins\_1(n,p) =
  let colonne = make\_vect (p+1) 1 (* colonne.(j) = N(i,j) *)
  in
    for i = 1 to n do
      for j = 1 to p do
        (* ici, colonne.(0) = N(i,0) ... colonne.(j-1) = N(i,j-1),
         * et   colonne.(j) = N(i-1,j) ... colonne.(p) = N(i-1,p)
         * de plus, !v = N(i-1,j-1) *)
        colonne.(j) <- colonne.(j) + colonne.(j-1);
      done;
    done;
    colonne.(p) (* le résultat attendu *)
;;
\end{programme}

      On sent nettement l'amélioration dés que $n$ et $p$ valent aux
      alentours de $10$.
    \item Cette fois ci, la récurrence est :
      $$N(0,p) = N(n,0) = 1\quad\text{et}\quad N(n,p) = N(n-1,p) +
      N(n,p-1) + N(n-1,p-1)$$
      Le programme \ref{villediag} est un tout petit peu plus technique :
      \begin{programme}%
        \caption{Nombre de chemins, deuxième règle}
        \label{villediag}
let Nchemins\_2(n,p) =
  let colonne = make\_vect (p+1) 1 (* colonne.(j) = N(i,j) *)
  and v = ref 1
  in
    for i = 1 to n do
      v := 1;
      for j = 1 to p do
        (* ici, colonne.(0) = N(i,0) ... colonne.(j-1) = N(i,j-1),
         * et   colonne.(j) = N(i-1,j) ... colonne.(p) = N(i-1,p)
         * de plus, !v = N(i-1,j-1) *)
        let w = colonne.(j) in
          colonne.(j) <- colonne.(j) + !v + colonne.(j-1);
          v := w;
      done;
    done;
    colonne.(p);; (* le résultat attendu *)
      \end{programme}
      Pour pouvoir calculer $N(n,p)$, il faut actualiser la colonne
      $n+1$ fois (en comptant l'initialisation), ce qui revient à
      remplir un tableau de $(n+1)\times(p+1)$ cases. La complexité
      est donc en $O(np)$.
    \end{enumerate}
  \end{corrige}
\end{Ex}
\begin{Ex}[Recherche dichotomique dans un dictionnaire]
  On cherche à savoir si un mot se trouve dans un dictionnaire classé
  par ordre alphabétique. Pour cela, on compare le mot recherché au
  mot situé au milieu du dictionnaire. Si ils coïncident, on a
  terminé. Sinon, on recherche le mot dans la seule moitié du
  dictionnaire dans laquelle il peut éventuellement se trouver.
  \begin{enumerate}
  \item Implémenter cet algorithme en une fonction \texttt{dico\_dicho
      : string -> bool}.
  \item Évaluer l'efficacité de cet algorithme. Cet algorithme est-il
    utilisable pour trier une liste plutôt qu'un tableau~?
  \end{enumerate}
  \begin{corrige}:

    On verra cet exemple plus tard, lorsqu'on traitera des arbres
    binaires de recherche.
  \end{corrige}
\end{Ex}

\titre{Travail avec les listes}
\begin{Ex}[Tri par insertion]
  On rappelle le principe du tri par insertion d'une liste d'entiers :
  \begin{itemize}
  \item si la liste est vide, on ne fait rien ;
  \item si la liste est de la forme \texttt{t::q}, on commence par
    trier \texttt{q}, puis on \emph{insère} \texttt{t} au bon endroit.
  \end{itemize}
  \begin{enumerate}
  \item Écrivez une fonction récursive \texttt{insère :\ int -> int
      list -> int list} qui insère son premier argument dans la liste
    \textbf{supposée triée} passée en deuxième argument.
  \item Écrivez une fonction récursive \texttt{tri\_insertion :\ int
      list -> int list} qui trie une liste donnée en argument et
    utilisant la fonction \texttt{insère}.
  \item Étudiez la complexité de cette fonction.
  \end{enumerate}
  \begin{corrige}:
    \begin{enumerate}
    \item Les listes se traitent très souvent avec des fonctions
      récursives, utilisant la décomposition d'une liste en sa tête et
      sa queue. Le programme \ref{insertion}
      ne fait pas défaut à
      cette règle :
      \begin{programme}%
        \caption{insertion dans une liste ordonnée}
        \label{insertion}
let rec insere n l =
  match l with
      [] -> [n]
    | t::q -> if n <= t then n::l
              else t::(insere n q);;
            \end{programme}
            
      Remarquez qu'on essaie de faire le minimum d'appels récursifs en
      plaçant \texttt{n} le plus tôt possible dans la liste.      
    \item La fonction \texttt{tri\_insertion} est elle aussi
      récursive, d'après sa définition (voir programme
      \ref{triinser}).
      \begin{programme}%
        \caption{tri par insertion d'une liste}
        \label{triinser}
let rec tri\_insertion l =
  match l with
      [] -> []
    | t::q -> insere t (tri\_insertion q);;
      \end{programme}
    \item Pour trier une liste à $n$ éléments, on commence par trier
      la queue, composée de $n-1$ éléments, puis on insère la tête
      dans la liste triée. L'opération élémentaire que nous
      utiliserons comme instrument de mesure est la
      comparaison.
      
      Notons $T(n)$ le nombre maximum de comparaisons qu'on doit
      effectuer pour trier une liste de $n$ éléments.  Pour insérer un
      élément dans une liste de $n$ élément, il faut effectuer au pire
      $n$ comparaisons. $T(n)$ vérifie donc la relation de récurrence
      :
      $$T(0)=0\quad\text{et}\quad T(n) = T(n-1) + n-1$$
      On en déduit que
      $$T(n) = \sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}$$
      La complexité de cet algorithme \emph{dans le pire cas} est donc
      en $\Theta(n^2)$.
      
      Remarquons que si l'on suppose que pour une liste quelconque de
      $n$ , il faudra en moyenne $n/2$ comparaisons pour insérer un
      élément, alors la complexité temporelle est seulement divisée
      par $2$, et la complexité \emph{moyenne} est donc elle aussi en
      $\Theta(n^2)$.
    \end{enumerate}
  \end{corrige}
\end{Ex}
\begin{Ex}[Tri fusion]
  Cet algorithme est une application du principe \emph{diviser pour
    régner}.
  \begin{enumerate}
  \item On dispose de deux listes d'entiers \texttt{l1} et \texttt{l2}
    triées par ordre croissant. On veut les réunir en une seule liste
    triée. Écrire une fonction \texttt{fusion :\ int list -> int list
      -> int list} réalisant ceci.
  \item Écrire une fonction \texttt{partition :\ int list -> int list
      * int list} qui partitionne une liste en deux listes
    approximativement de mêmes longueurs.
  \item Pour trier une liste \texttt{l}, on procède de la façon suivante :
    \begin{enumerate}
    \item on partitionne la liste \texttt{l} en deux sous-listes
      \texttt{l1} et \texttt{l2} ;
    \item on trie récursivement les deux listes \texttt{l1} et
      \texttt{l2} ;
    \item enfin on fusionne les listes \texttt{l1} et \texttt{l2}.
    \end{enumerate}
    Construire une fonction \texttt{tri\_fusion :\ int list -> int
      list} qui trie une liste en utilisant ce principe.
  \item Analysez la complexité du tri par fusion, en supposant d'abord
    que $n$ est une puissance de $2$.
  \end{enumerate}
  \begin{corrige}:
    \begin{enumerate}
    \item La fusion de deux listes ne pose pas de problèmes
      particuliers. On distingue trois cas : ceux où l'une des deux
      listes est vide, et le cas général (voir programme
      \ref{fusion}).
      \begin{programme}%
        \caption{fusion de deux listes ordonnées}
        \label{fusion}
let rec fusion l1 l2 =
  match (l1,l2) with
      ([],\_) -> l2
    | (\_,[]) -> l1
    | (h1::r1,h2::r2) ->
        if h1 <= h2
        then h1::(fusion r1 l2)
        else h2::(fusion l1 r2);;
      \end{programme}
    \item Le partage est un peu plus problématique. On va encore
      distinguer trois cas, selon que la liste est vide, a un élément
      ou en a plus de deux (voir programme \ref{partition}).
      \begin{programme}%
        \caption{partition d'une liste en deux sous-listes de mêmes tailles}
        \label{partition}
let rec partition l =
  match l with
      [] -> ([],[])
    | [x] -> ([x],[])
    | h1::h2::r -> match partition r with
          (r1,r2) -> (h1::r1,h2::r2);;
      \end{programme}
      Ce programme fait en fait exactement ce que ferait un joueur
      voulant séparer un paquet de cartes en deux : il en jette
      alternativement une à gauche et une à droite jusqu'à épuisement
      du paquet.
    \item Dés lors que les deux fonctions \texttt{fusion} et
      \texttt{partition} sont implémentées, le reste n'est que routine
      (voir programme \ref{trifusion}).

      \begin{programme}%
        \caption{tri par fusion d'une liste}
        \label{trifusion}
let rec tri\_fusion = function
    [] -> []
  | [x] -> [x]
  | l -> match partition l with
        (l1,l2) -> fusion (tri\_fusion l1) (tri\_fusion l2);;
      \end{programme}
    \item Mettons-nous dans le cas le plus simple : le cas ou la liste
      a une longueur égale à $2^p$. Appelons $T(p)$ le nombre
      d'opérations élémentaires effectuées pour trier cette liste.

      Le coût de la partition en deux sous-listes de longueur
      $2^{p-1}$ et celui de la fusion de ces deux listes une fois
      triées est de l'ordre de $k\times2^p$, $k$ étant une
      constante. Le coût du tri des deux sous-listes de longueurs
      $2^{p-1}$ est $2\times2^{p-1}$. Ainsi :
      $$T(p)=2T(p-1)+k2^p$$
      En posant $U(p) = T(p)/2^p$, on arrive à :
      $$U(p) = U(p-1) + k$$
      Ainsi, $U(p) = pk$, et
      $$T(p) = kp2^p$$
      On revenant à la signification de $p$, on voit que cet
      algorithme a une complexité temporelle dans le pire cas de
      l'ordre de $\Theta(n\ln_2n)$. Ce résultat subsiste quand la
      liste est de longueur quelconque.
    \end{enumerate}
  \end{corrige}
\end{Ex}
% \begin{Ex}
%   \begin{corrige}
    
%   \end{corrige}
% \end{Ex}

\titre{Des exercices plus longs}
\begin{Se}[Algorithmes compte-gouttes]
  \begin{enumerate}
  \item Ces algorithmes permettent d'obtenir les décimales de certains
    nombres ``au compte-gouttes'', c'est-à-dire une à une. Voici le
    procédé pour obtenir des décimales de $\pi$ :
    \begin{center}
      \begin{minipage}{0.8\textwidth}
        \begin{itemize}
        \item Écrire sur une première ligne $A$ les entiers de $1$ à
          $n$, sur une deuxième ligne $B$ les nombres impairs à partir
          de $3$, et sur une troisième ligne (appelée \emph{ligne des
            restes}) des $2$ et un $2$ placé devant.
        \item Répéter $n+1$ fois les opérations suivantes :
          \begin{itemize}
          \item Multiplier chaque nombre de la ligne des restes par
            $10$, l'écrire en dessous dans une ligne $X$.
          \item Placer un $0$ dans la ligne en dessous, appelée
            \emph{ligne des retenues.}
          \item Partant de la droite du tableau, pour toutes les
            colonnes :
            \begin{itemize}
            \item Ajouter le nombre de la ligne $X$ à celui de la
              ligne retenue, placer le résultat dans la ligne $S$.
            \item Calculer le reste $r$ et le quotient $q$ de la
              division du nombre de la ligne $S$ par celui de la ligne
              $B$. Le reste est écrit dans la \emph{ligne des restes},
              et on multiplie le quotient par le nombre placé dans la
              ligne $A$. Ce nombre constitue la retenue de la colonne
              précédente.
            \end{itemize}
          \item Quand on arrive à gauche, le chiffre des dizaines de
            la dernière somme donne une nouvelle décimale, le chiffre
            des unités est conservé comme reste.
          \item On démarre alors l'étape suivante en prenant comme
            nouvelle ligne des restes celle qui vient d'être
            construite.
          \end{itemize}
        \end{itemize}
      \end{minipage}
    \end{center}
    Voici un début de calcul :
    \begin{center}
      \begin{tabular}{l|rrrrrrrrr}
        $A$ &   &  $1$ & $2$ & $3$ & $4$ & $5$ \\ 
        $B$ &   &  $3$ & $5$ & $7$ & $9$ & $11$ \\
        \hline
        $\pi$ & $2$ & $2$ & $2$ & $2$ & $2$ & $2$ \\
        $\times10$ & $20$ & $20$ & $20$ & $20$ & $20$ & $20$ \\
        Retenue & $10$ & $12$ & $12$ & $8$ & $5$ & $0$ \\
        Somme & $\mathbf{3}0$ & $32$ & $32$ & $28$ & $25$ & $20$ \\
        \hline
        Reste & $0$ & $2$ & $2$ & $0$ & $7$ & $9$ \\
        $\times10$ & $0$ & $20$ & $20$ & $0$ & $70$ & $90$ \\
        Retenue & $11$ & $14$ & $18$ & $48$ & $40$ & $0$ \\
        Somme & $\mathbf{1}1$ & $34$ & $38$ & $48$ & $110$ & $90$ \\
        \hline
        Reste & $1$ & $1$ & $3$ & $6$ & $2$ & $2$
      \end{tabular}
    \end{center}
    Les nombres en gras sont les décimales obtenues. L'étape suivante
    fournirait un $2$, il faut plus de colonnes à notre tableau pour
    obtenir plus de décimales.

    La question est bien sûr d'implémenter cet algorithme en une
    fonction \textsc{Caml}.
  \item Pour $e$, il suffit d'écrire dans la première ligne des $1$,
    dans la deuxième les entiers à partir de $2$, et dans la troisième
    un $2$ suivi de $1$. Implémentez ce nouvel algorithme.
  \item En fait, l'algorithme donné pour $\pi$ échoue à la $32$\ieme{}
    décimale (le vérifier !). Stanley Rabinowitz, en 1991, a fournit
    un algorithme modifié de la façon suivante : si le nombre obtenu
    est différent de $9$, on l'écrit. Si il est égal à $9$, on le
    stocke dans une liste de \emph{pré-chiffres}, et on conserve ces
    pré-chiffres tant qu'on trouve des $9$. Si on finit par tomber sur
    un quotient inférieur à $9$, on écrit tous les pré-chiffres et le
    nouveau chiffre obtenu. Par contre, si on finit par tomber sur un
    quotient égal à $10$, on transforme tous les pré-chiffres en $0$,
    et on met en place un nouveau pré-chiffre à $0$.

    Mettez en place cette nouvelle méthode, et contrôlez-la.
  \item Que pouvez-vous dire de l'efficacité de cet algorithme ?
    Connaissez vous des méthodes pour calculer $\pi$ ou $e$ plus
    rapidement ?    
  \end{enumerate}
  \begin{corrigese}
    Je vous présente un programme (le programme \ref{gouttesfaux})
    implémentant le premier algorithme, qui tombe en défaut à la
    $32$\ieme{} décimale. Vous l'adapterrez à vos besoins.
    \begin{programme}%
      \caption{compte-gouttes : première version (incorrecte) pour $\pi$}
      \label{gouttesfaux}
let compte\_goutte\_1 n =
  let m = 10 * n / 3
  in
  let A = make\_vect (m+1) 0
  and B = make\_vect (m+1) 0
  and C = make\_vect (m+1) 2
  and X = make\_vect (m+1) 20
  and R = make\_vect (m+1) 0
  and S = make\_vect (m+1) 0
  in
    for i = 1 to m do
      A.(i) <- i;
      B.(i) <- (2 * i) + 1;
    done;
    for iteration = 1 to n do
      R.(m) <- 0;
      (* print\_string ("Itération numéro "); *)
      (* print\_int (i); *)
      (* print\_newline (); *)
      for j = m downto 1 do
        X.(j) <- C.(j) * 10;
        S.(j) <- X.(j) + R.(j);
        R.(j-1) <- (S.(j) / B.(j)) * A.(j);
        C.(j) <- S.(j) mod B.(j);
      done;
      X.(0) <- C.(0) * 10;
      S.(0) <- X.(0) + R.(0);
      print\_int (S.(0) / 10);
      if (iteration = 1) then print\_string (",");
      C.(0) <- S.(0) mod 10;
    done;
    print\_newline ();;
    \end{programme}
  
    Il est très simple à adapter au cas de $e$, mais la méthode
    corrigée (dont l'énoncé que je vous ai donné est d'ailleurs faux)
    est plus difficile à implémenter : il faut trouver une structure
    adéquate pour stocker les chiffres de garde, sachant qu'on devra
    les modifier si on tombe sur un reste égal à $10$ (on doit alors
    tous les augmenter de $1$, et non les changer en $0$).
  \end{corrigese}
\end{Se}

\begin{Se}[Tranche minimale d'un tableau d'entiers]
  Considérons un tableau $A$ d'entiers relatifs,
  $A=(a_1,\dots,a_n)$. On appelle \emph{tranche} ou \emph{coupe} de
  $A$ une suite extraite notée $A[i..j]$ où $i\le j$ et
  $A[i..j]=(a_i,\dots,a_j)$. Nous noterons $\sigma(i,j)$ la somme des
  termes de la tranche $A[i..j]$ : $$\sigma(i,j) = \sum_{k=i}^j a_k$$
  On s'intéresse à la recherche du minimum des $\sigma(i,j)$ pour
  $1\le i\le j\le n$.
  \begin{enumerate}
  \item On considère pour commencer l'algorithme naïf explorant toutes
    les tranches possibles :
    \begin{center}
      \begin{minipage}{0.5\textwidth}
        $S := a_1$

        pour $j$ de $1$ à $n$ faire
        
        \tv pour $i$ de $1$ à $j$ faire
          
        \tv \tv $S:=min(S,\sigma(i,j))$

        \tv fin pour

        fin pour

        renvoyer S
      \end{minipage}
    \end{center}
    Le traduire en une fonction \texttt{tranche\_naif :\ int vect ->
      int}.

    Étudiez la complexité de cet algorithme. Vous paraît-elle
    satisfaisante ?
  \item En constatant que dans l'algorithme naïf, on calcule plusieurs
    (!) fois les mêmes sommes. Or ce sont ces sommes qui prédominent
    dans le calcul de complexité. Modifiez votre algorithme de sorte
    que dans la boucle interne le calcul de $\sigma(i,j)$ soit
    remplacé par une simple addition, et calculez la nouvelle
    complexité.
    
    Traduisez cet algorithme en une nouvelle fonction
    \texttt{tranche\_moins\_naif}.
  \item On essaie d'améliorer notre analyse du problème en
    introduisant un raisonnement par récurrence. Considérons donc la
    suite $A_n=(a_1,\dots,a_n)$ et supposons $n\ge2$. Les tranches de
    $A_n$ sont de deux types~:
    \begin{itemize}
    \item celles qui ne contiennent pas $a_n$ : ce sont les tranches
      de $A_{n-1}$ ;
    \item celles qui contiennent $a_n$ : il s'agit de la tranche
      $A_n[n..n]$ et des tranches de la forme $A_n[i..n]$ ($i<n$) qui
      s'obtiennent en ajoutant $a_n$ à la tranche $A_{n-1}[i..n-1]$ de
      $A_{n-1}$.
    \end{itemize}
    Ceci nous invite à introduire la notion de \emph{tranche finale}
    pour désigner les tranches dont le deuxième indice est l'indice du
    dernier terme de la suite considérée. Notons alors $m(A_n)$ le
    minimum des sommes des tranches de $A_n$ (c'est ce qui nous
    intéresse) et $mf(A_n)$ le minimum des sommes des tranches finales.
    On a alors :
    $$m(A_1)=mf(A_1)=a_1\text{ et } \left\{\begin{array}{l}
        m(A_n) = \min(mf(A_n),m(A_{n-1}))\\
        mf(A_n) = min(mf(A_{n-1})+a_n,a_n)
      \end{array}\right.$$
    Implémentez cet algorithme en une fonction
    \texttt{tranche\_recur}, et déterminez la nouvelle complexité.
  \item Le dernier calcul ne doit pas nous faire perdre espoir : il
    suffit de l'envisager sous un angle itératif. Construisez un
    algorithme non récursif exploitant les constatations précédentes,
    et traduisez-le en une fonction
    \texttt{tranche\_qui\_decoiffe}. Vous devriez trouver une complexité
    en $O(n)$.
  \end{enumerate}
  \begin{corrigese}:

    Nous corrigerons ce sujet d'étude en TD de façon détaillée.
  \end{corrigese}
\end{Se}
% \begin{Ex}
%   \begin{corrige}
    
%   \end{corrige}
% \end{Ex}

\Closesolutionfile{soltp01spe}
\newpage
\titre{Corrigé (partiel) du premier TP : révisions}
\Readsolutionfile{soltp01spe}

\end{document}

    \begin{Programme}
      \caption{}
      \medskip
\begin{verbatim}
\end{verbatim}
    \end{Programme}
    
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: