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

%% Parametres de mise en page
\topmargin .96cm
\headheight 0pt
\headsep 0pt
\marginparwidth 0mm
\oddsidemargin  .96cm
\evensidemargin .96cm
\textwidth 14cm
\textheight 22.7cm
\advance\textheight by \topskip
\parindent 0pt

\def\ceil#1{\left\lceil #1\right\rceil}
\def\floor#1{\left\lfloor #1\right\rfloor}
\usepackage{amssymb}
\let\geq\geqslant
\let\leq\leqslant
\def\intro{\begin{center}\begin{minipage}{.9\linewidth}\small}
\def\endintro{\end{minipage}\end{center}}

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

Travaux dirigés, 19 et 20 octobre 1998

Louis Granboulan
\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 n'en ont pas deux,
  on obtient un arbre binaire complet et les n{\oe}uds rajoutés
  sont les 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.
  \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{Structures récursives}
\begin{enumerate}
\item
  On suppose que les piles ont une représentation chaînée.
  Écrire les primitives \texttt{vide}, \texttt{push} et \texttt{pop},
  puis implanter sans récursivité la recherche et suppression d'un
  élément dans une pile.
  \begin{enumerate}
  \item dans le cas où la pile vide est représentée par le pointeur NULL.
  \item dans le cas où une garde précède le premier élément.
  \end{enumerate}
\item
  On utilise une représentation chaînée pour les arbres binaires complets.
  on appelle {\em frontière} la liste (de droite à gauche) des valeurs
  des feuilles de l'arbre.
  \begin{enumerate}
  \item Concevoir un algorithme qui calcule la forntière de l'arbre.
  \item Imaginer un algorithme qui annonce si deux arbres binaires complets
  ont la même frontière.
  On doit éviter de calculer toute la frontière si ce n'est pas nécessaire.
  \end{enumerate}
\end{enumerate}

\section{Algorithmique}
\begin{enumerate}
\item{Exponentiation}
  \begin{intro}
  Dans un monoïde multiplicatif $G$,
  on suppose que les opérations \texttt{mul} et \texttt{sqr}
  de multiplication et d'élévation au carré sont efficaces.
  On cherche à calculer la puissance $n$-ième.
  \end{intro}
  \begin{enumerate}
    \item Trouver un algorithme qui effectue ce calcul
    en ${\cal O}(\log n)$ opérations.
    Compter plus précisément le nombre de carrés et de
    multiplications.
    \item Imaginer une variation de cet algorithme qui,
    avec un petit précalcul, diminue le nombre moyen
    de multiplications. (Hint : représenter en base $2^k$
    au lieu de 2.)
  \end{enumerate}
\item{Avec inversion}
  \begin{intro}
  Dans le cas où $G$ est un groupe, on peut espérer faire mieux
  si le calcul de l'inverse est efficace.
  \end{intro}
  \begin{enumerate}
    \item Trouver un algorithme qui donne une représentation
    de longueur minimale de l'entier $n$ comme somme signée
    de puissances de 2.
    \item Utiliser ceci pour le calcul de la puissance $n$-ième.
  \end{enumerate}
\item{Systèmes de numération redondants}
  \begin{intro}
  On vient de voir que la représentation classique en base $B$ d'un
  entier $n$ n'est pas la seule intéressante.
  Ici on représente $n = \sigma_{i=0..k-1} n_i B^i$ avec
  $-c_{\min} \leq n_i \leq c_{\max}$ avec $c_{\min}$ et $c_{\max} < B$.
  \end{intro}
  \begin{enumerate}
    \item Donner une condition nécessaire et suffisante sur les entiers
    naturel $B$, $c_{\min}$ et $c_{\max}$ pour que tout entier naturel
    admette une représentation.
    Donner une exemple de système de numération redondant, i.e. tel que
    certains entiers admettent plusieurs représentations.
    \item Supposant que $c_{\min} = c_{\max} = a$, que fait l'algorithme
    suivant qui prend $x = (x_{k-1}...x_0)$ et $y = (y_{k-1}...y_0)$
    pour fournir les $k+1$ valeurs $z_0$, ... $z_k$ ?
    \begin{itemize}
    \item[1.] Pour $i = 0..k-1$ calculer $t_{i+1} = \left\{\begin{array}{rl}
       1 & \mbox{si } x_i+y_i \geq a \cr
     - 1 & \mbox{si } x_i+y_i \leq -a \cr
       0 & \mbox{si } x_i+y_i \in ] -a, a [ \cr
       \end{array}\right.$
    \item[2.] Pour $i = 0..k$ calculer $z_i = w_i + t_i$
    avec la convention $t_0 = w_k = 0$.
    \end{itemize}
    \item Quel est l'intérêt d'un tel algorithme ?
  \end{enumerate}
\end{enumerate}

\end{document}
