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

\includeversion{solution}

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

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

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

Travaux dirigés, 9 et 10 novembre 1998

Louis Granboulan
\end{center}

\section{Tris par insertion}
On se place dans un contexte où les éléments à trier sont stockés
dans un tableau et où on sait comment comparer deux éléments.
\begin{enumerate}
\item{Tri par insertion directe}
  \begin{intro}
  On insère les éléments un par un
  dans la liste des é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 On recherche la position de l'élément à insérer en
          parcourant la liste des éléments déjà triés,
          puis on fait cette insertion en décalant la liste.
          Étudier la complexité de l'algorithme en nombre de
          comparaisons et d'affectations.
    \item On recherche par dichotomie la position où insérer
          (J. Mauchly, 1946).
          Que gagne-t-on ?
    \item On veut accélérer l'insertion en utilisant une représentation
          chaînée de la liste triée. Analyser cet algorithme si on
          utilise un tableau d'entiers pour implanter cette représentation.
          Comment faire pour conclure l'algorithme en mettant à jour le
          tableau de départ ?
    \item Comment utiliser simultanément les optimisations des deux
          questions précédentes ?
  \end{enumerate}
\item{Tri Shell}
  \begin{intro}
  L'idée est d'insérer les éléments
  à une position proche de leur position finale,
  puis de recommencer avec une contrainte plus stricte,
  jusqu'à ce qu'il soient tous triés (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 le 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 On montre 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}$ et $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.

\section{Fractions égyptiennes}
  \begin{intro}
  On appelle \textbf{fraction égyptienne} l'inverse
  d'un nombre entier.
  \end{intro}
  \begin{enumerate}
    \item Trouvez quatre 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}

\newpage
  \begin{solution}
  Dix algorithmes :
  \begin{itemize}
  \item \textbf{Approximation} :
        algorithme glouton ;
        algorithme glouton à dénominateurs impairs
          (la décomposition existe, mais on n'a pas prouvé que l'algo termine).
  \item \textbf{Résolution de conflits} :
        par découpage
          (on remplace $\frac2y$ par $\frac1y+\frac1{y+1}+\frac1{y(y+1)}$,
          la preuve de terminaison est compliquée) ;
        par mariages
          (on remplace $\frac2y$ par $\frac2{y+1} + \frac2{y(y+1)}$, ce qui
          diminue la suite des termes selon l'ordre lexicographique)
  \item \textbf{Décomposition binaire}
        écriture binaire
          (avec une décomposition de période $b$,
          le début non répétitif donne des fractions $\frac1{2^a}$
          et la séquence répétitive des fractions $\frac1{2^a(2^b-1)}$) ;
        Bezout binaire
          (si $(x2^k \bmod y)<2^{k+1}$, par exemple $y<2^{k+1}$,
          on cherche $r, s$ tels que
          $x 2^k = s y + r$. Alors l'écriture binaire permet de
          représenter $\frac r {2^k}$ et $\frac s {2^k}$ comme
          somme d'inverses de puissances de 2.
          Et $\frac x y = \frac s {2^k} + \frac r {2^k y}$.
          NB: tous les dénominateurs sont pairs.)
  \item \textbf{Fractions continues}
          %NB: tous les dénominateurs sont pairs.)
  \item \textbf{Gloutonnes réverses}
  \item \textbf{Force brute}
  \item \textbf{Petits numérateurs}
  \end{itemize}
  \end{solution}

