\documentclass[a4paper, 11pt]{article}
\usepackage[utf8]{inputenc} 
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{graphicx}
\usepackage[french]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{stmaryrd}
\usepackage{algpseudocode}
\usepackage{fullpage}
\usepackage{tikz}
\usepackage[trim]{tokenizer}
\usepackage{enumitem}
\usetikzlibrary{snakes,arrows,shapes}

% The sortingnetwork macro defined in this file uses Tikz package to draw a sorting network.
%
% written by: kaayy
% Oct. 10, 2010
%
% Usage:
% \begin{sortingnetwork}[number of inputs][number of layers][scale]
% \nodeconnection{{1, 2},{3, 4}, ...}
% \nodelabel{1, 2, 3, 4, ...}
% ...
% \end{sortingnetwork}

\makeatletter

\newcounter{sncolumncounter}
\newcounter{snrowcounter}

\def \nodelabel#1{%
\setcounter{snrowcounter}{1}
 \foreach \i in {#1}{%
   \draw (\value{sncolumncounter},\value{snrowcounter}) node[anchor=south]{\i};
   \addtocounter{snrowcounter}{1}
 }
 \addtocounter{sncolumncounter}{1}
}

\def \nodeconnection#1{%
  \foreach \i in {#1}{%
    \GetTokens{nodesrc}{nodedest}{\i}
    \draw (\value{sncolumncounter},\nodesrc) node[scale=0.6,circle,fill=black]{}--(\value{sncolumncounter},\nodedest) node[scale=0.6,circle,fill=black]{};
  }
  \addtocounter{sncolumncounter}{1}
}
 
