\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{amsthm}
\usepackage{enumitem}

\title{Tri polyphasé}
\author{Mathias Millet}
\date{2014}



\begin{document}
\maketitle

\section*{Introduction}
L'algorithme du tri polyphasé est un algorithme de tri adapté de l'algorithme de tri fusion. Il permet d'obtenir de bonnes performances dans le cas d'utilisation de bandes magnétiques en tant que mémoires externes.

Nous utiliserons ici la suite de Fibonacci $(F_n)_{n \in \mathbb{N}}$, définie par $F_0 = 0$, $F_1 = 1$ et $F_{n+2} = F_{n+1} + F_n$ pour $n \geq 0$.


\section*{Modèle de calcul}
On se place dans le modèle suivant :
\begin{itemize}[label=$\bullet$]
\item Un processeur avec une mémoire centrale de taille $M$
\item Trois bandes magnétiques pour stoquer les données, chacune équipée d'une tête de lecture qui peut lire ou écrire une case mémoire à la fois. On supposera les bandes de longueur non bornée.
\end{itemize}

On dispose donc des opérations élémentaires supplémentaires suivantes :
\begin{itemize}[label=$\bullet$]
\item $\mathtt{var \leftarrow lire_i}$ : donne à la variable \texttt{var} la valeur lue sur la bande $i$;
\item \texttt{écrire}$\mathtt{_i(var)}$ : écris la valeur de \texttt{var} sur la bande $i$;
\item $\mathtt{avancer_i}$ : avance d'une case mémoire sur la bande $i$;
\item $\mathtt{reculer_i}$ : recule d'une case mémoire sur la bande $i$;
\end{itemize}

\paragraph{Complexité Entrées/Sorties.}
Dans ce modèle de calcul, on peut définir la complexité entrées/sorties d'un algorithme comme le nombre d'opérations \texttt{avancer} et \texttt{reculer} effectuées pendant une exécution.

\section*{Tri polyphasé}

\paragraph{Définition (Monotonie)} Une monotonie est un tableau trié par ordre croissant, placé sur une bande magnétique.
\paragraph{Définition (Fusion)} La fusion de deux monotonies $M_1$ et $M_2$, de taille $m_1$ et $m_2$ respectivement, est la création d'une nouvelle monotonie, contenant exactement la réunion des éléments de $M_1$ et $M_2$. L'algorithme de la fusion est directement adapté de celui du tri fusion. Pour être efficace en terme d'entrées/sorties, chaque monotonie doit se trouver sur une bande différente, et les têtes de lecture doivent être placées initialement au début des monotonies. La complexité de l'opération de fusion est alors en $O(m_1 + m_2)$.

On suppose en général que les données lues sont effacées au fur et à mesure.

\subsection*{Algorithme du tri polyphasé}
On suppose que le tableau à trier se trouve sur une seule bande. La taille de ce tableau est $N$. On effectue les étapes suivantes :
\begin{itemize}[label=$\bullet$]
\item On trouve $n$ tel que $\frac{N}{F_n} > M \geq \frac{N}{F_{n+1}}$.
\item On découpe les données en paquets de taille $t = \frac{N}{F_{n+1}}$ (on obtient donc $F_{n+1}$ paquets), qu'on trie en mémoire, puis qu'on replace sur les autres bandes, obtenant ainsi des monotonies. On en place $F_{n-1}$ sur la première bande, $F_{n}$ sur la deuxième. 
\item On fusionne alors les paquets comme expliqué ci-dessous.
\end{itemize}

\paragraph{Fusion des monotonies}

\subparagraph{Première étape} La première étape se déroule de la manière suivante :
\begin{enumerate}
\item La première bande contient $F_{n}$ monotonies de taille $t$;
\item La deuxième bande contien $F_{n-1}$ monotonies de taille $t$;
\item La troisième bande est vide.
\end{enumerate}

On fusionne alors 2 à 2 les monotonies des deux premières bandes, en plaçant les nouvelles monotonies obtenues sur la troisième bande. On effectue ainsi $F_{n-1}$ fusions, de complexité $2t$ chacune.

