-\documentclass[a4paper,10pt]{article}
+\documentclass[a4paper,11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{ngerman}
\usepackage{fancyhdr}
% 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 active minimum maximum} = [vertex,color=violet!50, fill=violet!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 active minimum maximum} = [comp,color=black!20]
+\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]
-\tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10]
+\tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10]
\maketitle
\begin{abstract}
\newpage
\tableofcontents
-\newpage
+\newpage
\section{Motivation und Einleitung}
\subsection{Motivation}\label{sect:motivation}
\subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke}
-{\em Komparatoren} sind die Bausteine, die {\em Sortiernetzwerken} zugrunde
-liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten können.
-Ausserdem besitzt ein {\em Komparator} zwei Ausgänge, die im Gegensatz zu den
-Eingängen unterscheidbar sind: Die grö"sere der beiden Zahlen wird immer auf
-dem einen, die kleinere der beiden Zahlen immer auf dem anderen Ausgang
-ausgegeben.
+\emph{Komparatoren} sind die Bausteine, die \emph{Komparatornetzwerken}
+zugrunde liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten
+können und zwei Ausgänge, auf denen die Zahlen wieder ausgegeben werden. Dabei
+sind die Ausgänge im Gegensatz zu den Eingängen unterscheidbar, da die größere
+der beiden Zahlen wird immer auf dem einen, die kleinere der beiden Zahlen
+immer auf dem anderen Ausgang ausgegeben ausgegeben wird.
-Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die
-Ausgänge von {\em Komparatoren} mit dem Eingängen anderer {\em Komparatoren}
-verbindet, erhält man ein {\em Komparatornetzwerk}.
+Kombiniert man mehrere \emph{Komparatoren} miteinander, das heißt, dass die
+Ausgänge eines Komparators mit Eingängen weiterer Komparatoren verbunden sind,
+erhält man ein {\em Komparatornetzwerk}.
\begin{figure}
\begin{center}
\end{figure}
Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
-Komparatornetzwerk aus fünf Komparatoren in der üblichen Darstellungsweise:
-Die horizontalen Linien stellen Leitungen von den Eingängen auf der linken
-Seite zu den Ausgängen auf er rechten Seite dar. Die vertikalen Pfeile
-symbolisieren die Komparatoren, die die Werte "`auf den Leitungen"'
-vergleichen und ggf. vertauschen. Nach einem Komparator befindet sich die
+\emph{Komparatornetzwerk} aus fünf Komparatoren. Insgesamt gibt es vier
+verschiedene Eingänge und vier Ausgänge. Die Ein- und Ausgänge werden durch
+eine horizontale Linie dargestellt und als \emph{Leitung} bezeichnet. Die
+\emph{Komparatoren} sind durch vertikale Pfeile dargestellt und verbinden je
+zwei verschiedene \emph{Leitungen} miteinander. Die Verbindungsstellen von
+\emph{Leitungen} und \emph{Komparatoren} sind zur besseren Übersichlichkeit
+durch schwarze Punkte symbolisiert.
+
+Auf der linken Seite befinden sich die Eingänge. Hier wird eine Zahlenfolge in
+das Netzwerk hineingegeben. Jeder Komparator vergleicht die Zahlen „auf“ den
+beiden Leitungen, die er verbindet. Nach einem Komparator befindet sich die
kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
-befindet sich auf der Leitung auf der der Pfeil seinen Ursprung hat.
-
-Komparatornetzwerke, die für jede beliebige Eingabepermutation eine
-Ausgabe erzeugen, die der Sortierung der Eingabe entspricht, heißen
-{\em Sortiernetzwerke}. Das in
+befindet sich auf der Leitung, auf der der Pfeil seinen Ursprung hat.
+
+Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
+gleichzeitig angewandt werden. Das Beispiel in
+Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
+vergleicht die zwei oberen und die zwei unteren Leitungen gleichzeitig. Eine
+Gruppe von Komparatoren, die gleichzeitig angewendet werden können, nennt man
+eine \emph{Schicht} des Komparatornetwerks. Die \emph{Verzögerung} eines
+Komparatornetzwerks ist gleichbedeutend mit der Anzahl der Schichten, in die
+sich die Komparatoren mindestens gruppieren lassen, da sie die Anzahl der
+benötigten parallelen Schritte darstellt.
+
+\emph{Komparatornetzwerke}, die für \emph{jede} Eingabefolge eine Ausgabe
+erzeugen, die der Sortierung der Eingabe entspricht, heißen
+\emph{Sortiernetzwerke}. Das in
Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
-ist kein Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ würde zur Ausgabe
-${(2, 1, 3, 4)}$ führen -- die bestehenden Sortierung wird also sogar
+ist \emph{kein} Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur
+Ausgabe ${(2, 1, 3, 4)}$ -- die bestehenden Sortierung wird also sogar
zerstört.
-Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
-{\em nicht} hat, ist mit einem gegebenen Gegenbeispiel also einfach möglich.
-Dieses Gegenbeispiel zu finden ist allerdings aufwendig.
-
-\todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein
-Netzwerk sortiert, ist doch NP-vollständig, also müsste doch das Finden eines
-Gegenbeispiels im Allgemeinen auch exponentialle Laufzeit haben..?}
-\todo{Wenn die {\em Entscheidung}, ob ein Netzwerk sortiert, NP-vollständig
-ist, müsse man dann nicht einen Zeugen für die Sortiereigenschaft angeben
-können?}
-
-\todo{$0-1$-Prinzip}
-
-Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft
-besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen
-ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle
-$2^n$~${0-1}$-Folgen sortiert.
-
-Sortiernetzwerke:
-\begin{itemize}
-\item Ein Komparator-Netzwerk ist $\ldots$
-\item Ein Komparator-Netzwerk ist ein Sortiernetzwerk, wenn $\ldots$
-\item Die Frage nach der Sortiereigenschaft ist NP-vollständig.
-\end{itemize}
+\begin{figure}
+ \begin{center}
+ \input{images/09-e2-c24-allbut1.tex}
+ \end{center}
+ \caption{Ein \emph{Komparatornetzwerk} mit neun Eingängen und
+ 24~Komparatoren, die in 8~Schichten angeordnet sind. Das Netzwerk sortiert
+ alle Eingaben, bei denen das Minimum nicht auf dem mittleren Eingang liegt.}
+ \label{fig:09-e2-c24-allbut1}
+\end{figure}
+Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft {\em
+nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich. Das
+Komparatornetzwerk wird auf das Gegenbeispiel angewendet und anschließend wird
+überprüft, ob die Ausgabe sortiert ist. Ist sie es nicht heißt das, dass es
+mindestens eine Eingabefolge gibt, die nicht sortiert wird. Entsprechend der
+Definition handelt es sich bei dem \emph{Komparatornetzwerk} folglich
+\emph{nicht} um ein \emph{Sortiernetzwerk}. Ein solches Gegenbeispiel für ein
+gegebenes Komparatornetzwerk zu finden ist nach heutigem Kenntnisstand jedoch
+nicht \emph{effizient} möglich.
+
+Beispielsweise sortiert das Komparatornetzwerk in
+Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880 möglichen
+Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4, 8, 6)$
+lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die
+Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge
+$(1, 0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt.
+
+Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein
+Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese
+Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$
+über-exponentiell schnell, so dass ein Ausprobieren aller möglichen
+Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen
+ist.\footnote{1.307.674.368.000 Permutationen}
+
+Glücklicherweise reicht es aus, alle möglichen 0-1-Folgen zu überprüfen, wie
+\textit{Donald~E. Knuth} in \cite{KNUTH} zeigt. Die Beweisidee ist folgende:
+Angenommen ein Komparatornetzwerk sortiert alle 0-1-Folgen und es gibt eine
+Permutation $E = (e_0, \dots, e_{n-1})$ beliebiger Zahlen, die nicht sortiert
+wird. Die Ausgabefolge sei $A = (a_0, \dots, a_{n-1})$. Sei $i$ eine Position
+in der Ausgabe, die die Sortierbedingung verletzt:
+\begin{displaymath}
+ a_0 \leqq a_1 \leqq \dots \leqq a_{i-1} > a_i \dots
+\end{displaymath}
+Die Eingabe kann mittels
+\begin{displaymath}
+ \hat{e}_j = \left\{
+ \begin{array}{cl}
+ 0 & e_j \leqq a_i \\
+ 1 & e_j > a_i
+ \end{array} \right.
+\end{displaymath}
+auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme von
+Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das
+Verhalten jedes einzelnen Komparators nicht, so dass die Annahme auf einen
+Widerspruch geführt wird.
+
+Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
+Komplexitätsklasse
+$\mathcal{O}\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
+ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\mathcal{O}(2^n)$
+verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
+schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
+ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,
+sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für
+aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung
+eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa
+4,3~Millarden Tests notwendig, die einen Rechner durchaus mehrere Minuten
+beschäftigen.
\subsubsection{Evolutionäre Algorithmen}
verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
-werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em
+werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
Gütefunktion}.
Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
-es oft einfach ist {\em irgendeine} Lösung anzugeben. Zum anderen muss eine
-Methode für die Rekombination existieren. Das insbesondere dann problematisch
-wenn {\em Nebenbedingungen} eingehalten werden müssen.
-
-\begin{itemize}
-\item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$
-\item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die
-Mutation \textit{(vermutlich)} nicht (effizient) möglich.
-\end{itemize}
+es oft einfach ist {\em irgendeine} Lösung anzugeben. Die angegebenen
+Algorithmen verwenden als einfache, initiale Lösung häufig das
+\emph{Odd-Even-Transpositionsort}-Netzwerk, das in
+Abschnitt~\ref{sect:odd_even_transpositionsort} beschrieben wird. Zum anderen
+muss eine Methode für die Rekombination existieren. Das ist insbesondere dann
+problematisch, wenn {\em Nebenbedingungen} eingehalten werden müssen.
+
+Beim Aussuchen von zufälligen Lösungen aus der Population, der
+\emph{Selektion}, werden gute Lösungen bevorzugt. Wie sehr diese Lösungen
+bevorzugt werden, hat einen starken Einfluss auf das Verhalten des
+Algorithmus. Werden gute Lösungen stark bevorzugt, konvergiert der Algorithmus
+schnell gegen ein (lokales) Optimum. Dieses \textit{Exploitation} (Englisch
+für „Ausnutzung“) genannte Verhalten sorgt dafür, dass sich der Algorithmus
+schnell auf eine Lösung festlegt und andere, möglicherweise bessere lokale
+Optima nicht mehr findet. Werden gute Lösungen hingegen nur wenig bevorzugt,
+erforscht der Algorithmus den Lösungsraum in viele Richtungen. Dieses
+\textit{Exploration} (Englisch für „Erforschung“) genannte Verhalten sorgt
+zwar dafür, dass der Algorithmus langsamer auf ein Optimum zusteuert, dafür
+findet er aber in der Regel bessere Lösungen.
+
+Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
+Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
+nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
+eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
+beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
+zwischen verschiedenen Leitungszahlen stark unterscheiden.
+
+Die \textit{Exploration} kann von einem weiteren Mechanismus unterstützt
+werden, der ebenfalls der Evolutionslehre entliehen ist, der \emph{Mutation}.
+Dabei werden Lösungen zufällig verändert, so dass auch andere Lösungen „in der
+Nähe“ von direkten Nachfolgern erreicht werden können. Das hilft insbesondere
+bei der intensiven Suche in der Nähe eines lokalen Optimums aber auch beim
+„Ausbrechen“ und finden noch besserer Lösungen.
+
+Bei \emph{Sortiernetzwerken} ist eine \emph{Mutation} leider immer damit
+verbunden, dass anschließend die Sortiereigenschaft des resultierenden
+\emph{Komparatornetzwerks} wieder überprüft werden muss, da selbst das
+Hinzufügen eines zufälligen Komparators diese Eigenschaft zerstören kann. Beim
+Suchen möglichst effizienter Netzwerke ist natürlich das zufällige Entfernen
+von Komparatoren interessanter, was die Sortiereigenschaft sehr oft aufhebt.
+
+Die im Folgenden beschriebenen Algorithmen mutieren (verändern) daher nicht
+die \emph{Sortiernetzwerke} selbst, sondern verzichten auf Mutation oder
+mutieren lediglich Transformationen von Sortiernetzwerken, die die
+Sortiereigenschaft erhält. Transformationen von Sortiernetzwerken werden in
+Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der Mutation
+einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
+\newpage
\section{Bekannte konstruktive Sortiernetzwerke}
+\label{sect:konstruktive_netzwerke}
Ü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 möglichst 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-Transposi\-tionsort-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 $n = 2^t$ eine Zweierpotenz ist.
+Es ist jedoch möglich das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
\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.
\end{figure}
Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
-${m = \frac{n}{2}}$~Elementen, ${u_0, u_1, \ldots, u_{m-1}}$ und
-${v_0, v_1, \ldots, v_{m-1}}$. Die Folge der $u_i$ sei aufsteigend sortiert,
-die Folge der $v_i$ sei absteigend sortiert:
+${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und
+$V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend
+sortiert, die Folge $V$ sei absteigend sortiert:
\begin{eqnarray}
u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
> 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.
-
-\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).
+"`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.
+
+\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}
+\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.
+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}.~\cite{KNUTH}
-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
-$U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ -- die Einsen verhalten
+$U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ --~die Einsen verhalten
sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen
$W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu:
\begin{eqnarray}
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 {\em Odd-Even-Mergesort-Netzwerk} -- wie beim {\em bitonen
-Mergesort-Netzwerk} -- entsteht das Sortiernetzwerk aus dem {\em
-Odd-Even-Mischer} durch resursives 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{bitone 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.}
-\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{Kenneth
+Batcher} zeigt in~\cite{B1968}, 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}
+\newpage
\section{Transformation von Sortiernetzwerken}
+\label{sect:tranformation}
-\begin{itemize}
-\item Komprimieren (Alle Komparatoren so früh wie möglich anwenden).
-\item Normalisieren (Transformation zu Standard-Sortiernetzwerken).
-\end{itemize}
+\subsection{Komprimieren}
-\subsection{Zwei Netzwerke kombinieren}
+\todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}
-\begin{itemize}
-\item Mit dem Bitonic-Merge
-\item Mit dem Odd-Even-Merge
-\item Nach dem Pairwise sorting-network Schema.
-\end{itemize}
+Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
+gleichzeitig ausgewertet werden, wie bereits in
+Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
+\emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
+von \emph{Schichten} verstanden.
-\subsection{Leitungen entfernen}
+Diese Anzahl ist insbesondere beim automatisierten Bewerten von
+Komparatornetzwerken interessant. \dots
+
+\subsection{Normalisieren}
+
+\begin{figure}
+ \centering
+ \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
+ \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
+ \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
+ transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
+ intuitiven Konstruktion und die normalisierte Variante.}
+ \label{fig:beispiel_normalisieren}
+\end{figure}
+
+Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
+ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
+zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
+transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis})
+einen Algorithmus an.
+
+Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
+bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
+zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
+Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
+die unter und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei
+Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist.
+In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven
+Definition.
+
+In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
+Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche
+Richtung. Statt dem typischen "`Treppenmuster"' sind abwechselnd das Treppen-
+und das Trichtermuster zu sehen.
+
+\subsection{Zwei Netzwerke kombinieren}
+
+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{Sherenaz~W.
+Al-Haj Baddar} und \textit{Kenneth~E. Batcher} in ihrer Arbeit „An 11-Step
+Sorting Network for 18~Elements“~\cite{BB2009} 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}
+
+Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von
+\emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
+ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen
+beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass
+sich die Anzahl der Eingänge nicht verändert. Das heißt, dass wir wieder ein
+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
+„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
+„Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten Index.
+Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und welche
+dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum jeden
+Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
+Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
+das {\em Odd-Even-Transpositionsort-Netzwerk}.
\begin{figure}
\centering
\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.
+ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt
+haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
+Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
+zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
+ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
+das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
+auf die keine Komparatoren mehr berührt
+(Abbildung~\ref{fig:oe-transposition-cut1}).
+
+Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
+Komparatornetzwerk immernoch sortiert werden: Wir haben lediglich die Position
+des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss die
+Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum liegt.
+Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme
+auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage
+getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
+mit $(n-1)$~Elementen darstellen.
+
+Wenn wir die Minimum- beziehungsweise Maximum-Leitung entfernen
+(Abbildung~\ref{fig:oe-transposition-cut2}), bleibt das Sortiernetzwerk für
+$(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung ein Minimum oder ein
+Maximum angenommen wird, bezeichnen wir das eliminieren einer Leitung als
+\emph{Minimum-Schnitt} beziehungsweise \emph{Maximum-Schnitt}.
+
+Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
+Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
+markierten Komparatoren wurden verschoben, so dass sich eine kompaktere
+Darstellung ergibt. Ausserdem ist das
+{\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der
+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 auf diese Art und
+Weise einen Sortiernetzwerke mit $2n$~Eingängen wieder auf Sortiernetzwerke
+mit $n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die
+nacheinander angewendet ein $n$-Sortiernetzwerk auf ein
+${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als
+\emph{$k$-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
+auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
+ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
+ergeben sich insgesamt
+\begin{equation}\label{eqn:anzahl_schnittmuster}
+ \prod_{i=n}^{1+n-k} 2i = 2^k \frac{n!}{(n-k)!}
+ \quad (n > m)
+\end{equation}
+\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 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, $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen
+Minimum-~/ Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl
+der möglichen Schnittmuster:
+\begin{displaymath}
+ 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
+ = 2^{k} \cdot \frac{n!}{k! (n-k)!}
+ = 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!}
+ \quad (1 \leqq k < n)
+\end{displaymath}
+
+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, 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.
+
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 360 216,width=15cm]{images/count-cuts-16.pdf}
+ \end{center}
+ \caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch
+ 8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
+ $\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der
+ unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das
+ \emph{Odd-Even-Mergesort-Netzwerk}, 4973 für das \emph{bitone
+ Mergesort-Netzwerk} und 18764 für das \emph{Pairwise-Sorting-Netzwerk}.}
+ \label{fig:count-cuts-16}
+\end{figure}
+
+Alleine durch Betrachten der ersten Schicht von Komparatoren konnte die Anzahl
+der \emph{unterschiedlichen} Schnittmuster auf höchstens $\frac{2}{3}$ der
+\emph{möglichen} Schnittmuster reduziert werden. Um die Anzahl der
+\emph{unterschiedlichen} Schnittmuster experimentell zu ermitteln, wurden je
+eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke
+$\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$
+angewandt. Anschließend wurde mithilfe einer Hashtabelle überprüft, ob das
+resultierende Sortiernetzwerk schon von einem \emph{äquivalenten}
+Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk noch nicht in der
+Hashtabelle enthalten war, wurde der Zähler für unterschiedliche Schnittmuster
+erhöht und das Sortiernetzwerk eingefügt.
+
+Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
+\emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen
+Schnittmuster auf. Klar zu sehen ist, dass sich die Anzahl der erzeugten
+Sortiernetzwerke nach $500.000$~Iterationen nur noch gering verändert und der
+Wert nach $1.000.000$~Iterationen allem Anschein nach dem Endwert schon sehr
+nahe ist.
+
+Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der
+Formel~\ref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen Schnittmuster
+führen aber nur zu wenigen \emph{unterschiedlichen} Sortiernetzwerken: 3519
+($\approx 0,1\%$) im Fall des \emph{Odd-Even-Mergesort-Netzwerks}, 4973
+($\approx 0,15\%$) beim \emph{bitonen Mergesort-Netzwerk} und 18764 ($\approx
+0,57\%$) beim \emph{Pairwise-Sorting-Netzwerk}. Zwar ist es möglich, dass mehr
+Iterationen die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt.
+Die Graphen in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der
+Annahme, dass die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
+vernachlässigbar klein ist.
+
+Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
+Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar.
+Die Hashtabelle benötigt mehr Arbeitsspeicher als in derzeitigen Rechnern
+vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für
+„kleine“ x-Werte verlässt.
+
+Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
+können, kann man sich einer stochastischen Methode bedienen, der sogenannten
+\emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von
+$k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
+zufällig erzeugt und überprüft, ob sie sich in der Menge~$S$ enthalten sind.
+Unter der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in
+$S$ enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der
+unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der
+unterschiedlichen Schnittmuster abschätzen.
+
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
+ \end{center}
+ \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der
+ \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und
+ $\operatorname{BS}(32)$.}
+ \label{fig:collisions-10000-1000000-32}
+\end{figure}
+
+In Abbildung~\ref{fig:collisions-10000-1000000-32} ist das Ergebnis des
+Monte-Carlo-Algorithmus für 16-Schnittmuster zu sehen, die auf
+$\operatorname{OES}(32)$ und $\operatorname{BS}(32)$ angewandt wurden: Von
+jedem Sortiernetzwerk wurden zunächst eine Menge~$S$ von 10.000
+\emph{unterschiedlichen} Schnittmustern erzeugt. Anschließend wurden 1.000.000
+zufällige Schnittmuster erzeugt und der Anteil der zufälligen Schnittmuster,
+die \emph{äquivalent} zu einem in~$S$ enthalten Schnittmuster sind, berechnet.
+Für $\operatorname{OES}(32)$ war dieser Anteil etwa $0,19 \%$, für
+$\operatorname{BS}(32)$ etwa $0,29 \%$. Das ergibt eine Abschätzung von $5,2
+\cdot 10^6$ unterschiedlichen Schnittmustern für $\operatorname{OES}(32)$ und
+$3,4 \cdot 10^6$ für $\operatorname{BS}(32)$.
+
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf}
+ \end{center}
+ \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der
+ \emph{Monte-Carlo-Methode} für $\operatorname{PS}(32)$. 385 von 1.000.000
+ zufälligen Schnittmustern waren äquivalent zu einem Schnittmuster in einer
+ Menge von 100.000. Daraus ergibt sich eine Schätzung von $2,6 \cdot 10^8$
+ unterschiedlichen Schnittmustern.}
+ \label{fig:collisions-100000-1000000-32-ps}
+\end{figure}
+
+Im vorherigen Abschnitt wurde das \emph{Pairwise-Sorting-Netzwerk}
+$\operatorname{PS}(32)$ nicht betrachtet, da es für dieses Netzwerk viel mehr
+unterschiedliche 16-Schnittmuster gibt als für $\operatorname{OES}(32)$ und
+$\operatorname{BS}(32)$. In Anbetracht der Tatsache, dass die Anzahl der
+unterschiedlichen 8-Schnittmuster für $\operatorname{PS}(16)$ in
+Abbildung~\ref{fig:count-cuts-16} bereits mehr als dreimal größer war als die
+Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$,
+ist dieser Umstand wenig verwunderlich. In einem kombinierten Graphen hätte
+man keine Details mehr erkennen können. Aufgrund der hohen Anzahl
+unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit
+$\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedilchen
+Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
+Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent
+sind. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$
+unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den
+vorherigen Sortiernetzwerken, aber immernoch fünf Zehnerpotenzen kleiner als
+die Anzahl der \emph{möglichen} Schnittmuster.
+
+\newpage
+\section{Der \textsc{SN-Evolution}-Algorithmus}
+
+Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
+Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
+(Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
+(Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
+Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
+in Abschnitt~\ref{sect:bewertung} behandelt.
+
+\subsection{Bewertungsfunktion}\label{sect:bewertung}
+
+Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
+{\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
+die bei Sortiernetzwerken verfolgt werden können:
\begin{itemize}
-\item Min-Richtung
-\item Max-Richtung
+ \item Möglichst wenige Komparatoren („billig“)
+ \item Möglichst wenige Schichten („schnell“)
\end{itemize}
-\section{Der evolutionäre Ansatz}
+Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
+billigste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
+in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
+9~Schichten.
+
+Eine Gütefunktion, die die beiden Ziele "`billig"' und "`schnell"'
+berücksichtigen kann, hat die folgende allgemeine Form:
+\begin{equation}
+ \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}
+Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
+dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
+gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
+Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
+jegliche Ergebnisse sind dann rein zufälliger Natur.\footnote{Dass dies nicht
+so schlecht ist wie man intuitiv vermuten könnte, zeigt der
+\textsc{SN-Markov}-Algorithmus in Abschnitt~\ref{sect:markov}.}
+
+Da möglichst billige und schnelle Sortiernetzwerke gefunden werden sollen, ist
+ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert. Das
+heißt, dass das Ziel von \textsc{SN-Evolution} ist, $\operatorname{Guete}(S)$
+zu \emph{minimieren}.
+
+Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
+genommen werden. Ist er groß, wird der relative Unterschied der Güten
+verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
+gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
+klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
+Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
+Exploitation}, das Finden (lokaler) Optima, bevorzugt.
+
+Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
+der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
+Lösungen findet oder sich in \emph{lokalen} Optima verrennt. Leider gibt es
+kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
+Leitungszahlen und Mischer-Typen experimentiert werden muss.
+
+\subsection{Selektion}
+
+Die \emph{Selektion} sorgt dafür, dass bessere Individuen eine größere
+Wahrscheinlichkeit haben, zur nächsten Generation beizutragen. Diese
+Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für das
+Streben des Algorithmus nach besseren Lösungen.
+
+Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint,
+ist es sehr häufig, dass die \emph{Exploitation} überhand gewinnt und der
+Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert.
+
+Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von
+Pseudocode wie folgt beschreiben:
+\begin{verbatim}
+Guetesumme := 0
+Auswahl := (leer)
+
+fuer jedes Individuum in Population
+{
+ reziproke Guete := 1.0 / Guete(Individuum)
+ Wahrscheinlichkeit P := reziproke Guete / (reziproke Guete + Guetesumme)
+ Guetesumme := Guetesumme + reziproke Guete
+
+ mit Wahrscheinlichkeit P
+ {
+ Auswahl := Individuum
+ }
+}
+gebe Auswahl zurueck
+\end{verbatim}
+
+\subsection{Rekombination}
+
+Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
+einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
+den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
+{\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
+beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
+Anschließend entfernen wir zufällig $n$~Leitungen wie in
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
+
+Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
+erhält.
+
+\subsection{Mutation}
+
+Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine Mutation
+--~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
+Sortiernetzwerk zufällig zu verändern aber trotzdem die Sortiereigenschaft zu
+erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
+Eigenschaft zerstören.
+
+Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
+Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
+Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
+Ausprobieren aller $2^n$~Bitmuster.
+
+Um das Potenzial einer Mutation abzuschätzen habe ich in den evolutionären
+Algorithmus eine Überprüfung eingebaut. Unmittelbar vor dem Einfügen in die
+Population überprüft das Programm die Notwendigkeit jedes einzelnen
+Komparators. Dazu wurde nacheinander jeder Komparator entfernt und überprüft,
+ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt.
\begin{itemize}
\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
\begin{center}
\input{images/08-e2-1237993371.tex}
\end{center}
-\caption{\tt images/08-e2-1237993371.tex}
+\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
\label{fig:08-e2-1237993371}
\end{figure}
\begin{center}
\input{images/09-e2-1237997073.tex}
\end{center}
-\caption{\tt images/09-e2-1237997073.tex}
+\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
\label{fig:09-e2-1237997073}
\end{figure}
\begin{center}
\input{images/09-e2-1237999719.tex}
\end{center}
-\caption{\tt images/09-e2-1237999719.tex}
+\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten}
\label{fig:09-e2-1237999719}
\end{figure}
+\begin{figure}
+\begin{center}
+\input{images/10-e2-1239014566.tex}
+\end{center}
+\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
+\label{fig:10-e2-1239014566}
+\end{figure}
+
\subsection{Güte}
\begin{itemize}
-\item So gut kann man mindestens werden \em{($\rightarrow$ Bitonic-Mergesort,
-vermute ich)}.
+\item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}.
\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
+\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
\end{itemize}
-\subsection{Vom evolutionären Algorithmus zu einer Markov-Kette}
+%\input{shmoo-aequivalenz.tex}
+
+\newpage
+\section{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}. 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.
+
+\subsection{Versuche mit dem bitonen 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-from-bs32.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort-Netzwerk}
+ $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
+ \label{fig:16-ec-from-bs32}
+\end{figure}
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-bs32-normalized.tex}
+ \end{center}
+ \caption{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-from-bs32-normalized}
+\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 den
+Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized}
+zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$
+und das
+${\operatorname{MIN}(0,5,9,11,15,17,20,22,26,29,30)}$-${\operatorname{MAX}(2,4,13,19,24)}$-Schnittmuster,
+das durch \textsc{SN-Evolution-Cut} gefunden wurde.
+Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk
+nachdem das Schnittmuster angewandt und das Netzwerk normalisiert wurde. Eine
+Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist in
+diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten des
+Netzwerks scheinen rein zufällig zu sein.
+
+\begin{figure}
+ % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX
+ % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX
+ % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX
+ % 63:MAX
+ \begin{center}
+ \input{images/32-ec-from-bs64.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in
+ 15~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
+ $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige
+ Schnittmuster ist
+ $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$,
+ $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37,
+ 40, 43, 47, 48, 49, 55, 56, 60, 63)$.}
+ \label{fig:32-ec-from-bs64}
+\end{figure}
+
+Das Ergebnis von \textit{Mühlenthaler} von \textit{Wanka}, die den bitonen
+Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk
+konstruiert haben, kann demnach auch erreicht werden, wenn
+$\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen
+Größen, beispielsweise wenn man $\operatorname{BS}(64)$ auf ein
+32-Sortiernetzwerk reduziert, kann das Ergebnis sogar noch übertroffen werden,
+wie in Abbildung~\ref{fig:32-ec-from-bs64} zu sehen: Ein nach Batchers Methode
+konstruiertes Sortiernetzwerk benötigt 240~Komparatoren, ein aus den
+optimierten Mischern aufgebautes Netzwerk verbessert die Kosten auf
+208~Komparatoren. Das in Abbildung~\ref{fig:32-ec-from-bs64} dargestellte
+Sortiernetzwerk benötigt lediglich 206~Komparatoren. Die Komparatoren aller
+dieser Netzwerke können in 15~Schichten angeordnet werden, so dass die
+Verzögerung dieser Sortiernetzwerke gleich ist.
+
+Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
+unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
+gute Schnittmuster anzugeben.
+
+Entscheidend für das Ergebnis eines Schnittmusters scheint beim bitonen
+Mergesort-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
+Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
+Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
+ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
+ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
+die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks
+leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und
+der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden.
+
+Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur
+haben, 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}
+
+\subsection{Versuche mit dem 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 -- lediglich die
+Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
+
+\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.
+
+\subsection{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
+
+\todo{Schreibe noch etwas zum Odd-Even-Mergesort-Netzwerk.}
\begin{itemize}
-\item Kombiniere immer das aktuelle Netzwerk mit sich selbst.
-\item Kann die Mindestgüte immernoch erreicht werden? ({\em Ich denke schon.})
-\item Anzahl der erreichbaren Sortiernetzwerke.
+ \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? 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}
+\newpage
+\section{Der \textsc{SN-Markov}-Algorithmus}
+\label{sect:markov}
+
+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
+Leitungen eliminiert, lassen sich einige interessante Beobachtungen anstellen.
+Netzwerke, die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von
+$S_0$ mit sich selbst und anschließendem Eliminieren der Hälfte der Leitungen
+hervorgehen können, heißen \emph{Nachfolger} von $S_0$.
+
+Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
+(gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
+Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
+Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von
+$S_0$ 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
+(unterschiedlicher) 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 Nachfolger-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, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich
+selbst und erhält so einen zufälligen Nachfolger.
+
+\begin{itemize}
+ \item $n \leftarrow \mathrm{Input}$
+ \item \texttt{while} \textit{true}
+ \begin{itemize}
+ \item $n \leftarrow \operatorname{recombine} (n, n)$
+ \end{itemize}
+\end{itemize}
+
+\begin{itemize}
+ \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
+ \item Anzahl der erreichbaren Sortiernetzwerke.
+ \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen
+ Netzwerke. (Abbildung~\ref{fig:markov-comparators-16})
+\end{itemize}
+
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf}
+ \end{center}
+ \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen),
+ die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
+ \emph{Gamma-Verteilung} $f(x - 40)$ mit $k = 8,267$ und $\theta = 0,962$.}
+ \label{fig:markov-comparators-12}
+\end{figure}
+
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-14-pct.pdf}
+ \end{center}
+ \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen),
+ die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
+ \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.}
+ \label{fig:markov-comparators-14}
+\end{figure}
+
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16-pct.pdf}
+ \end{center}
+ \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen),
+ die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
+ \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.}
+ \label{fig:markov-comparators-16}
+\end{figure}
+
+\newpage
\section{Empirische Beobachtungen}
\begin{itemize}
\item $\ldots$
\end{itemize}
+\newpage
\section{Ausblick}
Das würde mir noch einfallen$\ldots$
-%\bibliography{references}
-%\bibliographystyle{plain}
+\newpage
+\section{Implementierung}
+
+So habe ich die ganzen Versuche durchgeführt.
+
+\newpage
+\bibliography{references}
+\bibliographystyle{plain}
%\listoffigures
projects / diplomarbeit.git / blobdiff