\documentclass[a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\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, 26 et 29 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{Fractions égyptiennes}
  \begin{intro}
  On appelle \textbf{fraction égyptienne} l'inverse
  d'un nombre entier.
  \end{intro}
  \begin{enumerate}
    \item Trouvez plusieurs algorithmes différents pour décomposer un rationnel
          positif en une somme de fractions égyptiennes distinctes.
    \item Réfléchir au nombre minimum de termes pour représenter
          un rationnel et à la minimisation du plus grand dénominateur
          d'une représentation.
  \end{enumerate}
  \verb|http://www.ics.uci.edu/~eppstein/numth/egypt/|.
\end{document}
