% 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 ist.
\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.
zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
Ausgabe und kann entfernt werden.
+\subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
+\label{sect:anzahl_schnittmuster}
+
Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
$n-3$,~\dots Eingängen zu erzeugen. Insbesondere können wir auf diese Art und
Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
-mit $n$~Eingängen reduzieren.
+mit $n$~Eingängen reduzieren. Das Anwenden mehrerer Minimum- und
+Maximum-Schnitte bezeichnen wir als \emph{Schnittmuster}.
+
+Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
+auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
+Schnittmuster \emph{unterschiedlich} bezüglich~$S$.
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
\prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
\quad (n > m)
\end{displaymath}
-Möglichkeiten. Diese Möglichkeiten sind nicht alle unterschiedlich. Legt man
-beispielsweise das Minimum auf die unterste Leitung und das Maximum auf die
-oberste Leitung eines Standard-Sortiernetzwerks, führen beide Reihenfolgen zum
-selben Ergebnis.
+\emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
+unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung
+und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks,
+führen beide Reihenfolgen zum selben Ergebnis.
\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass
es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise
-Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnitte
-reduziert, die Menge der erreichbaren Sortiernetzwerke bleibt aber
-unverändert. Die Anzahl der möglichen „Schnittmuster“ setzt sich zusammen aus
+Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster
+reduziert, die Menge der so erzeugbaren Sortiernetzwerke bleibt aber
+unverändert. Die Anzahl der möglichen Schnittmuster setzt sich zusammen aus
der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
-Formel:
+Formel für die Anzahl der Schnittmuster:
\begin{displaymath}
2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
= 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
\quad (n > m)
\end{displaymath}
-Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden
+Die Anzahl der möglichen Schnittmuster 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,
-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.
-
-Das Programm {\sc SN-Evolution-Cut} implementiert einen evolutionären
+ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schmittmuster mit
+16~Schnitten notwendig, für das 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.
+
+Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
+als die Anzahl der möglichen Schnittmuster. Für jeden Komparator auf der
+ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
+Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
+unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
+der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die
+Werte unterscheiden.
+
+Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe
+Ausgangmuster abgebildet, weil die Position des Minimums beziehungsweise des
+Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun
+unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster
+erzeugen. In der zweiten und allen folgenden Schichten kann man diesen
+Unterschied nicht mehr erkennen. In allen sechs Fällen, in denen sich die
+Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass
+sich die Resultate auch in der ersten Schicht nicht unterscheiden.
+
+\subsubsection{Der \textsc{SN-Evolution-Cut}-Algorithmus}
+\label{sect:sn-evolution-cut}
+
+Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
-von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}.
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
+Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
+gute Schnittmuster gesucht.
+
+Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster}
+als Individuen. Um zwei Individuen zu rekombinieren werden die ersten
+$r$~Schnitte des einen Schnittmusters verwendet und die letzten
+${c-r}$~Schnitte des zweiten Schmittmusters. $r$ ist eine Zufallsvariable mit
+$0 \leqq r \leqq c$.
+
+Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
+auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
+Schnitt-Richtung.
+
+% bitones Mergesort-Netzwerk
+
+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
+konstruiert wurde. Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger
+als das bitone Mergesort-Netzwerk nach Batchers Methode. Gegenüber Batchers
+Methode sparen so konstruierte Sortiernetzwerke ${\frac{1}{4}n(\log n - 1)}$
+Komparatoren ein.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-1277186619.tex}
+ \end{center}
+ \caption{{\tt images/16-ec-1277186619.tex}: Sortiernetzwerk mit 16~Leitungen
+ und 68~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem
+ Algorithmus \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
+ $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
+ \label{fig:16-ec-1277186619}
+\end{figure}
+
+Startet man {\sc SN-Evolution-Cut} mit dem bitonen Mergesort-Netzwerk
+$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
+Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
+16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in
+Abbildung~\ref{fig:16-ec-1277186619} zu sehen.
+
+% Odd-Even-Transpositionsort-Netzwerk
+
+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 Eingabe ab. 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.
+
+\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}
+
+% Pairwise-Sorting-Netzwerk
+
+Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
+$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
+Pairwise Sorting Network“ \cite{P1992} 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)$. Eines dieser Sortiernetzwerke ist in
+Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
+
+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.
+
+\begin{displaymath}
+\textit{Eingang}_i = \left\{ \begin{array}{rl}
+ -\infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{0, 6\} \\
+ \infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{2, 4\} \\
+ ? & \quad \mathrm{sonst}
+ \end{array} \right.
+\end{displaymath}
+
+\begin{figure}
+ \begin{center}
+ \input{images/32-pairwise-cut-16-pairwise.tex}
+ \end{center}
+ \caption{PS(32) mit 16 Schnitten zu PS(16).}
+ \label{fig:ps16-from-ps32}
+\end{figure}
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-pairwise.tex}
+ \end{center}
+ \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten
+ ($\operatorname{MIN}(0,2,4,6), \operatorname{MAX}(9,11,13,15)$). Das
+ resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.}
+ \label{fig:16-pairwise}
+\end{figure}
+
+Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann
+man $\operatorname{OES}(8)$ erhalten.
+
+% Odd-Even-Mergesort-Netzwerk
+
+\todo{Schreibe noch etwas zum Odd-Even-Mergesort-Netzwerk.}
\begin{itemize}
\item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort.
\item Wie gut kann man durch wegschneiden werden?
- \item Wieviele Schnitte ergeben das selbe Netzwerk?
+ \item Wieviele Schnitte ergeben das selbe Netzwerk? Oder andersrum: Wieviele
+ unterschiedliche Netzwerke kann ich erhalten? Wieviele Nachfolger hat ein
+ Netzwerk / Knoten in der Markov-Kette?
+ \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.
Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
berücksichtigen kann, hat die folgende allgemeine Form:
\begin{equation}
- \mathit{Guete}(S) = w_{\mathrm{Basis}}
+ \operatorname{Guete}(S) = w_{\mathrm{Basis}}
+ w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
+ w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
\end{equation}
\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
\end{itemize}
-\section{Markov-Kette}
+\section{Der \textsc{SN-Markov}-Algorithmus}
-Der evolutionäre Algorithmus aus dem vorherigen Abschnitt verwendete immer
-zwei zufällige Sortiernetzwerke („Individuen“) aus einer Population. Da die
-beiden „Eltern“ zufällig und unabhängig voneinander ausgewählt werden, kann es
-vorkommen, dass das selbe Sortiernetzwerk zweimal verwendet und mit sich
-selbst kombiniert wird.
+Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
+Abschnitt verwendete immer zwei zufällige Sortiernetzwerke („Individuen“) aus
+einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander
+ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal
+verwendet und mit sich selbst kombiniert wird.
Macht man diesen Spezialfall zum Regelfall, indem man \emph{immer} das
aktuelle Netzwerk mit sich selbst kombiniert und anschließend die Hälfte aller
ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
selbst erzeugen kann.
+Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben ist die Anzahl
+(unterschiedlichen) Schnittmuster und damit die Anzahl der Nachfolger sehr
+groß. Wenn $S_0$ ein Sortiernetzwerk mit $n$~Leitungen ist, so hat $S_0$ bis
+zu
+\begin{displaymath}
+ 2^n \cdot \left( \begin{array}{c} 2n \\ n \end{array} \right)
+\end{displaymath}
+Nachfolger.
+
Der Algorithmus {\sc SN-Markov} legt auf diesem Graph einen zufälligen Weg
(englisch: \textit{random walk}) zurück. Er startet auf einem gegebenen
Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu gelangen
\section{Optimierung der Schnitte}
-Der \emph{evolution-cut}-Algorithmus nimmt ein gegebenes Sortiernetzwerk mit
-$n$~Leitungen und sucht die beste Sequenz von $c$~Min- und Max-Schnitten um
-ein ${(n-c)}$-Sortiernetzwerk zu erhalten.
-
-Bei diesem Algorithmus werden die \emph{Schnitt-Sequenzen} als Individuen
-verwendet. Eine \emph{Schnitt-Sequenz} ist eine Liste mit $c$~Schnitten, die
-jeweils durch die Start-Leitung und die Richtung \textit{Min} beziehungsweise
-\textit{Max} gegeben ist. Der Algorithmus wendet jeden Schnitt einzeln an, so
-dass eine Leitungsnummer mehrfach in einer Schnittsequenz vorkommen kann. Die
-höchste zulässige Leitungsnummer ist abhängig von der Position des Schnitts in
-der Sequenz. Der Schnitt an Position~$i$ darf höchstens die
-Leitungsnummer~${n-i-1}$ enthalten.\footnote{Die niedrigste Leitungsnummer ist
-$0$, die höchste Leitungsnummer eines $n$-Sortiernetzwerks ist $n-1$.}
-
-Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte der einen
-Schnitt-Sequenz verwendet und die letzten ${c-r}$~Schnitte der zweiten
-Sequenz. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.
-
-Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
-auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
-Schnitt-Richtung.
-
-\begin{figure}
-\begin{center}
-\input{images/16-ec-1277186619.tex}
-\end{center}
-\caption{{\tt images/16-ec-1277186619.tex}: Sortiernetzwerk mit 16~Leitungen
- und 68~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem Algorithmus
- \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(32)$ durch
- 16~Schnitte erzeugt.}
-\label{fig:16-ec-1277186619}
-\end{figure}
-
-Wendet man den \emph{evolution-cut}-Algorithmus auf das
-Bitonic-Mergesort-Netzwerk $M(n)$ an und setzt die Anzahl der Schnitte~$c$ auf
-$\frac{n}{2}$, so erhält man Sortiernetzwerke, die weniger Komparatoren
-benötigen als $M(\frac{n}{2})$.
-
-Das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619} ist entstanden,
-indem der Algorithmus \emph{evolution-cut} auf das $M(32)$-Sortiernetzwerk
-angewendet wurde. Der Algorithmus fand eine Schnitt-Sequenz aus 16~Schnitten,
-die ein Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in 10~Schichten
-erzeugt. Das $M(16)$-Sortiernetzwerk besteht aus 80~Komparatoren in
-10~Schichten.
-
-Dieses Ergebnis deckt sich mit dem Sortiernetzwerk, dass
-\emph{Moritz Mühlenthaler} und \emph{Rolf Wanka} in ihrer Veröffentlichung
-„Improving Bitonic Sorting by Wire Elimination“ vorstellen. Sie verwenden
-Schnitte, um Komparatoren beim bitonen $(n,n)$-Mischer enizusparen. Ein
-sukzessive aus optimieren Mischern aufgebautes Sortiernetzwerk spart
---~verglichen mit dem Bitonic-Mergesort-Netzwerk~-- $\frac{1}{4}n(\log n - 1)$
-Komparatoren ein. Bei einem Sortiernetzwerk mit 16~Leitungen also
-12~Komparatoren -- 68 statt 80.
+\todo{In den Abschnitt "`Leitungen entfernen"' einbauen.}
\begin{figure}
\begin{center}
\end{center}
\caption{{\tt images/32-ec-1277190372.tex}: Sortiernetzwerk mit 32~Leitungen
und 206~Komparatoren in 15~Schichten. Das Netzwerk wurde von dem Algorithmus
- \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(64)$ durch
+ \textsc{SN-Evolution-Cut} aus dem Bitonic-Mergesort-Netzwerk $BS(64)$ durch
32~Schnitte erzeugt.}
\label{fig:32-ec-1277190372}
\end{figure}
Abbildung~\ref{fig:32-ec-1277190372} zeigt ein 32-Sortiernetzwerk, dass vom
-\emph{evolution-cut}-Algorithmus aus dem $M(64)$-Netzwerk erzeugt wurde. Es
-besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als
-$M(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler
+\textsc{SN-Evolution-Cut}-Algorithmus aus dem $BS(64)$-Netzwerk erzeugt wurde.
+Es besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als
+$BS(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler
und Wankas Methode konstruiert wird. Die Anzahl der Schichten ist bei allen
Netzwerken gleich.
-\textbf{TODO:} $M(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten
+\textbf{TODO:} $BS(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten
möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$
-Komparatoren; $M(64)$: 672~Komparatoren.
+Komparatoren; $BS(64)$: 672~Komparatoren.
Schnitt-Sequenz:
MIN( 92)
Das würde mir noch einfallen$\ldots$
-%\bibliography{references}
-%\bibliographystyle{plain}
+\bibliography{references}
+\bibliographystyle{plain}
%\listoffigures
projects / diplomarbeit.git / blobdiff