\documentclass{tpcaml}

\tp{6}{Algorithmes de Tri}

\begin{document}

  \maketitle

  L'objectif de cet énoncé est de présenter deux algorithmes de tri peu
  utilisés, qui sont le \em tri par tas \em et le \em tri par base\em.

\section{Tri par Tas}

  Le tri par tas utilise une structure appellée tas, qui est en réalité un
  arbre binaire ayant deux propriétés:
\begin{itemize}
\item La racine de l'arbre est plus grande que tous ses autres éléments.
\item Les sous-arbres gauche et droit sont des tas.
\end{itemize}

\vspace{12pt}
\begin{question}
On suppose qu'un arbre vérifie la deuxième propriété mais pas la première.
Sans écrire de code, proposer un algorithme de \em percolation \em qui 
transforme cet arbre en tas. Quelle est sa complexité?
\end{question}
\vspace{12pt}

  L'intérêt est que l'on peut trouver le plus grand élément d'un tas en 
  temps constant, donc qu'on peut améliorer la performance d'un tri par 
  sélection en utilisant un tas plutôt qu'une recherche linéaire. Néanmoins, 
  il faut maintenir la structure de tas à chaque fois qu'on extrait un
  élément, de même que pouvoir transformer un tableau en tas. 

\begin{codesection}
  let p i = i/2;;\\
  let g i = i*2;;\\
  let d i = i*2+1;;\\
  let e n i = i >= 0 \&\& i < n;;
\end{codesection}
  On choisit de représenter les tas par des tableaux. La racine qui se
  trouve à l'indice $i$ a pour fils gauche l'indice $2i$ et pour fils droit
  l'indice $2i+1$. Cela est représenté par les fonctions ci-contre. Un tas
  de taille $n$ est toujours de profondeur $\log_2 n$, par construction.

  Les éléments de $0$ à $n-1$ dans le tableau sont le tas, les éléments au-delà 
  sont ceux déjà triés. Trier revient donc à prendre l'élément le plus
  grand du tas, à le mettre à la position $n-1$, et à diminuer la taille
  du tas de 1.
  
\vspace{12pt}
\begin{question}
  Implémenter une fonction récursive \code{percoler t n i} qui applique
  l'algorithme de percolation au sous-arbre du tas $(t,n)$ enraciné en
  $i$. 
\end{question}
\vspace{12pt}
\begin{question}
  En déduire une fonction \code{transformer\_en\_tas t} qui transforme le
  tableau $t$ en un tas, avec $n$ égal à la taille du tableau. 
  Quelle est sa complexité?
\end{question}
\vspace{12pt}
\begin{question}
  Comment peut-on retirer un élément du tas en conservant la propriété de
  tas? Quelle est sa complexité? Programmer cet algorithme puis écrire 
  l'algorithme de tri par tas et déduire sa complexité.
\end{question}
\vspace{12pt}
\begin{question}
  Quelle critique pourrait-on faire à cet algorithme, par rapport à des
  algorithmes plus classiques (tri par insertion, tri rapide, tri fusion) ?
  Quels en sont les avantages et les inconvénients ? Quel choix
  faire dans quelle situation ?
\end{question}
\clearpage
\section{Tri par Base}

  Le tri par base utilise une propriété amusante de l'ordre lexicographique
  sur un alphabet fini. On prend une liste de mots de même taille, 
  et on la partitionne suivant leur dernière lettre avant de recoller
  les partitions par ordre alphabétique. On recommence avant l'avant-dernière
  lettre, et ainsi de suite jusqu'à la première. Lorsqu'on a fini, la liste
  est triée. 

  \vspace{12pt}
  \begin{question}
    S'en convaincre (c'est-à-dire le prouver). 
  \end{question}
  \vspace{12pt}

  On va travailler ici sur les entiers considérés comme des mots sur 
  l'alphabet ${0,1}$ (puisque les entiers naturels en Objective Caml 
  vont de $0$ à $2^{30}-1$, ce sont des mots de longueur 30. On rappelle
  que le $k-ème$ chiffre d'un entier $n$ écrit en base deux est 
  \code{k land (1 lsl n)}.
    \vspace{12pt}
  \begin{question}
    \'Ecrire une fonction \code{couper i l} qui sépare la liste d'entiers
    $l$ en deux listes, suivant que le $i$-ème bit de chaque entier (le
    coefficient de $2^i$ dans son écriture en base $2$) est égal à 0 ou à
    1. L'ordre des entiers dans chaque sous-liste doit être le même que
    dans la liste d'origine. Quelle est sa complexité?
  \end{question}
  \vspace{12pt}
  En théorie, on devrait recoller les listes, puis les scinder à nouveau
  suivant le bit suivant. C'est lent: concaténation, donc temps de calcul 
  linéaire. Au lieu de ça, on constate que recoller les listes puis les 
  scinder est équivalent à scinder les listes puis les recoller.
  \vspace{12pt}
  \begin{question}
    Modifier la fonction \code{couper} pour qu'elle fasse le recollement
    en même temps qu'elle scinde la liste. La fonction sera de la forme
    \code{couper i l (a0,a1)} où \code{a0} et \code{a1} sont des listes 
    déjà scindées suivant le bit $i$ auxquelles il faut recoller le
    résultat de l'opération de découpage. 
  \end{question}
  \vspace{12pt}
  \begin{question}
    Définir la fonction \code{tri\_par\_base}, qui utilise la fonction
    de découpage 30 fois pour regrouper nos éléments. Quelle est sa complexité? 
    Quels sont les facteurs importants à prendre en compte?
  \end{question}

\section{Question Difficile}

  \begin{question}
    Supposons que l'on veuille trier non pas des entiers, mais des 
    chaînes de caractères sur un alphabet défini à l'avance. Quelles 
    solutions proposer ?
  \end{question}
 
\end{document}