\newenvironment{sortingnetwork}[3]
{
  \setcounter{sncolumncounter}{0}
  \def \sn@fullsize{15}
  \begin{tikzpicture}[scale=#3*\sn@fullsize/#2]
  \foreach \i in {1, ..., #1}
  {
    \draw (0,\i)--(#2-1,\i);
  }
}
{
  \end{tikzpicture}
}
\makeatother


\begin{document}

\title{Réseaux de tri}
\author{Paul Melotti}
\date{mai 2014}
\maketitle
On dispose d'un composant comparateur-échangeur, qui permet d'obtenir le plus petit et le plus grand des deux nombres $a$ et $b$ donnés en entrée :
\begin{center}
\begin{tikzpicture}[>=latex',line join=bevel,]
  \pgfsetlinewidth{1bp}
%%
\pgfsetcolor{black}
  % Edge: foo -> min
  \draw [->] (144.02bp,52.521bp) .. controls (152.84bp,54.976bp) and (162.85bp,57.762bp)  .. (182.32bp,63.181bp);
  % Edge: a -> foo
  \draw [->] (54.003bp,63.899bp) .. controls (62.204bp,61.439bp) and (71.36bp,58.692bp)  .. (89.705bp,53.188bp);
  % Edge: foo -> max
  \draw [->] (144.02bp,37.479bp) .. controls (152.08bp,35.234bp) and (161.14bp,32.713bp)  .. (179.85bp,27.507bp);
  % Edge: b -> foo
  \draw [->] (54.003bp,26.101bp) .. controls (62.204bp,28.561bp) and (71.36bp,31.308bp)  .. (89.705bp,36.812bp);
  % Node: a
\begin{scope}
  \definecolor{strokecol}{rgb}{0.0,0.0,0.0};
  \pgfsetstrokecolor{strokecol}
  \draw (27bp,72bp) node {$a$};
\end{scope}
  % Node: max
\begin{scope}
  \definecolor{strokecol}{rgb}{0.0,0.0,0.0};
  \pgfsetstrokecolor{strokecol}
  \draw (214bp,18bp) node {$max(a;b)$};
\end{scope}
  % Node: b
\begin{scope}
  \definecolor{strokecol}{rgb}{0.0,0.0,0.0};
  \pgfsetstrokecolor{strokecol}
  \draw (27bp,18bp) node {$b$};
\end{scope}
  % Node: foo
\begin{scope}
  \definecolor{strokecol}{rgb}{0.0,0.0,0.0};
  \pgfsetstrokecolor{strokecol}
  \draw (144bp,63bp) -- (90bp,63bp) -- (90bp,27bp) -- (144bp,27bp) -- cycle ;
\end{scope}
  % Node: min
\begin{scope}
  \definecolor{strokecol}{rgb}{0.0,0.0,0.0};
  \pgfsetstrokecolor{strokecol}
  \draw (214bp,72bp) node {$min(a;b)$};
\end{scope}
  % Node: COMP
\begin{scope}
  \definecolor{strokecol}{rgb}{0.0,0.0,0.0};
  \pgfsetstrokecolor{strokecol}
  \draw (117bp,45bp) node {COMP};
\end{scope}
%
\end{tikzpicture}
\end{center}
% % Fin du diagramme
que l'on représentera plus simplement par :
\begin{center}
\begin{sortingnetwork}{2}{3}{0.25}
\nodelabel{$b$,$a$}
\nodeconnection{{1,2}}
\nodelabel{$max(a;b)$,$min(a;b)$}
\end{sortingnetwork}
\end{center}

Un \textit{réseau de comparateur} est un ensemble de comparateurs connectés entre eux, sans cycle, comportant $n$ entrées et $n$ sorties. Une \textit{entrée} (resp. une \textit{sortie}) d’un réseau est une entrée (resp. une sortie) d’un comparateur non connectée. Un \textit{réseau de tri} un réseau de comparateurs qui, étant donné une entrée $a_1, \dots , a_n$ quelconque, renvoie en sortie la liste triée $s_1 \leq \dots \leq s_n$.

\begin{enumerate}
\item Montrer que le réseau suivant est un réseau de tri. Comment s'appelle ce tri ?
\begin{center}
\begin{sortingnetwork}{6}{11}{0.5}
\nodelabel{$a_n$,\dots,\dots,\dots,$a_2$,$a_1$}
\nodeconnection{{5,6}}
\nodeconnection{{4,5}}
\nodeconnection{{3,4},{5,6}}
\nodeconnection{{4,5},{2,3}}
\nodeconnection{{5,6},{3,4},{1,2}}
\nodeconnection{{4,5},{2,3}}
\nodeconnection{{3,4},{5,6}}
\nodeconnection{{4,5}}
\nodeconnection{{5,6}}
\nodelabel{$s_n$,\dots,\dots,\dots,$s_2$,$s_1$}
\end{sortingnetwork}
\end{center}
\item Combien de portes possède ce réseau de tri ? Quel est l'intérêt par rapport à un tri logiciel qui effectue $O(n\log (n))$ comparaisons ?
\item Soit $f$ une fonction croissante. Montrer que si un réseau de comparateurs sur les entrées $a_1, \dots, a_n$ renvoie $b_1, \dots, b_n$ alors ce même réseau lancé sur les entrées $f(a_1), \dots, f(a_n)$ renvoie $f(b_1), \dots, f(b_n)$.
\item \textit{(Principe du 0-1)} Montrer que si un réseau de comparateurs trie correctement les entrées telles que les $a_i$ valent 0 ou 1, alors c'est un réseau de tri.
\end{enumerate}
\subsection*{Tri de listes bitoniques}
Une liste $a_1,\dots,a_n$ est dite \textit{bitonique} si elle vérifie l'une des conditions suivantes :
\begin{itemize}
\item elle est croissante puis décroissante ;
\item elle est décroissante puis croissante ;
\item une permutation circulaire de la liste vérifie l'une des propriétés ci-dessus.
\end{itemize}
\begin{enumerate}[resume]
\item À quoi ressemble une liste bitonique composée de 0 et de 1 ?
\end{enumerate}
\medskip

Soit $n$ un entier de la forme $n = 2^p$, $p \in \mathbf{N}^*$. Notre objectif est maintenant de créer un réseau capable de trier les listes bitoniques $a_1, \dots, a_n$ composées de 0 et de 1.
\begin{enumerate}[resume]
\item Donner un tel réseau dans les cas $p = 1$.
\item On considère le réseau suivant, noté $Sep_p$ :
\begin{center}
\begin{sortingnetwork}{8}{6}{0.3}
\nodelabel{$a_n$,\dots,\dots,\dots,\dots,\dots,\dots,$a_1$}
\nodeconnection{{4,8}}
\nodeconnection{{3,7}}
\nodeconnection{{2,6}}
\nodeconnection{{1,5}}
\nodelabel{$c_{n/2}$,\dots,\dots,$c_1$,$b_{n/2}$,\dots,\dots,$b_1$}
\end{sortingnetwork}
\end{center}
Montrer que les deux listes de sortie $b_1, \dots b_{n/2}$ et $c_1, \dots c_{n/2}$ sont bitoniques, et que tout $b_i$ est inférieur ou égal à tout $c_j$.
\item En déduire un réseau $TriBit_p$ qui trie les listes bitoniques de taille $2^p$ composées de 0 et de 1. Quel est son nombre de portes ? Sa \textit{profondeur} (nombre maximal de portes traversées par un signal d'entrée) ?
\end{enumerate}

\subsection*{Tri-fusion}
\begin{enumerate}[resume]
\item On se donne deux listes \textit{triées} $a = a_1, \dots, a_{n/2}$ et $b = b_1, \dots ; b_{n/2}$ composées de 0 et de 1, où $n = 2^p$, $p \in \mathbf{N}^*$. Déduire de la partie précédente un réseau qui renvoie la fusion des deux listes (comme dans l'algorithme de tri-fusion).

On appelle $Fus_p$ ce réseau.
\item En déduire un réseau de tri pour des entrées de taille $2^p$ à valeurs quelconques. Quel est son nombre de portes ? Sa profondeur ?
\end{enumerate}

\bigskip
Ajtai, Komlós, et Szemerédi ont publié en 1983 un réseau de tri comportant $O(n \log n)$ portes et de profondeur $O(\log n)$, et il est démontré que cette complexité est optimale. Toutefois, les constantes importantes devant ces ordres de grandeur rendent ce réseau inutile en pratique.
\end{document}