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

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

\title{TP 2 : Itération et récursion\\(première partie)}
\begin{document}

\maketitle

Nous allons dans ce TP mettre en pratique ce que nous avons vu en
cours sur les boucles et la récursion. Chaque exercice peut bien
entendu être résolu de bien des façons. Essayez de réfléchir à
plusieurs solutions, et n'oubliez pas, même si cela ne vous l'est pas
systématiquement demandé, de démontrer la validité de vos programmes
et d'en évaluer les complexités temporelle et spatiale.

\begin{Ex}
  Écrire une fonction \texttt{somme\_tableau : int vect -> int} qui
  lorsqu'on lui donne un tableau $T$ d'entiers renvoie la somme de ses
  éléments.
  \begin{corrige}
    
  \end{corrige}
\end{Ex}
\begin{Ex}
  Écrire une fonction \texttt{recherche\_tableau : int vect -> int ->
    bool} qui lorsqu'on lui donne un tableau $T$ d'entiers et un
  entier $n$ renvoie \texttt{true} si $n$ se trouve dans $T$,
  \texttt{false} sinon,
  \begin{itemize}
  \item avec une boucle indexée
  \item avec une boucle conditionnelle
  \item (plus dur) à l'aide d'une fonction récursive.
  \end{itemize}
  Évaluez l'efficacité de chacune de ces fonctions.
  \begin{corrige}
    
  \end{corrige}
\end{Ex}
\begin{Ex}
  \label{poly}
  On représente les polynômes à coefficients entiers par des tableaux
  d'entiers.
  \begin{enumerate}
  \item Écrire une fonction \texttt{deg : 'a vect -> int} renvoyant le
    degré d'un polynôme (la longueur du vecteur) et une fonction
    \texttt{init\_poly : int -> int vect} qui crée un polynôme de
    degré $n$ donné initialisé à $0$ (attention : celui-ci n'est pas
    un vrai polynôme de degré $n$ !).
  \item Écrire une fonction \texttt{add\_p : 'int vect -> 'int vect ->
      'int vect} qui renvoie la somme de deux polynômes. Écrire de
    même des fonctions \texttt{sub\_p}, \texttt{mul\_p}, \texttt{quo\_p}
    et \texttt{res\_p} renvoyant respectivement la différence, le
    produit, le quotient (euclidien) et le reste de la division
    euclidienne de deux polynômes.
  \item Écrire une fonction \texttt{pgcd\_p : 'int vect -> 'int vect ->
      'int vect} calculant le pgcd de deux polynômes.
  \item Évaluer les complexités temporelles et spatiales de toutes ces
    procédures.
  \end{enumerate}
  On verra dans un prochain TP un moyen de manipuler efficacement des
  polynômes du genre $\Xd^{1000}-1$, dont le stockage dans un tableau
  constitue un effroyable gaspillage d'espace.
  \begin{corrige}
    
  \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}
\begin{Ex}[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{Ex}
\begin{Se}[Manipulation de grands entiers]
  Ce sujet d'étude est relativement long. S'il vous intéresse, il vous
  faudra sans doute plusieurs heures de préparation avant d'obtenir
  les fonctions nécessaires à la réalisation de l'objectif final. Vous
  remarquerez sans doute que beaucoup des algorithmes construits dans
  l'exercice \ref{poly} sont presque immédiatement réutilisables. Ceci
  n'est bien entendu pas un hasard.

  On représente donc les entiers par des tableaux (de taille fixée au
  départ) de \emph{chiffres}, ces chiffres étant dans une certaine
  base $b$. Pour se fixer les idées, on prendra $b=10000$, ce qui fait
  que chaque case du tableau correspondra à $4$ chiffres de l'écriture
  décimale du nombre représenté.
  \begin{enumerate}
  \item Écrire les fonctions arithmétiques de base, ainsi que des
    fonctions de test ou d'initialisation qui peuvent vous sembler
    pertinentes. Indiquez les complexités de chacune de ces fonctions.
  \item Testez vos fonctions en calculant $1000!$, ou
    $\Cnp{533}{227}$. Essayez de trouver expérimentalement la
    complexité de vos fonctions, en les testant sur une collection de
    données.
  \item \textbf{Une application : calcul d'une valeur approchée de
      $\pi$}

    Pour représenter un réel, on écrit le début de son développement
    décimal dans un entier long, la case de numéro $0$ correspondant à
    la partie entière du réel.
    
    Archimède a calculé des valeurs approchées de $\pi$ en approchant
    le périmètre d'un cercle de rayon $1/2$ par le périmètre de polygones
    réguliers à $2^n$ cotés. Si $p_n$ est ce périmètre, on a :
    $$p_1=2,\quad p_{n+1}=\frac{p_n}{c_{n+1}}\text{ avec }c_1=0\text{
      et }c_{n+1} = \sqrt{\frac{1+c_n}{2}}$$
    $$0<\pi-p_n\le \frac{1}{6.4^{n-3}}$$
    En utilisant notre
    représentation des réels et la méthode d'Archimède, calculer
    quelques (un petit millier de ?) décimales de $\pi$.
  \end{enumerate}
  \begin{corrige}
    
  \end{corrige}
\end{Se}
\Closesolutionfile{soltp2sup}
\newpage
\titre{Corrigé (partiel) du TP 2 : itération et récursion}
\Readsolutionfile{soltp2sup}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

\begin{Ex}
  
  \begin{corrige}
    
  \end{corrige}
\end{Ex}