\usepackage{subfigure}
\usepackage{icomma}
+\usepackage{tikz}
+\usetikzlibrary{arrows,shapes}
+
% Fuer mathtoolsset
\usepackage{mathtools}
-\geometry{paper=a4paper,margin=25mm}
+\geometry{paper=a4paper,margin=30mm}
\pagestyle{fancy}
%\fancyhf{}
\begin{document}
+\tikzstyle{vertex} = [circle,draw,thick,fill=black,minimum size=5,inner sep=0pt]
+\tikzstyle{comp} = [draw,thick,-]
+\tikzstyle{compup} = [draw,thick,->]
+\tikzstyle{compdown} = [draw,thick,<-]
+\tikzstyle{edge} = [draw,thick,-]
+\tikzstyle{diredge} = [draw,thick,->]
+\tikzstyle{prob} = [font=\tiny]
+
+\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]
+
\maketitle
\begin{abstract}
-Dies ist der Abstract.
+Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
+vorgestellt (Off-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
+Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
+Evolutionäre Algorithmen werden beschrieben und ein evolutionärer
+Algorithmus für die Optimierung von Sortiernetzwerken wird angegeben.
+Die mindestens von diesem Algorithmus erreichte Güte wird angegeben und die
+Transformation zu einer Markov-Kette wird gezeigt. {\em Natürlich: So fern ich
+das hinbekomme bzw. Recht behalte.}
\end{abstract}
\newpage
\section{Motivation und Einleitung}
-\subsection{Motivation}
+\subsection{Motivation}\label{sect:motivation}
+
+\begin{itemize}
+\item Sortiernetzwerke sind toll, weil $\ldots$
+\item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
+\item Bisher noch kein evolutionärer Algorithmus zur automatischen
+ Optimierung von Sortiernetzwerken bekannt. \textit{(Glaube ich zumindest.)}
+\end{itemize}
+
+\subsection{Einleitung}\label{sect:einleitung}
+
+\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.
+
+Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die
+Ausgänge von Komparatoren mit dem Eingängen anderer Komparatoren verbindet,
+erhält man ein {\em Komparatornetzwerk}.
+
+\begin{figure}
+\begin{center}
+\input{images/einfaches_komparatornetzwerk.tex}
+\end{center}
+\caption{Einfaches Komparatornetzwerk mit vier Ein- bzw. Ausgängen, bestehend
+aus 5~Komparatoren.}
+\label{fig:einfaches_komparatornetzwerk}
+\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
+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.
+
+Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
+gleichzeitig angewandt werden. Das Beispiel in
+Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
+vergleicht in einem ersten Schritt 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.
+
+Komparatornetzwerke, die für jede beliebige Eingabepermutation eine
+Ausgabe erzeugen, die der Sortierung der Eingabe entspricht, heißen
+{\em 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
+zerstört.
+
+Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
+{\em nicht} hat, ist mit einem gegebenen Gegenbeispiel 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}
+
+\subsubsection{Evolutionäre Algorithmen}
+
+Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
+entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
+$NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte
+sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$
+liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese
+Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese
+Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer
+Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit
+praktikablen Zeitkonstanten gefunden werden.
+
+Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
+die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus
+zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser
+Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
+beispielsweise immitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
+auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
+
+Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
+ist es, bestehende Lösungen zu neuen, unter Umständen besseren Lösungen zu
+kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
+Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem häufig
+als {\em Individuum} bezeichnet.
+
+Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
+bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen
+ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
+Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
+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
+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}
+
+\section{Bekannte konstruktive Sortiernetzwerke}
+
+Übersicht über bekannte konstruktive Sortiernetzwerke.
+
+\subsection{Odd-Even-Transpositionsort}
+\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
+${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}
+\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!}
+
+\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}
+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
+(Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein
+darf.
+
+\begin{figure}
+ \centering
+ \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}}
+ \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}}
+ \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}}
+ \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}}
+ \caption{Beispiele bitoner Folgen.}
+ \label{fig:beispiel-biton}
+\end{figure}
+
+\begin{figure}
+ \centering
+ \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
+ \qquad
+ \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
+ \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
+ aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
+ der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
+ resultierenden Teilfolgen sind wiederum biton.}
+ \label{fig:bitonic-merge-schema}
+\end{figure}
+
+Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
+${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}
+\end{eqnarray}
+Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen
+Positionen verglichen und ggf. vertauscht:
+\begin{equation}
+u_i \longleftrightarrow v_i, \quad 0 \leqq i < m
+\end{equation}
+Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die
+durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass
+Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$
+gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+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).
+
+
+
+%\begin{figure}
+%\begin{center}
+%\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
+%\end{center}
+%\caption{Rekursiver Aufbau von $S(n)$: Es besteht aus zwei Instanzen von
+%$S(n/2)$ und dem Mischer $M(n)$.}
+%\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}
+
+Obwohl der Name ähnlich klingt, haben \emph{Odd-Even-Mergesort} (OEM) und
+\emph{Odd-Even-Transposition\-sort} (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.
+
+\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 {\em 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
+$W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
+\begin{equation}
+w_i = \left\{ \begin{array}{ll}
+ u_i, & i < n \\
+ v_{i-n}, & i \geqq n
+ \end{array} \right.,
+ \quad 0 \leqq i < N
+\end{equation}
+
+\begin{figure}
+ \begin{center}
+ \input{images/oe-merge.tex}
+ \end{center}
+ \caption{Schematischer Aufbau des {\em Odd-Even} Mischers. Im Vergleich zum
+ bitonen Mischer für Acht kommt dieses Schema mit einem Komparator weniger
+ aus. Der Effekt wird duch den rekursiven Aufbau noch verstärkt.}
+ \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.
+\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) \\
+ V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\
+ V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
+\end{eqnarray}
+
+Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die
+ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden
+rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am
+Ausgang der Mischer die Folgen
+\begin{eqnarray}
+ W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
+ W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
+\end{eqnarray}
+ergeben.
+
+Anschließend werden die Komparatoren zwischen benachbarten Leitungen
+hinzugefügt,
+\begin{equation}
+ w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
+\end{equation}
+die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em
+Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}.
+
+Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
+Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
+entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
+offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
+Aufbau lauten:
+\begin{itemize}
+ \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
+ \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
+ einzelnen Komparator.
+\end{itemize}
+
+Dass die resultierende Folge sortiert ist, lässt sich mit dem
+{\em 0-1-Prinzip} leicht 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
+sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen
+$W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu:
+\begin{eqnarray}
+ \left|W_{\textrm{gerade}}\right|_0
+ &=& \left|U_{\textrm{gerade}}\right|_0
+ + \left|V_{\textrm{gerade}}\right|_0
+ = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
+ + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
+ \left|W_{\textrm{ungerade}}\right|_0
+ &=& \left|U_{\textrm{ungerade}}\right|_0
+ + \left|V_{\textrm{ungerade}}\right|_0
+ = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
+ + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
+\end{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.
+
+\begin{figure}
+ \centering
+ \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
+ \qquad
+ \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
+ \qquad
+ \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
+ \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
+ kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der
+ Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
+ letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
+ sortiert ist.}
+ \label{fig:oe-post-recursive}
+\end{figure}
+
+\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.
+
+\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}
+\end{figure}
+
+\begin{itemize}
+\item Odd-Even-Transpositionsort
+\item Bitonic-Mergesort
+\item Odd-Even-Mergesort
+\item Pairwise sorting-network
+\end{itemize}
+
+\section{Transformation von Sortiernetzwerken}
+
+\subsection{Komprimieren}
+
+\todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}
+
+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.
+
+Diese Anzahl ist insbesondere beim automatisierten Bewerten von
+Komparatornetzwerken interessant. \dots
+
+\subsection{Normalisieren}
-Das habe ich gemacht, bzw. darum habe ich das gemacht.
+\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}
-\subsection{Einleitung}\label{sect:introduction}
+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.
-Das sind Sortiernetzwerke und so.
+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.
-\section{Die Algorithmen}
+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}
+
+\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[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
+ \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.}
+\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.
+
+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.
+
+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 $m$-Sortiernetzwerk zu reduzieren, ergeben
+sich insgesamt
+\begin{displaymath}
+ \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.
+
+\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
+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:
+\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!}
+ = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!}
+ \quad (n > m)
+\end{displaymath}
+
+Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden
+Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
+ein Sortiernetzwerk mit 16~Ein\-gängen zu reduzieren sind 16~Schnitte notwendig,
+für die es bereits etwa ${3,939 \cdot 10^{13}}$ Möglichkeiten gibt. Ein
+Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter
+erheblichem Ressourcenaufwand möglich.
+
+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{Schnitt-Sequenzen} als Individuen. 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.
+
+In ihrer Arbeit \textit{“Improving Bitonic Sorting by Wire Elimination”}
+zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka}, wie man einen
+bitonen Mischer, der nach Batchers Methode konstruiert wurde, durch
+systematisches Entfernen von Leitungen in einen ebenfalls bitonen Mischer mit
+der Hälfte der Leitungen transformiert. Diese alternativen Mischer sparen im
+Vergleich zu den Mischern, die nach Batchers Methode konstruiert werden,
+Komparatoren ein.
+
+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.
+
+\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 Abschnitt „Optimierung der Schnitte“ hier einbauen.
+\end{itemize}
+
+\section{Der evolutionäre Ansatz}
+
+Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
+die vorgestellten Methoden kombiniert.
+
+\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 interessant sind:
+\begin{itemize}
+ \item Möglichst wenige Komparatoren ("`klein"')
+ \item Möglichst wenige Schichten ("`schnell"')
+\end{itemize}
+
+Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
+kleinste 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 "`klein"' und "`schnell"'
+berücksichtigen kann, hat die folgende allgemeine Form:
+\begin{equation}
+ \mathit{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.
+
+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.
+
+\subsection{Selektion}
...
-\subsection{Ausblick}
+\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
+Schichten, kobiniert)
+\item Rekombination: Merge Anhängen und Leitungen entfernen.
+\end{itemize}
+
+Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt
+Abbildung~\ref{fig:evolutionary_08}.
+
+\begin{figure}
+\begin{center}
+\input{images/evolutionary-08.tex}
+\end{center}
+\caption{Ein mit dem evolutionären Algorithmus erzeugtes Sortiernetzwerk mit
+acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
+\label{fig:evolutionary_08}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/08-e2-1237993371.tex}
+\end{center}
+\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
+\label{fig:08-e2-1237993371}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/09-e2-1237997073.tex}
+\end{center}
+\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
+\label{fig:09-e2-1237997073}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/09-e2-1237999719.tex}
+\end{center}
+\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 Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
+\end{itemize}
+
+\section{Markov-Kette}
+
+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.
+
+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.
+
+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
+rekombiniert er 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-16.pdf}
+ \end{center}
+ \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden.}
+ \label{fig:markov-comparators-16}
+\end{figure}
+
+%\input{shmoo-aequivalenz.tex}
+
+\section{Optimierung der Schnitte}
+
+\todo{In den Abschnitt "`Leitungen entfernen"' einbauen.}
+
+\begin{figure}
+\begin{center}
+\input{images/32-ec-1277190372.tex}
+\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
+ \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
+\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:} $BS(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten
+möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$
+Komparatoren; $BS(64)$: 672~Komparatoren.
+
+Schnitt-Sequenz:
+MIN( 92)
+MAX( 80)
+MIN(100)
+MAX( 54)
+MAX(102)
+MAX( 53)
+MAX(105)
+MAX( 6)
+MAX( 99)
+MAX( 79)
+MAX( 26)
+MIN(111)
+MAX( 12)
+MIN( 22)
+MAX( 61)
+MAX( 72)
+MAX( 68)
+MIN( 80)
+MAX( 80)
+MAX( 99)
+MAX(105)
+MAX( 0)
+MIN( 8)
+MAX( 40)
+MAX( 74)
+MAX( 40)
+MAX( 40)
+MIN( 56)
+MAX( 27)
+MAX( 13)
+MAX( 1)
+MAX( 81)
+MAX( 17)
+MAX( 4)
+MIN( 36)
+MIN( 22)
+MAX( 13)
+MIN( 72)
+MAX( 24)
+MAX( 5)
+MIN( 10)
+MAX( 59)
+MIN( 37)
+MAX( 65)
+MAX( 46)
+MAX( 73)
+MAX( 58)
+MAX( 29)
+MAX( 65)
+MIN( 23)
+MAX( 56)
+MAX( 11)
+MIN( 75)
+MIN( 51)
+MIN( 46)
+MIN( 34)
+MAX( 32)
+MAX( 6)
+MAX( 37)
+MIN( 4)
+MIN( 28)
+MIN( 20)
+MAX( 33)
+MAX( 34)
+
+% images/32-ec-1277190372.tex
+
+\section{Empirische Beobachtungen}
+
+\begin{itemize}
+\item So schnell konvergiert der Algorithmus.
+\item $\ldots$
+\end{itemize}
+
+\section{Ausblick}
-So geht's jetzt weiter.
+Das würde mir noch einfallen$\ldots$
%\bibliography{references}
%\bibliographystyle{plain}
projects / diplomarbeit.git / blobdiff