On obtient à  la fin des fusions:
\begin{enumerate}
\item La première bande contient $F_{n-2}$ monotonies de taille $t \cdot F_{i+1}$;
\item La deuxième bande est vide. 
\item La troisième bande contient $F_{n-1}$ monotonies de taille $t \cdot F_{i+2}$.
\end{enumerate}

\subparagraph{$i$\up{ème} étape}
Au début de la $i$\up{ème} étape, on a la situation suivante :
\begin{enumerate}
\item Une bande avec $F_{n-i+1}$ monotonies de taille $t \cdot F_i$;
\item Une bande avec $F_{n-i}$ monotonies de taille $t \cdot F_{i+1}$;
\item Une bande vide.
\end{enumerate}

On fusionne alors 2 à 2 les monotonies des deux premières bandes, en plaçant les nouvelles monotonies obtenues sur la troisième bande. On effectue ainsi $F_{n-i}$ fusions, de complexité $t \cdot F_i + t \cdot F_{i+1}$ chacune.

On obtient à  la fin des fusions:
\begin{enumerate}
\item Une bande avec $F_{n-i-1}$ monotonies de taille $t \cdot F_{i+1}$;
\item Une bande vide;
\item Une bande avec $F_{n-i}$ monotonies de taille $t \cdot F_{i+2}$.
\end{enumerate}

