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

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

\title{TP 5 : Listes, vecteurs}

\begin{document}

\maketitle
\medskip
\begin{Ex}[Implémentation des ensembles]
  
  On utilise des listes pour représenter des ensembles. Ecrire des
  fonctions réalisant les opérations suivantes :
  \begin{multicols}{2}
    \begin{itemize}
    \item appartenance à un ensemble
    \item suppression des redondances d'une liste
    \item intersection de deux ensembles
    \item réunion de deux ensembles
    \item différence et différence symétrique de deux ensembles.
    \end{itemize}
  \end{multicols}
  \begin{corrige}
  \end{corrige}
\end{Ex}
\medskip
\begin{Ex}[Tri par fusion naturelle]
  Soit \texttt{L=[$a_0$;\dots;$a_{n-1}$]} une liste d'éléments
    comparables. On appelle \emph{séquence croissante} toute
    sous-liste \texttt{[$a_i$;\dots;$a_{j}$]} triée par ordre
    croissant, et \emph{séquence croissante maximale} une séquence
    croissante qui n'est contenue dans aucune autre séquence
    croissante. On propose l'algorithme suivant pour trier \texttt{L}:
    \begin{itemize}
    \item parcourir \texttt{L} en fusionnant deux par deux les
      séquences croissantes maximales ;
    \item recommencer jusqu'à ce qu'il ne reste plus qu'une seule
      séquence.
    \end{itemize}
    \begin{enumerate}
    \item Ecrire une fonction implémentant cet algorithme. Pour cela :
      \begin{itemize}
      \item écrire une fonction recherchant la plus grande séquence
        croissante initiale de \texttt{L}, et la renvoyant avec le
        reste de la liste ;
      \item écrire une fonction fusionnant les séquences croissantes
        de \texttt{L} deux par deux ;
      \item écrire la fonction principale qui fusionne les
        sous-séquences maximales de \texttt{L} tant qu'il en reste
        plus d'une.
      \end{itemize}
    \item Evaluer la complexité de cette fonction.
    \end{enumerate}
  \begin{corrige}
  \end{corrige}
\end{Ex}
\medskip
\begin{Ex}[Structure FIFO, files d'attentes]
  On utilise le type de données suivante :

  \hfil\texttt{type 'a file = \{mutable debut : 'a list; mutable fin :
    'a list\}}\hfil
  
  On ajoute un élément à une file en le plaçant en tête de la liste
  \texttt{fin}. Le premier élément d'une file est la tête de la liste
  \texttt{debut}.
  
  Lorsqu'on cherche à accéder au premier d'une file, il se peut que la
  liste \texttt{debut} soit vide. Dans ce cas, il convient d'abord de
  renverser la liste \texttt{fin} et la transférer dans la liste
  \texttt{debut}.

  \begin{enumerate}
  \item Programmer les primitives suivantes :
    \begin{itemize}
    \item \texttt{file\_vide : unit -> 'a file} : crée une file vide
    \item \texttt{est\_vide : 'a file -> bool} : teste si la file est vide
    \item \texttt{miroir : 'a list -> 'a list} : renverse une liste
    \item \texttt{premier : 'a file -> 'a} : renvoie la tête de la file
    \item \texttt{enfile : 'a -> 'a file -> 'a file} : ajoute un élément
      à une file
    \item \texttt{defile : 'a file -> 'a file} : renvoie une file privée
      de sa tête.
    \end{itemize}
  \item Tester ces primitives su un exemple.
  \item En évaluer la complexité temporelle.
  \end{enumerate}
  \begin{corrige}
  \end{corrige}
\end{Ex}
\newpage
\begin{Ex}[Produits matriciels]
  
  Une matrice sera considérée comme un vecteur de vecteurs :
  \texttt{type 'a matrice = 'a vect vect}.
  
  Par exemple, si \texttt{A = [| [|1; 2|]; [|-1; 1|]|]}, alors
  \texttt{A.(0)} renvoie \texttt{[|1; 2|]}, et \texttt{A.(0).(1)}
  renvoie \texttt{2}.
  
  \begin{enumerate}
  \item Ecrire une fonction calculant la somme de deux matrices.
  \item Ecrire une fonction calculant le produit de deux matrices.
    
    En déduire une fonction \texttt{exponentiation : int matrice ->
      int -> int matrice} calculant la puissance $n$ème d'une matrice
    carrée. Chercher un moyen de réduire au maximum le nombre de
    produits à effectuer.
  \item Combien de produits d'entiers doit-on effectuer pour calculer
    $A^{16}$, où $A$ est une matrice $(n,n)$ ? Et $A^{15}$ ?
  \item Ecrire une fonction qui a une matrice $A$, deux entiers $i$ et
    $j$ et un réel $\alpha$, associe la matrice déduite de $A$ en
    ajoutant $\alpha$ fois la ligne $j$ à la ligne $i$.
    
    En déduire une fonction calculant le déterminant d'une matrice.
    (Préférer la méthode du pivot au développement récursif par rapport
    à une ligne ou une colonne).
    
    Quelle est la complexité d'une telle fonction ? La comparer avec
    celle du développement.
  \end{enumerate}
  \begin{corrige}
  \end{corrige}
\end{Ex}
%% \medskip
%% \begin{Ex}[]
%%   \begin{enumerate}
%%   \item 
%%   \end{enumerate}
%%   \begin{corrige}
%%   \end{corrige}
%% \end{Ex}
\Closesolutionfile{soltp4sup}
\clearpage
\titre{Corrigé (partiel) du TP 5 : Listes et vecteurs}
\Readsolutionfile{soltp4sup}

\end{document}

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

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