\documentclass[a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage[francais]{babel}

\usepackage{hevea}
\ifhtml
\def\linewidth{}
\def\mathbb#1{\textbf{#1}}
\def\atop{}
\def\big{}
%\newenvironment{introduction}{\quotation\footnotesize}{\endquotation}
\newenvironment{intro}{\\\footnotesize}{}

\else

\def\url#1#2{#2 ({\tt #1})}

%% Parametres de mise en page
\topmargin -.04cm
\headheight 0pt
\headsep 0pt
\marginparwidth 0mm
\oddsidemargin  -.04cm
\evensidemargin -.04cm
\textwidth 16cm
\textheight 24.7cm
\advance\textheight by \topskip
\parindent 0pt

\usepackage{amssymb}
\let\geq\geqslant
\let\leq\leqslant
\newenvironment{intro}
  {\begin{center}\begin{minipage}{.9\linewidth}\small}
  {\end{minipage}\end{center}}

\fi
\def\ceil#1{\left\lceil #1\right\rceil}
\def\floor#1{\left\lfloor #1\right\rfloor}

\begin{document}
\begin{center}
\LARGE
Algorithmique et programmation

Travaux dirigés, 10 novembre 2000

Louis Granboulan et Laurent Mauborgne
\end{center}

\section{Structures de données}
\begin{enumerate}
\item{Files et piles}
  \begin{intro}
  Rappels : une file est munie de deux opérations,
  \texttt{enfiler} et \texttt{défiler} et d'un test \texttt{vide}.
  Fonctionnement FIFO (first in, first out).
  Une pile munie de deux opérations, \texttt{push} et \texttt{pop}
  et d'un test \texttt{vide}.
  Fonctionnement LIFO (last in, first out).
  \end{intro}
  \begin{enumerate}
    \item Trouvez une méthode pour simuler une file
    avec des piles, telle que la complexité amortie
    d'une opération sur la file soit une constante.
  \end{enumerate}
\item{Arbres binaires}
  \begin{intro}
  Rappels : tout n{\oe}ud d'un arbre binaire a éventuellement
  un fils gauche et un fils droit. Si on complète cet arbre en
  rajoutant des fils à tous les n{\oe}uds qui en ont 0 ou 1,
  on obtient un arbre binaire complet et les n{\oe}uds rajoutés
  sont appelés feuilles de l'arbre.
  On note $n$ la taille d'un arbre binaire, c'est-à-dire
  le nombre de ses n{\oe}uds. L'arbre binaire complet
  correspondant a donc $n+1$ feuilles et $n$ n{\oe}uds (internes).
  \par
  On se propose de calculer le nombre $C_n$ d'arbres
  binaires de taille $n$, appelé \textit{nombre de Catalan}.
  \end{intro}
  \begin{enumerate}
    \item Commencez par établir une correspondance
    entre les arbres binaires complets de taille $n$ dont un n{\oe}ud
    ou une feuille est distingué et les arbres binaires complets
    de taille $n+1$ dont une feuille est distinguée. En déduire que
    $(n+2)C_{n+1} = 2 (2n+1)C_n$.
    \item En déduire que $C_n = \frac1{n+1}\left(2n\atop n\right)$.
    \item Donner un algorithme de génération aléatoire et
    équiprobable d'un arbre binaire de taille $n$.
  \end{enumerate}
\end{enumerate}

\section{Comparaisons et tri}
\begin{enumerate}
\item{Minimum}
  \begin{enumerate}
    \item Montrer, à l'aide d'un algorithme, que le minimum
    d'un ensemble totalement ordonné de $n$ éléments peut être déterminé
    en $n-1$ comparaisons.
    \item Est-ce la meilleure borne possible ?
    \item Évaluer le nombre moyen d'opérations effectuées par
    votre algorithme
  \end{enumerate}
\item{Minimum et maximum}
  \begin{enumerate}
    \item Montrer, à l'aide d'un algorithme, que le minimum
    et le maximum d'un ensemble totalement ordonné de $n$ éléments
    peuvent être déterminés en $\ceil{3n/2}-2$ comparaisons.
    \item Est-ce la meilleure borne possible ?
  \end{enumerate}
\item{Tri d'un petit nombre d'éléments}
  \begin{intro}
  Soit $S(n)$ le nombre minimal de comparaisons pour trier $n$ éléments.
  \end{intro}
  \begin{enumerate}
    \item Montrer que $S(n) \geq \ceil{\log_2 n!}$.
    \item Déterminer les valeurs exactes de $S(1)$, $S(2)$, $S(3)$,
    $S(4)$ et $S(5)$.
  \end{enumerate}
\end{enumerate}

\section{Tri Shell}
\begin{enumerate}
\item{Rappels sur le tri par insertion directe}
  \begin{intro}
  Soit un tableau contenant $n$ valeurs distinctes.
  Le tri par insertion directe consiste à insérer un par un les
éléments de la liste dans la fin du tableau, contenant les éléments déjà triés.
  \end{intro}
  \begin{enumerate}
    \item Pour une permutation $\sigma$, on appelle inversion
          un couple $i<j$ tel que $\sigma(i)>\sigma(j)$.
          Évaluer le nombre moyen d'inversions d'une permutation
          de $n$ éléments.
    \item Étudier la complexité de l'algorithme en nombre de
          comparaisons et d'affectations.
    \item Réfléchir aux différentes façons d'améliorer cet
	  algorithme
  \end{enumerate}
\item{Tri Shell}
  \begin{intro}
  L'idée est d'essayer de gagner sur le nombre d'affectations en insérant
  dans des sous-listes (et donc en faisant faire de plus grands déplacements).
  L'algorithme consiste en un tri par insertion dans des sous-listes 
  contenant de plus en plus d'éléments, de telle sorte que les éléments
  soient de plus en plus proches de leur position finale (D. Shell, 1959).
  \par
  On dit qu'un tableau est $h$-trié si les $h$ sous-tableaux
  regroupant les éléments d'indice différant d'un multiple de $h$
  sont triés.
  C'est-à-dire que les suites $(x_i, x_{i+h}, x_{i+2h}, ...)$
  pour $i = 1, ..., h$ sont triées.
  \par
  Pour le tri Shell,
  on choisit une suite entière décroissante $h_t, h_{t-1}, ... , h_1$
  avec $h_1 = 1$. On commence par $h_t$-trier le tableau,
  puis on continuer avec $h_{t-1}$, etc.
  Le $h_s$-tri se fait par exemple par insertion directe,
  pour chaque sous-tableau.
  \end{intro}
  \begin{enumerate}
    \item Prouver la correction de cet algorithme de tri.
    \item Prouver que le $h$-tri d'un ensemble $k$-trié donne un ensemble
          $k$-trié. En déduire que le cas $h_s = 2^{s-1}$ n'est pas optimal.
    \item Évaluer le nombre moyen d'inversions d'une permutation 2-triée.
          \begin{enumerate}
          \item Calculer le nombre de permutations 2-triées.
          \item Montrer que la somme des nombres d'inversions des permutations
                2-triées de $n$ éléments (avec $k=\floor{n/2}$) est
                $A_n = \sum_{i=0..k, j=0..k} |i-j|\big({i+j\atop j}\big)
                 \big({n-i-j-1\atop k-j}\big)$.
          \item Prouver $A_{2k+1}=2A_{2k}$. On peut montrer que 
                 $A_{2k}=k4^{k-1}$.
          \end{enumerate}
          En déduire la complexité de l'algorithme dans le cas où on fait
          un 2-tri suivi d'un 1-tri.
    \item Regarder le cas où on fait un $h$-tri suivi d'un 1-tri.
    \item Regarder le cas où $h_s = 2^s-1$.
  \end{enumerate}
\end{enumerate}
Knuth, {\em The Art of Computer Programming, vol. 3 :
       \textbf{Sorting and Searching}}, pp. 87--92.

\end{document}