\subparagraph{Arrêt de l'algorithme}
On obtient une unique monotonie à la fin de la $(n-1)$\up{ème} étape. Les données sont alors triées !

\subsection*{Calcul de complexité}

\paragraph{Théorème :} La complexité E/S de l'algorithme du tri polyphasé est en
$ \displaystyle  O \left( N \log\left(\frac{N}{M}\right) \right) $.

\subparagraph{Preuve :}
Le tri et la formation des monotonies initiales sont faits en complexité linéaire. 
Calculons maintenant la complexité des fusions de monotonies. 
La fusion s'exécute en $n-1$ étapes, la $i$\up{ème} étape impliquant $F_{n-i}$ fusions de complexité $O(t \cdot F_i + t \cdot F_{i+1})$ chacune, d'où une complexité totale en
\[ O \left( t \cdot  \sum_{i=1}^{n-1} F_{n-i} F_{i+2} \right) \].
On dispose aussi des deux lemmes suivants :
\subparagraph{Lemme 1 :} $\displaystyle \sum_{k=0}^{n} F_{n-k}F_k = \frac{n-1}{5}F_n + \frac{2n}{5}F_{n-1}$.
\subparagraph{Lemme 2 :} $\displaystyle F_n = \frac{1}{\sqrt{5}}(\phi^n + \bar{\phi}^n)$ avec $|\phi| > 1$, $|\bar{\phi}| < 1$.

Mettons notre expression sous une forme compatible avec celle du lemme 1 :
\begin{align*}
C &= t \cdot \sum_{i=1}^{n-1}  F_{n-i} F_{i+2}  = t \cdot\sum_{i=1}^{n-1} F_{n +2 -(i+2)} F_{i+2} = t \cdot\sum_{k=3}^{n+1} F_{n +2 - k} F_k\\
&=  t \cdot \left( \sum_{k=0}^{n+2} F_{n +2 - k} F_k \quad - \quad \left(2\cdot F_0F_{n+2} + F_1F_{n+1} + F_2F_n \right) \right)\\
&\text{On peut maintenant réécrire }\\
C &= t \cdot \left( \frac{n+1}{5}F_{n+2} + \frac{2(n+2)}{5}F_{n+1} - F_{n+2}\right) = t \cdot \left( \frac{n-4}{5}F_{n+2} + \frac{2(n+2)}{5}F_{n+1} \right)\\
 & \text{Or on sait que } t  = \frac{N}{F_{n+1}} \text{, on a donc }  C = N \cdot  \left( \frac{n-4}{5}\frac{F_{n+2}}{F_{n+1}} + \frac{2(n+2)}{5} \right)
\end{align*} 

\begin{tabular}{ll}
Par définition de $(F_n)_n$, on a & $\displaystyle\frac{F_{n+2}}{F_{n+1}} = 1 + \frac{F_{n}}{F_{n+1}} = O(1)$, et \\
& $\displaystyle \log(F_n) = -\frac{1}{2}\log(5)  + n \log(\phi) + \log(1 + o(1)) \Longrightarrow n = O(\log(F_n))$.
\end{tabular}

On obtient donc que $C = O(N \log(F_n))$.

Finalement, comme $\displaystyle \frac{N}{F_n} > M$, $F_n = O(\frac{N}{M})$, et la complexité de l'algorithme est 
\[\boxed{ O \left(N \log(\frac{N}{M}) \right)} \]
\qed

\paragraph{Preuve du lemme 1 :} Montrons par récurrence, pour $n \geq 1$, la propriété \[ \mathcal{P}(n) : \quad \displaystyle \sum_{k=0}^{n} F_{n-k}F_k = \frac{n-1}{5}F_n + \frac{2n}{5}F_{n-1} \]
\begin{itemize}[label=$\bullet$]
\item $\mathcal{P}(1) : 2 F_1F_0 = 0F_1 + \frac{2}{5}F_0 = 0$ est vraie.
\item $\mathcal{P}(2) :  2F_2F_0  + F_1^2= \frac{1}{5} F_2 + \frac{4}{5}F_1 = 1$ est vraie.
\item Soit $n \geq 2$, supposons $\mathcal{P}(n)$ et $\mathcal{P}(n-1)$ vraies. On a 
\begin{align*}
\sum_{k=0}^{n+1} F_{n+1-k}F_k & = \sum_{k=0}^{n-1} F_{n+1-k}F_k \quad + \quad F_n F_1 + F_{n+1}F_0 
=  \sum_{k=0}^{n-1} (F_{n-k} + F_{n-1-k}) F_k \quad + \quad F_n  \\
& = \sum_{k=0}^{n-1} F_{n-k} F_k  + \sum_{k=0}^{n-1} F_{n-1-k} F_k \quad + \quad F_n
= \sum_{k=0}^{n} F_{n-k} F_k  + \sum_{k=0}^{n-1} F_{n-1-k} F_k \quad + \quad F_n  \\
& = \frac{n-1}{5}F_n + \frac{2n}{5}F_{n-1} \quad + \quad \frac{n-2}{5}F_{n-1} + \frac{2(n-1)}{5}F_{n-2} \quad + \quad F_n\\
& = \frac{4}{5}F_n + \frac{n}{5} (F_n + F_{n-1}) +  \frac{2(n-1)}{5}(F_{n-1} + F_{n-2})\\
& = \frac{n}{5} F_{n+1} +  \frac{2(n-1)}{5}F_n= \frac{4}{5}F_n + \frac{n}{5} F_{n+1} +  \frac{2(n+1)}{5}F_n\\
\end{align*} 
Donc $\mathcal{P}(n+1)$ est vraie.
\end{itemize}
On a ainsi prouvé par récurrence que, pour tout $n \geq 1$, et la propriété $\mathcal{P}(n)$ est vraie. \qed


\paragraph{Preuve du lemme 2 :}
D'après le théorème sur les suites récurrentes définies par une équation linéaires, les suites $(u_n)_n$ qui vérifient 
$u_{n+2} = u_{n+1} + u_n$ pour $n \geq 0$ sont de la forme $ u_n = \lambda \phi^n + \mu \bar{\phi}^n$, où $\phi = \frac{1+ \sqrt{5}}{2}$ et $\bar{\phi} = \frac{1 - \sqrt{5}}{2}$ sont les deux solutions de l'équation $X^2 - X - 1 = 0$.

Les conditions initiales nous permettent de poser: $F_0 = \lambda + \mu = 0$ et $F_1 = \lambda \phi + \mu \bar{\phi} = \frac{1}{2}((\lambda + \mu) + \sqrt{5}(\lambda - \mu) = 1$, d'où $\lambda = - \mu = \frac{1}{\sqrt{5}}$, et $F_n = \frac{1}{\sqrt{5}}( \phi^n + \bar{\phi}^n)$.\qed


\section*{Références}
\begin{itemize}[label=$\bullet$]
\item Christine Froidevaux, Marie-Claude Gaudel, Michèle Soria, \textit{Types de données et algorithmes}.

Directement tiré de ce livre

\item Donald Knuth, \textit{The Art of Computer Programming, Volume 3, Sorting and Searching}

Traite le tri polyphasé, je n'ai pas regardé en détails.
\end{itemize}
\end{document}
