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

%% 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\'es, 16 et 19 novembre 1999

\Large
Louis Granboulan et Laurent Mauborgne
\end{center}

\section{Tri Shell}
\begin{enumerate}
\item{Rappels sur le tri par insertion directe}
  \begin{intro}
  Le tri par insertion dierecte consiste \`a ins\'erer un par un les
\'el\'ements de la liste dans le tableau des \'el\'ements d\'ej\`a tri\'es.
  \end{intro}
  \begin{enumerate}
    \item Pour une permutation $\sigma$, on appelle inversion
          un couple $i<j$ tel que $\sigma(i)>\sigma(j)$.
          \'Evaluer le nombre moyen d'inversions d'une permutation
          de $n$ \'el\'ements.
    \item \'Etudier la complexit\'e de l'algorithme en nombre de
          comparaisons et d'affectations.
    \item R\'efl\'echir aux diff\'erentes fa\c{c}ons d'am\'eliorer cet
	  algorithme
  \end{enumerate}
\item{Tri Shell}
  \begin{intro}
  L'id\'ee est d'essayer de gagner sur le nombre d'affectations en ins\'erant
  dans des sous-listes (et donc en faisant faire de plus grands d\'eplacements).
  L'algorithme consiste en un tri par insertion dans des sous-listes 
  contenant de plus en plus d'\'el\'ements, de telle sorte que les \'el\'ements
  soient de plus en plus proches de leur position finale (D. Shell, 1959).
  \par
  On dit qu'un tableau est $h$-tri\'e si les $h$ sous-tableaux
  regroupant les \'el\'ements d'indice diff\'erant d'un multiple de $h$
  sont tri\'es.
  C'est-\`a-dire que les suites $(x_i, x_{i+h}, x_{i+2h}, ...)$
  pour $i = 1, ..., h$ sont tri\'ees.
  \par
  Pour le tri Shell,
  on choisit une suite enti\`ere d\'ecroissante $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\'e donne un ensemble
          $k$-tri\'e. En d\'eduire que le cas $h_s = 2^{s-1}$ n'est pas optimal.
    \item \'Evaluer le nombre moyen d'inversions d'une permutation 2-tri\'ee.
          \begin{enumerate}
          \item Calculer le nombre de permutations 2-tri\'ees.
          \item Montrer que la somme des nombres d'inversions des permutations
                2-tri\'ees de $n$ \'el\'ements (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\'eduire la complexit\'e de l'algorithme dans le cas o\`u on fait
          un 2-tri suivi d'un 1-tri.
    \item Regarder le cas o\`u on fait un $h$-tri suivi d'un 1-tri.
    \item Regarder le cas o\`u $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{Cha\^{\i}nes d'additions}
  \begin{intro}
	Le but est de calculer de mani\`ere aussi efficace que possible la
puissance enti\`ere d'un nombre.
  \end{intro}
  \begin{enumerate}
    \item Trouver diff\'erentes fa\c{c}ons de calculer la puissance enti\`ere
	  d'un nombre en minimisant le nombre de multiplications.
    \item{Les cha\^{\i}nes d'additions}
      \begin{intro}
	Une cha\^{\i}ne d'additions pour $n$ est une suite $a_0,\ldots,a_r$
	telle que $a_0=1$, $a_r=n$ et tout \'el\'ement de la liste est la
	somme de deux \'el\'ements pr\'ec\'edents ($a_i=a_j+a_k$ et $j,k<i$).
      \end{intro}
     \begin{enumerate}
	\item On appelle $l(n)$ la longueur de la plus petite cha\^{\i}ne 
	d'additions pour $n$. D\'eduire des m\'ethodes pr\'ec\'edentes des 
	propri\'et\'es de $l(n)$.
	\item On appelle doublage un \'el\'ement d'une cha\^{\i}ne d'additions
	un \'el\'ement $a_i=a_{i-1}+a_{i-1}$. Soit $d$ le nombre de doublages
	d'une cha\^{\i}ne d'additions pour $n$. Montrer que 
	$n\leq2^{d-1}F_{r-d+3}$ o\`u $(F_k)$ est la suite de Fibonacci.
	\item Trouver $l(n)$ si $n=2^A$, $n=2^A+2^B$, $n=2^A+2^B+2^C$.
     \end{enumerate}
  \end{enumerate}
  Knuth, {\em The Art of Computer Programming, vol. 2 :
\textbf{Seminumerical Algorithms}}, pp. 398--422.
\end{document}
