<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}[&gt;=latex',line join=bevel,]
  \pgfsetlinewidth{1bp}
%%
\pgfsetcolor{black}
  % Edge: foo -&gt; min
  \draw [-&gt;] (144.02bp,52.521bp) .. controls (152.84bp,54.976bp) and (162.85bp,57.762bp)  .. (182.32bp,63.181bp);
  % Edge: a -&gt; foo
  \draw [-&gt;] (54.003bp,63.899bp) .. controls (62.204bp,61.439bp) and (71.36bp,58.692bp)  .. (89.705bp,53.188bp);
  % Edge: foo -&gt; max
  \draw [-&gt;] (144.02bp,37.479bp) .. controls (152.08bp,35.234bp) and (161.14bp,32.713bp)  .. (179.85bp,27.507bp);
  % Edge: b -&gt; foo
  \draw [-&gt;] (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 Ã&nbsp; 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 Ã&nbsp; 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$ Ã&nbsp; 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}
</pre></body></html>