% Fuer mathtoolsset
\usepackage{mathtools}
-\geometry{paper=a4paper,margin=25mm}
+\geometry{paper=a4paper,margin=30mm}
\pagestyle{fancy}
%\fancyhf{}
\tikzstyle{diredge} = [draw,thick,->]
\tikzstyle{prob} = [font=\tiny]
+\tikzstyle{edge minimum} = [edge,color=blue!20]
+\tikzstyle{edge maximum} = [edge,color=red!20]
+\tikzstyle{vertex active minimum} = [vertex,color=blue!50, fill=blue!50]
+\tikzstyle{vertex active maximum} = [vertex,color=red!50, fill=red!50]
+\tikzstyle{vertex inactive minimum} = [vertex,color=blue!20, fill=blue!20]
+\tikzstyle{vertex inactive maximum} = [vertex,color=red!20, fill=red!20]
+\tikzstyle{vertex inactive minimum maximum} = [vertex,color=black!20, fill=black!20]
+\tikzstyle{comp active minimum} = [comp]
+\tikzstyle{comp active maximum} = [comp]
+\tikzstyle{comp inactive minimum} = [comp,color=blue!20]
+\tikzstyle{comp inactive maximum} = [comp,color=red!20]
+\tikzstyle{comp inactive minimum maximum} = [comp,color=black!20]
+
\tikzstyle{red box} = [draw,-,color=red, top color=red!2,bottom color=red!10]
\tikzstyle{blue box} = [draw,-,color=blue,top color=blue!2,bottom color=blue!10]
\tikzstyle{green box} = [draw,-,color=teal,top color=teal!2,bottom color=teal!10]
Übersicht über bekannte konstruktive Sortiernetzwerke.
-\subsection{Odd-Even-Transpositionsort}
+\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der
einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
"`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
-Abbildung~\ref{fig:odd_even_transposition_08} zeigt das OET-Netzwerk für
+Abbildung~\ref{fig:odd-even-transposition-08} zeigt das OET-Netzwerk für
${n = 8}$ Leitungen.
\begin{figure}
-\begin{center}
-\input{images/oe-transposition-8.tex}
-\end{center}
-\caption{Das {\em Odd-Even-Transpositionsort-Netzwerk} für acht Eingänge.}
-\label{fig:odd_even_transposition_08}
+ \begin{center}
+ \input{images/oe-transposition-8.tex}
+ \end{center}
+ \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.}
+ \label{fig:odd-even-transposition-08}
\end{figure}
-\subsection{Batcher's Mergesort}
-
-Ein Netzwerk von K.~E.~Batcher. Siehe:
-K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring
-Joint Comput. Conf., Vol. 32, 307-314 (1968)
-\todo{Bibtex!}
+Dass das Odd-Even-Transporitionsort-Netzwerk tatsächlich jede beliegibe
+Eingabe sortiert ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass
+sowohl das Minimum als auch das Maximum durch das im Netzwerk enthaltene
+Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt. Beim
+Odd-Even-Transporitionsort-Netzwerk mit drei Eingängen,
+$\operatorname{OET}(3)$, ist die Ausgabe folglich sortiert.
+
+Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen,
+indem man $\operatorname{OET}(n)$ auf $\operatorname{OET}(n-1)$ durch
+Herausschneiden einer Leitung reduziert. In
+Abschnitt~\ref{sect:leitungen_entfernen} wird das Vorgehen im Detail
+beschrieben, Abbildung~\ref{fig:oe-transposition-cut} zeigt das
+Herausschneiden einer Leitung aus $\operatorname{OET}(8)$.
+
+Das Odd-Even-Transporitionsort-Netzwerk ist weder in Bezug auf die Anzahl der
+Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen sich die
+Komparatoren anordnen lassen, effizient. Es benötigt
+${\frac12 n (n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten
+angeordnet sind. Andere Sortiernetzwerke benötigen deutlich weniger
+Komparatoren, beispielsweise $\mathcal{O}(n (\log n)^2)$, die in weniger
+Schichten, zum Beispiel $\mathcal{O}(\log n)$, angeordnet sind.
+
+Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
+folgenden Algorithmen benötigen ein (einfaches) Sortiernetzwerk als
+Starteingabe, auf dessen Basis sie versuchen optimierte Sortiernetzwerke zu
+finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
+Algorithmen.
+
+\subsection{Das bitone Mergesort-Netzwerk}
+
+Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
+Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968}
+veröffentlicht wurde. Es ist deutlich effizienter als das
+Odd-Even-Transporitionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
+Komparatoren als auch bezüglich der benötigten Zeit, also der Anzahl der
+Schichten.
+
+Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei
+sortierte Listen zusammenfügen (englisch: \textit{to~merge}) kann. Dieser
+\emph{„bitoner Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein
+verleiht dem Sortiernetzwerk seinen Namen.
+
+Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
+Instanzen des Netzwerks, deren Leitungszahl eine Zweierpotenz ist,
+$\operatorname{BS}(n = 2^t)$.
\subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
-Das Netzwerk basiert auf dem {\em bitonen Mischer}, einem Komparator-Netzwerk,
-das eine beliebige bitone Folge in eine sortierte Listen umordnen kann. Eine
-{\em bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton
-fallenden Folge, oder ein zyklischer Shift davon.
-Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinipiellen Möglichkeiten
-die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für
-Batcher's Mergesort-Netzwerk zeigen die Abbildungen~\ref{fig:beispiel-biton-0}
+Das \emph{bitone Mergesort-Netzwerk} basiert auf dem sogenannten \emph{bitonen
+Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine beliebige
+\emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine \emph{bitone
+Folge} ist eine monoton steigende Folge gefolgt von einer monoton absteigenden
+Folge, oder ein zyklischer Shift davon. Abbildung~\ref{fig:beispiel-biton}
+zeigt die vier prinzipiellen Möglichkeiten die durch zyklische Shifts
+entstehen können. Die wichtigsten Varianten für das \emph{bitone
+Mergesort-Netzwerk} zeigen die Abbildungen~\ref{fig:beispiel-biton-0}
und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und
-eine absteigend sortierte Liste aneinanderhängt. Bei den
-anderen beiden Formen ist wichtig zu beachten, dass das letzte Element nicht
-größer (Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner
+eine absteigend sortierte Liste aneinanderhängt. Bei den anderen beiden Formen
+ist wichtig zu beachten, dass das letzte Element nicht größer
+(Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner
(Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein
darf.
> v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
"`linken"' Folge, $u_{m-1}$, kleiner ist als das kleinste Element der
-"`rechten"' Folge, $v_{m-1}$. Daraus folgt, dass die entstehende Folge aus
-zwei bitonen Folgen besteht, die rekursiv zusammengeführt werden können.
-Abbildung~\ref{fig:bitonic-merge-normal} zeigt die Situationen vor und nach
-diesem Schritt des Mischers.
-
-Mit dem bitonen Mischer auch zwei aufsteigend sortierte Folgen sortiert
-werden. Dazu ist lediglich das "`Umbenennen"' der Leitungen notwendig.
-Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das Schema des bitonen
-Mischers für zwei aufsteigend sortierte Foglen. Durch das Umbenennen verändert
-sich das Muster der Komparatoren ein wenig: Statt an eine Treppe erinnert das
-Muster nun an einen Trichter.
+"`rechten"' Folge, $v_{m-1}$. Daraus folgt, dass das Resultat in zwei bitone
+Folgen aufteilen lässt: Eine aufsteigende~/ absteigende Folge und eine
+absteigende~/ aufsteigende Folge. Abbildung~\ref{fig:bitonic-merge-normal}
+zeigt die Situationen vor und nach diesem Schritt des Mischers.
+
+Um die Folge vollständig zu sortieren, müssen anschließend die beiden
+resultierenden bitonen Folgen sortiert werden. Die geschieht ebenfalls
+mithilfe des bitonen Mischers, mit zwei Instanzen von
+$\operatorname{BM}(\frac{n}{2})$. Diese rekursive Definition endet mit dem
+bitonen Mischer mit zwei Leitungen, $\operatorname{BM}(2)$, der als
+Komparator-Netzwerk mit einem Komparator zwischen den beiden Leitungen
+definiert ist.
+
+Der bitonen Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist
+lediglich eine etwas modifizierte Vergleichs-Kaskade im ersten Schritt
+notwendig. Die folgenden, kleineren Mischer erhalten als Eingabe wieder eine
+„echte“ bitone Folge. Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das
+Schema des bitonen Mischers für zwei aufsteigend sortierte Foglen. Durch das
+Umdrehen einer Folge verändert sich das Muster der Komparatoren ein wenig:
+Statt an eine Treppe erinnert das Muster nun an einen Trichter.
+
+Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
+die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
+$\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus
+$\frac{1}{2} n \log(n) = \mathcal{O}\left(n \log(n)\right)$~Komparatoren
+besteht, die in $\log(n)$~Schichten angeordnet werden können.
+
+\subsubsection{Das bitone Mergesort-Netzwerk}
+
+Ebenso wie der bitone Mischer $\operatorname{BM}(n)$ ist auch das \emph{bitone
+Mergesort-Netzwerk} $\operatorname{BS}(n)$ rekursiv definiert. Es setzt sich
+zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe,
+$\operatorname{BS}(\frac{n}{2})$, für je die Hälfte der Eingänge, sowie dem
+bitonen Mischer für $n$~Leitungen, $\operatorname{BM}(n)$. Das Rekursionsende
+ist das bitone Mergesort-Netzwerk mit nur einer Leitung,
+$\operatorname{BS}(1)$, welches als leeres Komparatornetzwerk definiert ist.
+Entsprechend sind die Komparatornetzwerke $\operatorname{BM}(2)$ und
+$\operatorname{BS}(2)$ identisch.
+
+Bei der Konstruktion kommt die trichterförmige Anordnung der Komparatoren
+(Abbildung~\ref{fig:bitonic-merge-tricheter}) gelegen, weil so die beiden
+rekursiven Sortiernetzwerke in die gleiche Richtung sortieren können und so
+alle Komparatoren in die gleiche Richtung zeigen.
-\subsubsection{Batcher's Bitonic-Mergesort-Netzwerk}
-
-Das Sortiernetzwerk $S(n)$ mit $n$~Eingängen besteht aus zwei Instanzen von
-$S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen und dem bitonen
-Mischer~$M(n)$. Die Rekursion bricht bei ${n = 1}$~ab --~eine einelementige
-Liste ist immer sortiert.
-Das konkrete Netzwerk~$S(8)$ ist in Abbildung~\ref{fig:batcher_08} zu sehen.
-Eingezeichnet sind ebenfalls die beiden Instanzen des Netzwerks~$S(4)$ (rot)
-sowie der bitone Mischer~$M(8)$ (blau).
+\begin{figure}
+ \begin{center}
+ \input{images/batcher-8.tex}
+ \end{center}
+ \caption{$\operatorname{BS}(8)$, Batchers {\em bitones Mergesort-Netzwerk}
+ für acht Eingänge. Markiert sind die beiden Instanzen von
+ $\operatorname{BS}(4)$ (rot), die beiden bitonen
+ Mischer~$\operatorname{BM}(4)$ (blau) und die Komparatoren, die im letzten
+ rekursiven Schritt hinzugefügt wurden (grün).}
+ \label{fig:bitonic-08}
+\end{figure}
+Das konkrete Netzwerk~$\operatorname{BS}(8)$ ist in
+Abbildung~\ref{fig:bitonic-08} zu sehen. Eingezeichnet sind ebenfalls die
+beiden Instanzen des Netzwerks~$\operatorname{BS}(4)$ (rot) sowie der bitone
+Mischer~$\operatorname{BM}(8)$ (blau). Die trichterförmige Komparator-Kaskade,
+die die bitone Eingabefolge in zwei bitone Ausgabefolgen transformiert, ist
+grün hinterlegt.
+Das \emph{bitone Mergesort-Netzwerk} $\operatorname{BS}(8)$ besteht aus
+$\frac{1}{4} n \log(n) \log(n+1) = \mathcal{O}\left(n (log (n))^2\right)$
+Komparatoren, die in $\frac{1}{2} \log(n) \log(n+1) = \mathcal{O}(\log(n))$
+Schichten angeordnet sind.
%\begin{figure}
%\begin{center}
%\label{fig:bms_rekursiver_aufbau}
%\end{figure}
-\begin{figure}
- \begin{center}
- \input{images/batcher-8.tex}
- \end{center}
- \caption{$S(8)$, Batcher's {\em bitone Mergesort-Netzwerk} für acht
- Eingänge. Markiert sind die beiden Instanzen von $S(4)$ (rot), die beiden
- bitonen Mischer~$M(4)$ (blau) und die Komparatoren, die im letzten rekursiven
- Schritt hinzugefügt wurden (grün).}
- \label{fig:batcher_08}
-\end{figure}
-
-\subsection{Odd-Even-Mergesort}
+\subsection{Das Odd-Even-Mergesort-Netzwerk}
-Obwohl der Name ähnlich klingt, haben {\em Odd-Even-Mergesort} (OEM) und
-{\em Odd-Even-Transpositionsort} (OET, siehe
-Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Auch dieses
-Netzwerk ist von K.~Batcher gefunden worden und wird rekursiv durch einen
-"`Mischer"' definiert.
+Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk}
+(OES) und das \emph{Odd-Even-Transpositionsort-Netzwerk} (siehe
+Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Vielmehr ist
+OES dem \emph{bitonen Mergesort-Netzwerk}, das im vorherigen Abschnitt
+vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von
+\textit{Kenneth~E. Batcher} gefunden worden und ist ebenfalls in~\cite{B1968}
+beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht
+darin, dass es ebenfalls rekursiv durch einen Mischer definiert wird.
\subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer}
-Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte
-Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit
-weniger Vergleichen aus als der {\em bitone Mischer}, der im
-Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde, aus.
+Der \emph{Odd-Even-Mischer} $\operatorname{OEM}(n,m)$ ist ein
+Komperatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$
+Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
+zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
+\emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}
+vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even-Mischer} unter
+Umständen mehr Schichten als der \emph{bitone Mischer}.\footnote{Knuth,
+“Bitonic Sorting”, Seite~230}
-Der {\em Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
+Der \emph{Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
$V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
\label{fig:oe-merge}
\end{figure}
-Diese werden jetzt in insgesamt vier sortierte Folgen aufgeteilt, je eine
-Liste der geraden Indizes und je eine Liste der ungeraden Indizes.
+Diese werden in insgesamt vier sortierte Folgen aufgeteilt, je eine Liste der
+geraden Indizes und je eine Liste der ungeraden Indizes.
\begin{eqnarray}
U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\
U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
\end{itemize}
Dass die resultierende Folge sortiert ist, lässt sich mit dem
-{\em 0-1-Prinzip} leicht zeigen:
+{\em 0-1-Prinzip} zeigen:
Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden
Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder
gleich der Anzahl der Nullen in den ungeraden Teilfolgen
Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
-wenn $W_{\textrm{gerade}}$ $2$~Nullen mehr enthählt als
-$W_{\textrm{ungerade}}$, muss eine Vertauschung stattfinden, um die Ausgabe zu
-sortieren. Die jeweiligen Situationen sind in
-Abbildung~\ref{fig:oe-post-recursive} dargestellt.
+wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthählt als
+$W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die
+Ausgabe zu sortieren. Diese wird von den Komparatoren, die benachbarte
+Leitungen miteinander vergleichen, ausgeführt. Die jeweiligen Situationen sind
+in Abbildung~\ref{fig:oe-post-recursive} dargestellt.
\begin{figure}
\centering
\label{fig:oe-post-recursive}
\end{figure}
+Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,
+bricht die Rekursion nach $\mathcal{O}\left(\log (n) + \log (m)\right)$
+Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
+Schichten im Mischer-Netzwerk), hängt von der Längeren der beiden
+Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.
+
+Die Anzahl der Komparatoren $K(n,m)$, die $\operatorname{OEM}(n,m)$ im
+allgemeinen Fall verwendet, ist Gemäß der rekursiven Definition in
+Abhängigkeit der Länge der Eingabefolgen, $n$ und $m$:
+\begin{displaymath}
+ K(n,m) = \left\{ \begin{array}{ll}
+ nm, & \mathrm{falls} \quad nm \leqq 1 \\
+ K\left(\left\lceil \frac{n}{2} \right\rceil, \left\lceil \frac{m}{2} \right\rceil\right)
+ + K\left(\left\lfloor \frac{n}{2} \right\rfloor, \left\lfloor \frac{m}{2} \right\rfloor\right)
+ + \left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor & \mathrm{falls} \quad nm > 1
+ \end{array} \right.
+\end{displaymath}
+Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
+anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
+dass $K(n,m)$ in $\mathcal{O}(N \log (N))$ enthalten ist.
+
+Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$, lässt sich die Anzahl
+der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der erste
+Rekursionsschritt der OEM-Konstruktion fügt
+$\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$
+Komparatoren ein -- einen Komparator weniger als der \emph{bitone Mischer} in
+diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer,
+$\operatorname{OEM}(\frac{n}{2}, \frac{n}{2})$ und so weiter bis
+einschließlich $\operatorname{OEM}(2, 2)$, von denen es $2, 4, \dots,
+\frac{N}{4} = 2^{\log(N)-2}$ Instanzen gibt. Insgesamt werden
+\begin{displaymath}
+ \sum_{i=0}^{\log(N)-2} 2^i = 2^{\log(N) - 1} - 1 = \frac{N}{2} - 1 = n - 1
+\end{displaymath}
+Komparatoren eingespart. Damit ergibt sich
+\begin{displaymath}
+ K\left(n = 2^{t-1}, n = 2^{t-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
+\end{displaymath}
+für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^t)$
+benötigt werden.
+
\subsubsection{Das Odd-Even-Mergesort-Netzwerk}
-Auch beim \emph{Odd-Even-Mergesort-Netzwerk} --~wie beim \emph{bitonen
-Mergesort-Netzwerk}~-- entsteht das Sortiernetzwerk aus dem {\em
-Odd-Even-Mischer} durch rekursives Anwenden auf einen Teil der Eingabe
-(üblicherweise die Hälfte der Leitungen) und anschließendes zusammenfügen.
-Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
+Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht, --~wie
+das \emph{bitonen Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
+sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die
+effizientesten Sortiernetzwerke in Bezuf auf Komparator- und Schichtzahl
+entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
+$\operatorname{OES}(n)$ aus
+$\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$,
+$\operatorname{OES}\left(\left\lfloor\frac{n}{2}\right\rfloor\right)$
+und $\operatorname{OEM}\left(\left\lceil\frac{n}{2}\right\rceil,
+\left\lfloor\frac{n}{2}\right\rfloor\right)$. Die Rekursion endet mit
+$\operatorname{OES}(1)$ und $\operatorname{OES}(0)$, die als leere
+Komparatornetzwerke definiert sind.
\begin{figure}
-\begin{center}
-\input{images/oe-mergesort-8.tex}
-\end{center}
-\caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
-sind die Instanzen von $S(4)$ (rot), die beiden \emph{Odd-Even-Mischer}
-$\mathit{OEM}(4)$ für gerade und ungerade Leitungen (blau) und die im letzten
-Rekursionsschritt hinzugefügten Komparatoren zwischen benachbarten Leitungen
-(grün).}
-\label{fig:odd_even_mergesort_08}
+ \begin{center}
+ \input{images/oe-mergesort-8.tex}
+ \end{center}
+ \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
+ sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden
+ \emph{Odd-Even-Mischer} $\operatorname{OEM}(4)$ für gerade und ungerade
+ Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
+ Komparatoren zwischen benachbarten Leitungen (grün).}
+ \label{fig:odd-even-mergesort-08}
\end{figure}
-\begin{itemize}
-\item Odd-Even-Transpositionsort
-\item Bitonic-Mergesort
-\item Odd-Even-Mergesort
-\item Pairwise sorting-network
-\end{itemize}
+In Abbildung~\ref{fig:odd-even-mergesort-08} ist das konkrete Sortiernetzwerk
+$\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven
+Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den
+\emph{Odd-Even-Mischer} für acht Leitungen dar: Die beiden blauen Blöcke sind
+die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
+die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
+
+Im Allgemeinen ist die Anzahl der Komparatoren, die vom
+\emph{Odd-Even-Mergesort-Netzwerk} verwendet wird, $k(n)$, direkt aus der
+Definition beziehungsweise der Konstruktionsanleitung abzulesen:
+\begin{displaymath}
+ k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
+ + k\left(\left\lfloor\frac{n}{2}\right\rfloor\right)
+ + K\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor\right)
+\end{displaymath}
+Eine geschlossene Form dieser Formel ist schon alleine deshalb schwierig, weil
+sie für $K(n,m)$ schwierig anzugeben ist. Es ist allerdings bekannt, dass
+$k(n)$ in $\mathcal{O}\left(n \left(\log (n)\right)^2\right)$ enthalten ist.
+
+Für den wichtigen Spezialfall, dass $n = 2^t$ eine Zweierpotenz ist, kann die
+Anzahl der Komparatoren wieder explizit angegeben werden. \textit{K.~Batcher}
+zeigt in seiner Arbeit\footnote{\todo{Referenz!}}, dass in diesem Fall
+\begin{displaymath}
+ k(n = 2^t) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
+\end{displaymath}
+gilt.
+
+% gnuplot:
+% oem(n,m) = ((n*m) <= 1) ? (n*m) : oem(ceil(.5*n), ceil(.5*m)) + oem(floor(.5*n), floor(.5*m)) + floor(.5*(n+m-1.0))
+% oem1(n) = oem(ceil(.5*n),floor(.5*n))
+% oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)
+
+%\begin{itemize}
+%\item Pairwise sorting-network
+%\end{itemize}
\section{Transformation von Sortiernetzwerken}
\subsection{Zwei Netzwerke kombinieren}
-\begin{itemize}
-\item Mit dem Bitonic-Merge
-\item Mit dem Odd-Even-Merge
-\item Nach dem Pairwise sorting-network Schema.
-\end{itemize}
+Um Sortiernetzwerke als \emph{Individuen} evolutionärer Algorithmen verwenden
+zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen
+Sortiernetzwerk zusammenzufassen.
+
+Wir haben diese Technik in den vorangegangen Abschnitten bereits verwendet,
+beispielsweise um zwei \emph{bitone Mergesort-Netzwerke} mit jeweils der
+halben Leitungszahl, $\operatorname{BS}\left(\frac{n}{2}\right)$, zu einem
+einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das
+\emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ wurde auf diese Art
+und Weise rekursiv aufgebaut.
+
+Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte
+Folgen. \emph{Wie} diese Folgen sortiert wurden, ist unerheblich. Entsprechend
+können wir beliebige Sortiernetzwerke einsetzen, um die beiden Eingabefolgen
+zu sortieren, und die Ausgaben mit einem der beschriebenen Mischer
+zusammenfügen.
+
+Beispielsweise kann man die Ausgabe von zwei \emph{bitonen
+Mergesort-Netzwerken} $\operatorname{BS}(8)$ mit je acht Leitungen mit dem
+\emph{Odd-Even-Merge} $\operatorname{OEM(8,8)}$ zu einer sortierten
+Gesamtfolge zusammenfügen. Das resultierende Sortiernetzwerk besitzt
+73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
+80~Komparatoren, $\operatorname{OES}(16)$ nur 63).
+
+Verbesserungen in der Anzahl der benötigten Komparatoren beziehungsweise der
+Schichten eines „kleinen“ Sortiernetzwerks übertragen sich direkt auf das
+resultierende Gesamtnetzwerk. Das \emph{Odd-Even-Mergesort-Netzwerk}
+$\operatorname{OES}(9)$ benötigt beispielsweise 26~Komparatoren, die in in
+neun Schichten angeordnet sind. Es sind allerdings Sortiernetzwerke mit neun
+Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten
+benötigen. Kombiniert man zwei dieser Netzwerke mit dem
+\emph{Odd-Even-Mischer} erhält man ein Sortiernetzwerk mit 18~Eingängen, das
+80~Komparatoren in 11~Schichten benötigt -- $\operatorname{OES}(18)$ benötigt
+82~Komparatoren in 13~Schichten. Damit ist das resultierende Netzwerk so
+schnell wie das Sortiernetzwerk mit 18~Eingängen, das \textit{Baddar} und
+\textit{Batcher} in ihrer Arbeit „An 11-Step Sorting Network for 18~Elements“
+vorstellen, benötigt aber 6~Komparatoren weniger.
+
+% 9 9
+% 9 18
+% 9 27
+% 9 36
+% 9 45
+% 8 53
+% 8 61
+% 7 68
+% 7 75
+% 6 81
+% 5 86
+
+Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
+ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
+sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
+Aneinanderreihung der Art „die ersten $x$~Schichten des einen, dann die
+letzten $y$~Schichten des anderen Sortiernetzwerks“ zerstören im Allgemeinen
+die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden
+Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
+nur mit exponentiellem Aufwand möglich ist.
+
+%\begin{itemize}
+%\item Mit dem Bitonic-Merge
+%\item Mit dem Odd-Even-Merge
+%\item Nach dem Pairwise sorting-network Schema.
+%\end{itemize}
\subsection{Leitungen entfernen}\label{sect:leitungen_entfernen}
Sortiernetzwerk mit $n$~Eingängen erhalten müssen.
Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
-Sortiernetzwerk mit $(n-1)$~Leitungen verkleinern, indem man eine Leitung
+Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung
„eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem
bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maxim
durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an einem der
\subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
\subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
\subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
- \caption{Eine Leitung wird aus dem {\em Odd-Even-Transpositionsort} Netzwerk
- $\textrm{OET}(8)$ entfernt: Auf der rot markierten Leitung wird $\infty$
- angelegt. Da der Wert bei jedem Komparator am unteren Ende herauskommt, ist
- der Pfad fest vorgegeben. Da die restlichen Werte trotzdem noch richtig
- sortiert werden müssen, kann dieser Pfad herausgetrennt werden. In der
- letzten Abbildung ist $\textrm{OET}(7)$ markiert.}
+ \caption{Eine Leitung wird aus dem
+ \emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(8)$ entfernt:
+ Auf der rot markierten Leitung wird $\infty$ angelegt. Da der Wert bei jedem
+ Komparator am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die
+ restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
+ Pfad herausgetrennt werden. In der letzten Abbildung ist
+ $\operatorname{OET}(7)$ markiert.}
+ \label{fig:oe-transposition-cut}
\end{figure}
Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
mit $n$~Eingängen reduzieren.
+\subsubsection{Der \textsc{SN-Evolution-Cut}-Algorithmus}
+
Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden
Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
-ein Sortiernetzwerk mit 16~Eingängen zu reduzieren sind 16~Schnitte notwendig,
+ein Sortiernetzwerk mit 16~Ein\-gängen zu reduzieren sind 16~Schnitte notwendig,
für die es bereits etwa ${3,939 \cdot 10^{13}}$ Möglichkeiten gibt. Ein
Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter
erheblichem Ressourcenaufwand möglich.
auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
Schnitt-Richtung.
-In ihrer Arbeit \textit{“Improving Bitonic Sorting by Wire Elimination”}
-zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka}, wie man einen
-bitonen Mischer, der nach Batchers Methode konstruiert wurde, durch
-systematisches Entfernen von Leitungen in einen ebenfalls bitonen Mischer mit
-der Hälfte der Leitungen transformiert. Diese alternativen Mischer sparen im
-Vergleich zu den Mischern, die nach Batchers Methode konstruiert werden,
-Komparatoren ein.
+In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka},
+wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
+durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen
+Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer
+sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert
+werden, Komparatoren ein.
Beispeilsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in
Abbildung~\ref{fig:16-ec-1277186619} zu sehen.
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-ps32.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk}
+ $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.}
+ \label{fig:16-ec-from-ps32}
+\end{figure}
+
+Betrachtet man das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619}, so
+ist keine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$
+erkennbar -- insbesondere die ersten Schichten des Netzwerks scheinen rein
+zufällig zu sein. Dies ist jedoch kein Eigenschaft des Algorithmus, sondern
+hängt insbesondere von der Eingaben. Wird \textsc{SN-Evolution-Cut}
+beispielsweise mit dem \emph{Odd-Even-Transpositionsort-Netzwerk}
+$\operatorname{OET}(n)$ und $m$~Schnitten gestartet, so ist das beste Ergebnis
+immer das $\operatorname{OET}(n-m)$-Netzwerk.
+
+Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
+$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
+Pairwise Sorting Network“ definiert. Startet man \textsc{SN-Evolution-Cut} mit
+$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man
+ein Sortiernetzwerk, dass die gleiche Anzahl an Komparatoren und Schichten hat
+wie $\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Der Algorithmus gibt
+auch nach zahlreichen Versuchen nur eines von zwei Sortiernetzwerken zurück,
+die beide sehr symmetrisch sind und eine saubere Struktur aufweisen. Eines der
+beiden Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32}
+dargestellt, das andere Sortiernetzwerk unterscheidet sich lediglich dadurch,
+dass die zweite und dritte Schicht vertauscht sind.
+
+Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht
+einsetzt und auch nicht auf einem Mischer basiert, ist der
+$\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
+Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
+den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzerke, die
+strukturell identisch zu $\operatorname{PS}(8)$ sind -- die Schichten~1 und~2
+sowie 4~und~5 sind vertauscht, was jeweils zum selben Ergebnis nach dem
+Schichtenpaar führt.
+
+Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann
+man $\operatorname{OES}(8)$ erhalten.
+
\begin{itemize}
\item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort.
\item Wie gut kann man durch wegschneiden werden?
\item Abschnitt „Optimierung der Schnitte“ hier einbauen.
\end{itemize}
-\section{Der evolutionäre Ansatz}
+\section{Der \textsc{SN-Evolution}-Algorithmus}
Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
die vorgestellten Methoden kombiniert.
Das würde mir noch einfallen$\ldots$
-%\bibliography{references}
-%\bibliographystyle{plain}
+\bibliography{references}
+\bibliographystyle{plain}
%\listoffigures
projects / diplomarbeit.git / blobdiff