X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=0358d88fd7e21f040e2607f0b11ab6ee9a155d41;hb=46edfe5592d85122354f2f39674d0e28986c856d;hp=c4d1fce35e5984de8469c3b730da99575f5ce811;hpb=0a343ac9a2e2d42ae177d043e0afcc55d577a443;p=diplomarbeit.git

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index c4d1fce..0358d88 100644
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -435,7 +435,7 @@ ${n = 8}$ Leitungen.
   \begin{center}
     \input{images/oe-transposition-8.tex}
   \end{center}
-  \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.}
+  \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.}
   \label{fig:odd-even-transposition-08}
 \end{figure}
 
@@ -598,10 +598,10 @@ alle Komparatoren in die gleiche Richtung zeigen.
   \begin{center}
   \input{images/batcher-8.tex}
   \end{center}
-  \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für acht
-  Eingänge. Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden
-  bitonen Mischer~\bm{4} (blau) und die Komparatoren, die im letzten
-  rekursiven Schritt hinzugefügt wurden (grün).}
+  \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für 8~Eingänge.
+    Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden bitonen
+    Mischer~\bm{4} (blau) und die Komparatoren, die im letzten rekursiven
+    Schritt hinzugefügt wurden (grün).}
   \label{fig:bitonic-08}
 \end{figure}
 
@@ -656,10 +656,12 @@ w_i = \left\{ \begin{array}{ll}
   \begin{center}
   \input{images/oe-merge.tex}
   \end{center}
-  \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Im
-    Vergleich zum bitonen Mischer für acht Leitungen kommt dieses Schema mit
-    einem Komparator weniger aus. Der Effekt wird durch den rekursiven Aufbau
-    verstärkt.}
+  \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Die
+    beiden Dreiecke symbolisieren die beiden sortierten Folgen $U$ und $V$,
+    die Blöcke darunter die rekursiven Mischer mit etwa der Hälfte der
+    Leitungen. Im Vergleich zum \emph{bitonen Mischer} für 8~Leitungen kommt
+    dieses Schema mit einem Komparator weniger aus. Der Effekt wird durch den
+    rekursiven Aufbau verstärkt.}
   \label{fig:oe-merge}
 \end{figure}
 
@@ -701,7 +703,7 @@ Aufbau lauten:
   einzelnen Komparator.
 \end{itemize}
 
-Mit dem {\em 0-1-Prinzip} lässt sich zeigen, sass die resultierende Folge
+Mit dem {\em 0-1-Prinzip} lässt sich zeigen, dass die resultierende Folge
 sortiert ist. Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den
 geraden Teilfolgen $U_{\textrm{gerade}}$, beziehungsweise
 $V_{\textrm{gerade}}$ größer oder gleich der Anzahl der Nullen in den
@@ -802,7 +804,7 @@ die als leere Komparatornetzwerke definiert sind.
   \begin{center}
   \input{images/oe-mergesort-8.tex}
   \end{center}
-  \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
+  \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für 8~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
@@ -813,7 +815,7 @@ die als leere Komparatornetzwerke definiert sind.
 In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk
 zu sehen. Rot markiert sind die beiden rekursiven Instanzen
 $\operatorname{OES}(4)$. Die anderen Blöcke stellen den
-\emph{Odd-Even}-Mischer für acht Leitungen dar: die beiden blauen Blöcke sind
+\emph{Odd-Even}-Mischer für 8~Leitungen dar: die beiden blauen Blöcke sind
 die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
 die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden.
 
@@ -935,7 +937,7 @@ zu sortieren und die Ausgaben mit einem der beschriebenen Mischer
 zusammenfügen.
 
 Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken}
-$\operatorname{BS}(8)$ mit je acht Leitungen mit dem
+$\operatorname{BS}(8)$ mit je 8~Leitungen mit dem
 \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten
 Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt
 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
@@ -1311,17 +1313,20 @@ w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
 
 \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.
+Als \emph{Selektion} wird der Vorgang bezeichnet, der zwei Individuen zufällig
+aus der Population auswählt. Sie werden im folgenden Schritt miteinander
+rekombiniert. Die Auswahl der Individuen erfolgt zufällig, aber nicht
+gleichverteilt. So sorgt die \emph{Selektion} 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.
+passiert es häufig, dass die Ausnutzung \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:
+Die in \textsc{SN-Evolution} implementierte Selektion eines Individuums lässt
+sich mit Pseudocode wie folgt beschreiben:
 \begin{verbatim}
   Gütesumme := 0
   Auswahl := (leer)
@@ -1340,6 +1345,10 @@ Pseudocode wie folgt beschreiben:
   gib Auswahl zurück
 \end{verbatim}
 
+Diese Auswahl wird zweimal ausgeführt, um zwei Individuen für die
+Rekombination zu erhalten. Das heißt, dass die Individuen bei
+\textsc{SN-Evolution} stochastisch unabhängig voneinander ausgewählt werden.
+
 \subsection{Rekombination}
 \label{sect:sn-evolution:rekombination}
 
@@ -1617,6 +1626,175 @@ Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}}
 %\input{shmoo-aequivalenz.tex}
 
 \newpage
+\section{Der \textsc{SN-Markov}-Algorithmus}
+\label{sect:markov}
+
+Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
+Abschnitt verwendet 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, kombiniert das aktuelle Netzwerk
+\emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller
+Leitungen, 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 $S_1$ durch die Rekombination von $S_0$ mit sich
+selbst erzeugt werden kann.
+
+Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl
+der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger
+sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der
+Nachfolger zwar noch unter 20.000, bei den untersuchten
+32-Sortier\-netz\-werken wurden jedoch bereits bis zu $2,6 \cdot 10^8$
+unterschiedliche Schnittmuster geschätzt.
+
+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. In Pseudocode lässt sich der
+Algorithmus wie folgt beschreiben:
+
+\begin{verbatim}
+  Netzwerk := Eingabe
+  
+  für n Iterationen
+  {
+    Nachfolger := kombiniere (Netzwerk, Netzwerk)
+    Netzwerk   := Nachfolger
+  }
+  
+  gib Netzwerk zurück
+\end{verbatim}
+
+Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der
+Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem
+zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der
+\textsc{SN-Markov}-Algorithmus auf einem entsprechenden
+\emph{Odd-Even-Transpositionsort}-Netzwerk gestartet und hat mindestens
+1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der
+Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler
+erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende
+prozentuale Verteilung zu sehen.
+
+Ebenfalls in die Graphen der Abbildung~\ref{fig:markov-comparators}
+eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen
+Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der
+um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde.
+Beispielsweise war die kleinste erreichte Komparatorzahl bei
+16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$
+gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$
+und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem
+Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$
+unter den Graphen angegeben.
+
+\begin{figure}
+  \centering
+  \subfigure[12 Leitungen, $k = 8,267$, $\theta = 0,962$, $\delta = 40$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-12-pct.pdf}}
+  \subfigure[14 Leitungen, $k = 9,522$, $\theta = 0,867$, $\delta = 52$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-14-pct.pdf}}
+  \subfigure[16 Leitungen, $k = 17,939$, $\theta = 1,091$, $\delta = 62$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-16-pct.pdf}}
+  \subfigure[18 Leitungen, $k = 10,724$, $\theta = 0,766$, $\delta = 81$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-18-pct.pdf}}
+  \caption{Anzahl der Komparatoren von Sortiernetzwerken,
+  die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet
+  ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der
+  gemessenen Daten darstellt.}
+  \label{fig:markov-comparators}
+\end{figure}
+
+\begin{figure}
+  \begin{center}
+    \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf}
+  \end{center}
+  \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von
+  \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem
+  \emph{Odd-Even}-Mischer und dem \emph{bitonen Mischer}) besaßen.}
+  \label{fig:comparison-comparators}
+\end{figure}
+
+Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der
+\textsc{SN-Markov}-Algorithmus nicht schlechter ist als der
+\textsc{SN-Evolution}-Algo\-rith\-mus. Analog zu dem Versuch mit
+\textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die Anzahl
+der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als
+Startnetzwerk diente bei beiden Algorithmen das
+\emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der
+x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der
+ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt
+wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden sich außerdem je
+nach verwendetem Mischer-Netzwerk -- \oem{32}, beziehungsweise \bm{32}.
+
+Sowohl der \textsc{SN-Markov}-Algorithmus, der das
+\emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit
+\oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die
+bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind.
+Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger:
+Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit
+63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335
+\%$ rund 20~mal höher.
+
+Erwartungsgemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem
+\emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist
+jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die
+mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort}. \oet{16}
+ist aus 120~Komparatoren aufgebaut. Bei dem Lauf, der die Daten für
+Abbildung~\ref{fig:comparison-comparators} lieferte, trat auch jeweils ein
+Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so
+vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen
+Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das
+mit der Initialisierung durch das \emph{Odd-Even-Transpositionsort}-Netzwerk
+zusammenhängt.
+
+%\begin{figure}
+%  \begin{center}
+%  \includegraphics[viewport=0 0 425 262,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 425 262,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}
+%
+%\begin{figure}
+%  \begin{center}
+%  \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf}
+%  \end{center}
+%  \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen),
+%  die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
+%  \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.}
+%  \label{fig:markov-comparators-18}
+%\end{figure}
+
+%\begin{figure}
+%  \begin{center}
+%  \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
+%  \end{center}
+%  \caption{Zyklen, die beim \textit{Random Walk} des
+%  \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die
+%  Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der
+%  y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale
+%  Start-Sortiernetzwerk war $\operatorname{OET}(16)$.}
+%  \label{fig:markov-cycles-16}
+%\end{figure}
+
+\newpage
 \section{Der \textsc{SN-Evolution-Cut}-Algorithmus}
 \label{sect:sn-evolution-cut}
 
@@ -1632,7 +1810,7 @@ Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
 in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
 Ein Individuum besteht aus einer Liste von $n$~Zahlen, die entweder 1, $-1$
 oder 0 sind. Dieser Werte entsprechen Maximum, Minimum und unbelegt. Bei einem
-$k$-Schnittmuster sind genau $k$ Zahlen nicht Null.
+$k$-Schnittmuster sind genau $k$ Zahlen ungleich Null.
 
 Um zwei Individuen zu rekombinieren werden die ersten $r$~Werte des einen
 Schnittmusters und die letzten ${n-r}$~Schnitte des zweiten Schnittmusters
@@ -1645,20 +1823,247 @@ multipliziert den Wert einer Leitung mit $-1$, um die Schnittrichtung zu
 invertieren.
 
 \subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:bs}
+
+Wenn der \textsc{SN-Evolution-Cut}-Algorithmus mit dem \emph{bitonen
+Mergesort}-Netzwerk \bs{n} gestartet wird und $k$~Leitungen entfernen soll,
+ergeben die gefundenen Schnittmuster in vielen Fällen effizientere Netzwerke
+als \bs{n-k}. Wird \textsc{SN-Evolution-Cut} beispielsweise mit \bs{22} und $k
+= 6$ gestartet, resultiert das gefundene Schnittmuster in einem
+Sortiernetzwerk mit 67~Komparatoren, 13~Komparatoren weniger als \bs{16}
+benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert
+wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen.
+
+\begin{figure}
+  \begin{center}
+    \input{images/16-ec-from-bs22.tex}
+  \end{center}
+  \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
+    10~Schichten. Das Netzwerk wurde von dem Algorithmus
+    \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk
+    $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4,
+    10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.}
+  \label{fig:16-ec-from-bs22}
+\end{figure}
+
+Eine Übersicht über die Effizienz der Ergebnisse, die mit dem \emph{bitonen
+Mergesort}-Netzwerk als Eingabe für \textsc{SN-Evolution-Cut} erzielt wurden,
+gibt Tabelle~\ref{tbl:ec-bs-efficiency}. \textsc{SN-E\-vo\-lu\-tion-Cut} wurde
+mit \bs{n}, $n = 9 \dots 24$ und $k = 1 \dots (n-8)$ gestartet. Die Konstanten
+der Bewertungsfunktion waren $w_{\mathrm{Basis}} = 0$,
+$w_{\mathrm{Komparatoren}} = 1$ und $w_{\mathrm{Schichten}} = n$. In jeder
+Zeile befinden sich die Ergebnisse für ein Eingabenetzwerk, in den Spalten
+befinden sich die Ergebnisse für eine Leitungszahl $m=n-k$ des
+Ausgabenetzwerks. In den Zellen stehen jeweils die Anzahl der Komparatoren des
+resultierenden Netzwerks. Die letzte Zeile enthält die Anzahl der
+Komparatoren, die \bs{m} benötigt, um die Ergebnisse besser einordnen zu
+können.
+
+\begin{table}
+  \begin{center}
+    \rowcolors{2}{black!5}{}
+    \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+    \hline
+       &  8 &  9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 &  20 &  21 &  22 &  23 \\
+    \hline
+    9  & 21 &    &    &    &    &    &    &    &    &    &    &    &     &     &     &     \\
+    10 & 20 & 27 &    &    &    &    &    &    &    &    &    &    &     &     &     &     \\
+    11 & 20 & 27 & 32 &    &    &    &    &    &    &    &    &    &     &     &     &     \\
+    12 & 20 & 26 & 32 & 39 &    &    &    &    &    &    &    &    &     &     &     &     \\
+    13 & 20 & 26 & 32 & 39 & 45 &    &    &    &    &    &    &    &     &     &     &     \\
+    14 & 20 & 26 & 32 & 39 & 45 & 53 &    &    &    &    &    &    &     &     &     &     \\
+    15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 &    &    &    &    &    &     &     &     &     \\
+    16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 &    &    &    &    &     &     &     &     \\
+    17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 &    &    &    &     &     &     &     \\
+    18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 &    &    &     &     &     &     \\
+    19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 &    &     &     &     &     \\
+    20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 &     &     &     &     \\
+    21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 &     &     &     \\
+    22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 &     &     \\
+    23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 &     \\
+    24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\
+    \hline
+\bs{m} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\
+    \hline
+    \end{tabular}
+  \end{center}
+  \caption{Anzahl der Komparatoren der Ergebnisse von
+    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
+    Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
+    die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
+    Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
+  \label{tbl:ec-bs-efficiency}
+\end{table}
+
+Zu sehen ist, dass jedes einzelne Ergebnis von \textsc{SN-Evolution-Cut}
+mindestens so effizient wie das \emph{bitone Mergesort}-Netzwerk mit der
+gleichen Leitungszahl ist. Außerdem enthält jede Spalte (mit Ausnahme von
+$m=23$) ein Ergebnis, das effizienter als \bs{m} ist.
+
+In zahlreichen Fällen reicht das Entfernen einer einzigen Leitung aus, um ein
+effizientes Ergebnis zu erzielen. Das Ergebnis, das \textsc{SN-Evolution-Cut}
+gestartet mit \bs{20} und $k = 1$ erreicht, benötigt mit 95~Komparatoren
+3~weniger als \bs{19}.
+
+Bei anderen Größen ergeben erst größere~$k$ effiziente Sortiernetzwerke,
+beispielsweise bei $m = 10$: erst für $n = 18$, $k = 8$ wird ein
+Sortiernetzwerk mit 31~Komparatoren gefunden.
+
+\begin{figure}
+  \centering
+  \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das
+  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{19} erzeugt.]{\input{images/10-ec-from-bs19-fast.tex}\label{fig:10-ec-from-bs19-fast}}
+  \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
+  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{18} erzeugt.]{\input{images/11-ec-from-bs18-fast.tex}\label{fig:11-ec-from-bs18-fast}}
+  \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
+  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/12-ec-from-bs22-fast.tex}\label{fig:12-ec-from-bs22-fast}}
+  \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das
+  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{37} erzeugt.]{\input{images/19-ec-from-bs37-fast.tex}\label{fig:19-ec-from-bs37-fast}}
+  \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11,
+  12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
+  erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.}
+  \label{fig:ec-bs-fast_networks}
+\end{figure}
+
+Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der
+\textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als
+das entsprechende \emph{bitone Mergesort}-Netzwerk \bs{m} sind. In
+Tabelle~\ref{tbl:ec-bs-speed} sind die Schichten, die die Ergebnisse von
+\textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren, aufgelistet.
+Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n}, jede Spalte
+enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die Zellen
+enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks.
+
+\begin{table}
+  \begin{center}
+    \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+\hline
+    &   8 &   9 &  10 &  11 &  12 &  13 &  14 &  15 &  16 &  17 &  18 &  19 &  20 &  21 &  22 &  23 \\
+\hline
+  9 &   6 &     &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 10 &   6 &   8 &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 11 &   6 &   8 &   9 &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 12 &   6 &   8 &   9 &  10 &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 13 &   6 &   8 &   9 &  10 &  10 &     &     &     &     &     &     &     &     &     &     &     \\
+ 14 &   6 &   8 &   9 &  10 &  10 &  10 &     &     &     &     &     &     &     &     &     &     \\
+ 15 &   6 &   8 &   9 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     &     &     \\
+ 16 &   6 &   8 &   9 &  10 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     &     \\
+ 17 &   6 &   8 &   8 &   9 &  10 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     \\
+ 18 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &     &     &     &     &     &     \\
+ 19 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &     &     &     &     &     \\
+ 20 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &     &     &     &     \\
+ 21 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &     &     &     \\
+ 22 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &     &     \\
+ 23 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &     \\
+ 24 &   6 &   8 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &  15 \\
+\hline
+\bs{m}& 6 &   8 &   9 &  10 &  10 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &  15 \\
+\hline
+\end{tabular}
+  \end{center}
+  \caption{Anzahl der Schichten der Ergebnisse von
+    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
+    Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
+    die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
+    Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
+  \label{tbl:ec-bs-speed}
+\end{table}
+
+Für die Ziel-Leitungszahlen 9, 10 und 11 wurden Schnittmuster gefunden, die
+schnelle Sortiernetzwerke erzeugen. Beispiele für schnelle Sortiernetzwerke,
+die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt
+werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt.
+
+Bei der Betrachtung der Effizienz wurde festgestellt, dass oft schon das
+Entfernen einer einzigen Leitung zu eines effizienteren Ergebnis als \bs{m}
+führt. Bei der Geschwindigkeit ist die Anzahl der Leitungen, die entfernt
+werden müssen, um schnellere Netzwerke zu erzielen, größer. Um eine Schicht
+einzusparen waren bei $m = 10$ und $m = 11$ $k = 6$ Schnitte notwendig. Bei $m
+= 9$ war sogar ein 7-Schnittmuster notwendig, um die Anzahl der Schichten zu
+reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise
+noch größer gewählt werden.
+
+Die Effizienz und Geschwindigkeit der Sortiernetzwerke, die von
+\textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk erzeugten
+werden, ist für $m = 19$ und $n = 20 \dots 38$ ($k = 1 \dots 19$) in
+Tabelle~\ref{tbl:ec-bs-19} aufgelistet. Erst, wenn $k \geqq 6$ ist, wird im
+Vergleich zu \bs{19} eine Schicht eingespart. Für $n = 36$ ($k = 17$) und $n =
+37$ ($k = 18$) werden Sortiernetzwerke ausgegeben, die schneller als \bs{19}
+und \oes{19} sind und nur einen Komparator mehr als \oes{19} benötigen. Ein
+Beispiel für ein solches Netzwerk ist in
+Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen.
+
+\begin{table}
+  \begin{center}
+    \rowcolors{2}{black!5}{}
+    \begin{tabular}{|r|r|r|}
+    \hline
+    $n$ & Komp. & Schichten \\
+    \hline
+          20 & 95 & 14 \\
+          21 & 94 & 14 \\
+          22 & 93 & 14 \\
+          23 & 93 & 14 \\
+          24 & 93 & 14 \\
+          25 & 96 & 13 \\
+          26 & 96 & 13 \\
+          27 & 96 & 13 \\
+          28 & 96 & 13 \\
+          29 & 95 & 13 \\
+          30 & 96 & 13 \\
+          31 & 95 & 13 \\
+          32 & 96 & 13 \\
+          33 & 93 & 13 \\
+          34 & 94 & 13 \\
+          35 & 93 & 13 \\
+          \rowcolor{green!10}
+          36 & 92 & 13 \\
+	  \rowcolor{green!10!white!95!black}
+          37 & 92 & 13 \\
+          38 & 93 & 13 \\
+    \hline
+    \bs{19}  & 98 & 14 \\
+    \oes{19} & 91 & 14 \\
+    \hline
+    \end{tabular}
+  \end{center}
+  \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die
+    von \textsc{SN-Evolution-Cut} aus \bs{n}, $n = 20, \dots, 38$ erzeugt
+    wurden. Für $k \geqq 6$ ergeben sich Sortiernetzwerke, die schneller als
+    \bs{19} sind. Mit $k \in \{14, 16, 19\}$ erreichen die Ergebnisse mit
+    13~Schichten die Effizienz der vorherigen
+    Ergebnisse mit 14~Schichten, mit $k = 17$ und $k = 18$ wird diese
+    Effizienz noch übertroffen. Ein 19-Sortiernetzwerk, das aus \bs{37}
+    auf diese Art erzeugt wurde, ist in
+    Abbildung~\ref{fig:19-ec-from-bs37-fast} dargestellt.}
+  \label{tbl:ec-bs-19}
+\end{table}
 
 \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
-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.
-
-Beispielsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
-Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
-konstruiert wurde. Dieses Sortiernetzwerk be\-nö\-tigt 68~Komparatoren,
-12~weniger als das \emph{bitone Mergesort}-Netzwerk nach Batchers Methode.
-Gegenüber Batchers Methode sparen so konstruierte Sortiernetzwerke
-${\frac{1}{4}n(\log n - 1)}$ Komparatoren ein.
+wie ein \emph{bitoner Mischer} $\bm{n = 2^d}$, der nach Batchers Methode
+konstruiert wurde, durch systematisches Entfernen von Leitungen in einen
+ebenfalls bitonen Mischer mit der Hälfte der Leitungen transformiert werden
+kann, so dass dieser alternative Mischer im Vergleich zu $\bm{\frac{n}{2} =
+2^{d-1}}$ Komparatoren einspart.
+
+Basierend auf diesen alternativen Mischern geben \textit{Mühlenthaler} und
+\textit{Wanka} eine Konstruktionsvorschrift für Sortiernetzwerke an, die
+gegenüber \bs{n} ${\frac{1}{4}n(\log n - 1)}$ Komparatoren einspart.
+Beispielsweise wird ein 16-Sortiernetzwerk angegeben, das nur 68~Komparatoren
+benötigt. Dieses Netzwerk ist in Abbildung~\ref{fig:16-muehlenthaler}
+dargestellt.
+
+\begin{figure}
+  \begin{center}
+    \input{images/16-muehlenthaler.tex}
+  \end{center}
+  \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
+    10~Schichten. Das Netzwerk wurde 2010 von \textit{Mühlenthaler} und
+    \textit{Wanka} aus optimierten bitonen Mischern konstruiert und
+    in~\cite{MW2010} veröffentlicht.}
+  \label{fig:16-muehlenthaler}
+\end{figure}
 
 \begin{figure}
   \begin{center}
@@ -1692,10 +2097,10 @@ und das Schnittmuster ${\operatorname{MIN}(0, 5, 9, 11, 15, 17, 20, 22, 26,
 29, 30)}$, ${\operatorname{MAX}(2, 4, 13, 19, 24)}$, 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.
+nachdem das Schnittmuster angewendet 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
@@ -1716,19 +2121,24 @@ Netzwerks scheinen rein zufällig zu sein.
   \label{fig:32-ec-from-bs64}
 \end{figure}
 
-Das Ergebnis von \textit{Mühlenthaler} und \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
-Geschwindigkeit dieser Sortiernetzwerke gleich ist.
+Wenn \textsc{SN-Evolution-Cut} mit dem \bs{64}-Netzwerk und $k = 32$ gestartet
+wird, findet der Algorithmus 32-Sortiernetzwerke, die effizienter sind als
+32-Sortiernetzwerke, die nach \textit{Mühlenthalers} und \textit{Wankas}
+Methode konstruiert werden. Ein von \textsc{SN-Evolution-Cut} aus \bs{64}
+generiertes 32-Sortiernetzwerk ist in Abbildung~\ref{fig:32-ec-from-bs64}
+dargestellt. Das \emph{bitone Mergesort}-Netzwerk \bs{32} benötigt
+240~Komparatoren, ein aus den optimierten Mischern aufgebautes Netzwerk
+verbessert die Effizienz auf 208~Komparatoren. Das Ergebnis von
+\textsc{SN-Evolution-Cut} kommt mit nur 206~Komparatoren aus. Die
+Geschwindigkeit aller genannten Sortiernetzwerke ist mit 15 parallelen
+Schritten identisch.
+
+Wenn die Leitungszahl des Eingabenetzwerks keine Zweierpotenz ist, kann
+\textsc{SN-Evo\-lu\-tion-Cut} auch 16-Sortiernetzwerke erzeugen, die diese
+Effizienz unterbieten. Das geht aus den Daten in
+Tabelle~\ref{tbl:ec-bs-efficiency} hervor. Ein 16-Sortiernetzwerk mit
+67~Komparatoren, das von \textsc{SN-Evolution-Cut} generiert wurde, ist in
+Abbildung~\ref{fig:16-ec-from-bs22} dargestellt.
 
 Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
 unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
@@ -1744,170 +2154,143 @@ die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
 Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
 mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
 
-\begin{figure}
-  \centering
-  \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
-  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/11-ec-from-bs22-fast.tex}\label{fig:11-ec-from-bs22-fast}}
-  \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
-  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{24} erzeugt.]{\input{images/12-ec-from-bs24-fast.tex}\label{fig:12-ec-from-bs24-fast}}
-  \caption{Startet man \textsc{SN-Evolution-Cut} mit \bs{22} und \bs{24}, kann
-  der Algorithmus schnelle Sortiernetzwerke ausgeben.}
-  \label{fig:11-12-ec-from-bs22-bs24}
-\end{figure}
+Dass die Sortiernetzwerke, die mit den Schnittmustern von
+\textsc{SN-Evolution-Cut} entstehen, 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
+$k$~Schnitten gestartet, so ist das beste Ergebnis immer das
+$\operatorname{OET}(n-k)$-Netzwerk. 
 
-Verwendet man als Eingabe für \textsc{SN-Evolution-Cut} Instanzen des
-\emph{bitonen Mergesort}-Netzwerks, deren Leitungszahl keine Zweierpotenz ist,
-können Sortiernetzwerke zurückgegeben werden, die sowohl schneller als auch
-effizienter als das entsprechende \emph{bitone Mergesort}-Netzwerk sind. Die
-folgende Tabelle listet einige interessante Fälle auf. Die Eingabe für
-\textsc{SN-Evolution-Cut} war jeweils das \emph{bitone Mergesort}-Netzwerk mit
-der doppelten Leitungszahl. Die Abbildungen~\ref{fig:11-12-ec-from-bs22-bs24}
-und~\ref{fig:23-ec-from-bs46} zeigen beispielhaft ein 11-, 12- und
-23-Sortiernetzwerk, die aus \bs{22}, \bs{24} und \bs{46} generiert wurden.
+\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:oes}
 
-\begin{center}
-\begin{tabular}{|r|r|r|r|r|}
+Wird \textsc{SN-Evolution-Cut} mit dem \emph{Odd-Even-Mergesort}-Netzwerk
+\oes{n} gestartet, gibt der Algorithmus meist Sortiernetzwerke zurück, die
+genauso effizient und schnell wie das entsprechende
+\emph{Odd-Even-Mergesort}-Netzwerk \oes{m} sind. Die Effizienz der
+Sortiernetzwerke, die mit Schnittmustern von \textsc{SN-Evolution-Cut} aus
+\oes{n} entstehen können, zeigt Tabelle~\ref{tbl:ec-oes-efficiency}
+tabellarisch.
+
+\begin{table}
+  \begin{center}
+    \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
 \hline
-Leitungen  & Komparatoren & Schichten & Komparatoren & Schichten \\
-           & \textsc{SN-EC} & \textsc{SN-EC} & \bs{n} &
-	   \bs{n} \\
+    &   8 &   9 &  10 &  11 &  12 &  13 &  14 &  15 &  16 &  17 &  18 &  19 &  20 &  21 &  22 &  23 \\
 \hline
-11 &  37 &  9 &  39 & 10 \\
-12 &  42 &  9 &  46 & 10 \\
-19 &  93 & 13 &  98 & 14 \\
-20 & 102 & 13 & 106 & 14 \\
-% 20: # sn-cut 2:MAX 3:MIN 4:MIN 9:MIN 10:MIN 13:MIN 14:MIN 15:MIN 19:MIN 20:MAX 24:MAX 26:MIN 27:MAX 29:MIN 31:MAX 33:MIN 34:MAX 35:MIN 37:MIN 39:MAX
-21 & 109 & 14 & 114 & 15 \\
-22 & 116 & 14 & 123 & 15 \\
-23 & 124 & 14 & 133 & 15 \\
+  9 &  19 &     &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 10 &  19 &  26 &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 11 &  19 &  26 &  31 &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 12 &  19 &  26 &  31 &  37 &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 13 &  19 &  26 &  31 &  37 &  41 &     &     &     &     &     &     &     &     &     &     &     \\
+ 14 &  19 &  26 &  31 &  37 &  41 &  48 &     &     &     &     &     &     &     &     &     &     \\
+ 15 &  19 &  26 &  31 &  37 &  41 &  48 &  53 &     &     &     &     &     &     &     &     &     \\
+ 16 &  19 &  26 &  31 &  37 &  41 &  48 &  53 &  59 &     &     &     &     &     &     &     &     \\
+ 17 &  19 &  26 &  31 &  38 &  41 &  48 &  53 &  59 &  63 &     &     &     &     &     &     &     \\
+ 18 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &     &     &     &     &     &     \\
+ 19 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &     &     &     &     &     \\
+ 20 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &     &     &     &     \\
+ 21 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &  97 &     &     &     \\
+ 22 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &  97 & 107 &     &     \\
+ 23 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &  97 & 107 & 114 &     \\
+ 24 &  19 &  26 &  31 &  38 &  43 &  48 &  53 &  59 &  63 &  74 &  82 &  91 &  97 & 107 & 114 & 122 \\
 \hline
 \end{tabular}
-\end{center}
+  \end{center}
+  \caption{Anzahl der Komparatoren der Ergebnisse von
+    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+    \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
+    Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
+    Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+    Ausgabenetzwerks.}
+  \label{tbl:ec-oes-efficiency}
+\end{table}
 
 \begin{figure}
-  \begin{center}
-    \input{images/23-ec-from-bs46-fast.tex}
-  \end{center}
-  \caption{23-Sortiernetzwerk mit 124~Komparatoren in 14~Schichten. Das
-  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{46} mit dem
-  Schnittmuster $\operatorname{MIN}(2, 4, 9, 12, 20, 22, 28, 30, 32, 33, 37,
-  38, 41)$, $\operatorname{MAX}(1, 5, 16, 19, 21, 24, 25, 35, 36, 43)$
-  erzeugt.}
-  \label{fig:23-ec-from-bs46}
+  \centering
+  \subfigure[11-Sortiernetzwerk aus 38~Komparatoren in 9~Schichten. Das
+  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{17} erzeugt.]{\input{images/11-ec-from-oes17-fast.tex}\label{fig:11-ec-from-oes17-fast}}
+  \subfigure[12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten. Das
+  Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{18} erzeugt.]{\input{images/12-ec-from-oes18-fast.tex}\label{fig:12-ec-from-oes18-fast}}
+  \caption{Für einige Ziel-Leitungszahlen, unter anderem $m = 10$ und $m =
+  11$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
+  erzeugen, die \emph{schneller} aber weniger \emph{effizient} als \oes{m}
+  sind.}
+  \label{fig:ec-oes-fast_networks}
 \end{figure}
 
-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. 
+Die Bewertungsfunktion, die \textsc{SN-Evolution-Cut} verwendet, bevorzugt
+schnelle Sortiernetzwerke. Dadurch kann es vorkommen, dass ein
+$m$-Sortiernetzwerk, das durch ein von \textsc{SN-Evolution-Cut} ausgegebenes
+Schnittmuster entsteht, schneller als \oes{m} ist. Diese Geschwindigkeit
+war allerdings in allen beobachteten Fällen nur dann möglich, wenn
+zusätzliche Komparatoren in Kauf genommen wurden. In den
+Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} ist dieser
+Fall für $m = 11$ und $k \geqq 6$, beziehungsweise $m = 12$ und $k \geqq 6$ zu
+beobachten. Die entsprechenden schnellen Sortiernetzwerke sind in
+Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt.
+
+\begin{table}
+  \begin{center}
+    \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+\hline
+    &   8 &   9 &  10 &  11 &  12 &  13 &  14 &  15 &  16 &  17 &  18 &  19 &  20 &  21 &  22 &  23 \\
+\hline
+  9 &   6 &     &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 10 &   6 &   8 &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 11 &   6 &   8 &   9 &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 12 &   6 &   8 &   9 &  10 &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 13 &   6 &   8 &   9 &  10 &  10 &     &     &     &     &     &     &     &     &     &     &     \\
+ 14 &   6 &   8 &   9 &  10 &  10 &  10 &     &     &     &     &     &     &     &     &     &     \\
+ 15 &   6 &   8 &   9 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     &     &     \\
+ 16 &   6 &   8 &   9 &  10 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     &     \\
+ 17 &   6 &   8 &   9 &   9 &  10 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     \\
+ 18 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &     &     &     &     &     &     \\
+ 19 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &     &     &     &     &     \\
+ 20 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &     &     &     &     \\
+ 21 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &     &     &     \\
+ 22 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &     &     \\
+ 23 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &     \\
+ 24 &   6 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &  15 \\
+\hline
+\oes{m}& 6 &  8 &   9 &  10 &  10 &  10 &  10 &  10 &  10 &  12 &  13 &  14 &  14 &  15 &  15 &  15 \\
+\hline
+\end{tabular}
+  \end{center}
+  \caption{Anzahl der Schichten der Ergebnisse von
+    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+    \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
+    Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
+    Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+    Ausgabenetzwerks.}
+  \label{tbl:ec-oes-speed}
+\end{table}
 
-\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
+In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
+viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke
+$\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und $\operatorname{PS}(32)$
+besitzen. Eines der Ergebnisse war, dass von diesen Sortiernetzwerken das
+\emph{Odd-Even-Mergesort}-Netzwerk die wenigsten unterschiedlichen
+16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. Entsprechend ist es
+wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit
+$\operatorname{OES}(32)$ sehr schnell\footnote{Auf dem Computer, auf dem diese
+Arbeit geschrieben wurde, dauerte es in den meisten Fällen weniger als eine
+Sekunde bis ein entsprechendes Schnittmuster gefunden wurde.} ein gutes
+16-Schnittmuster findet.
 
-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, das die gleiche
-Anzahl 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.
+Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
+bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist
+$\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7,
+8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in
+Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende
+Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
 
 \begin{figure}
   \begin{center}
-    \input{images/16-ec-from-ps32.tex}
-  \end{center}
-  \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
-    10~Schichten. Das Netzwerk wurde von dem Algorithmus
-    \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk}
-    $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.}
-  \label{fig:16-ec-from-ps32}
-\end{figure}
-
-Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht
-einsetzt und auch nicht auf einem Mischer basiert, ist das
-\emph{Odd-Even-Merge}-Netzwerk $\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 Sortiernetzwerke, die
-strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die
-Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
-
-\begin{figure}
-  \begin{center}
-    \input{images/32-pairwise-cut-16-pairwise.tex}
-  \end{center}
-  \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu
-    sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk
-    bilden.}
-  \label{fig:ps16-from-ps32}
-\end{figure}
-
-Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
-regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres
-schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das
-einfache Schnittmuster
-\begin{displaymath}
-\textit{Eingang}_i = \left\{ \begin{array}{rl}
-  -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\
-   \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\
-        ? & \quad \mathrm{sonst}
-  \end{array} \right.
-\end{displaymath}
-für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk
-$\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der
-dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das
-verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32}
-dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind
-diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden
-Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den
-„richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht
-werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende
-Netzwerk in schwarz gut zu erkennen.
-
-\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}
-
-Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf
-$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein
-8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für
-größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise
-kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16}
-konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n}
-untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.
-
-\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
-\label{sect:sn-evolution-cut:oes}
-
-In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
-viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke
-$\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und $\operatorname{PS}(32)$
-besitzen. Eines der Ergebnisse war, dass von diesen Sortiernetzwerken das
-\emph{Odd-Even-Mergesort}-Netzwerk die wenigsten unterschiedlichen
-16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. Entsprechend ist es
-wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit
-$\operatorname{OES}(32)$ sehr schnell\footnote{Auf dem Computer, auf dem diese
-Arbeit geschrieben wurde, dauerte es in den meisten Fällen weniger als eine
-Sekunde bis ein entsprechendes Schnittmuster gefunden wurde.} ein gutes
-16-Schnittmuster findet.
-
-Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
-bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist
-$\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7,
-8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in
-Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende
-Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
-
-\begin{figure}
-  \begin{center}
-    \input{images/16-ec-from-oes32-cut.tex}
+    \input{images/16-ec-from-oes32-cut.tex}
   \end{center}
   \caption{Visualisierung eines 16-Schnittmusters, das auf
   $\operatorname{OES}(32)$ angewendet wieder ein schnelles und effizientes
@@ -2018,9 +2401,7 @@ Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
 Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der
 Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In
 beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu
-\bs{23} beziehungsweise \oes{23} eine Schicht einspart. Allerdings ist das
-Sortiernetzwerk auf Basis von \bs{46} (Abbildung~\ref{fig:23-ec-from-bs46})
-effizienter, da es nur 124~Komparatoren benötigt.
+\bs{23} beziehungsweise \oes{23} eine Schicht einspart.
 
 \begin{figure}
   \begin{center}
@@ -2034,174 +2415,127 @@ effizienter, da es nur 124~Komparatoren benötigt.
   \label{fig:23-ec-from-oes46}
 \end{figure}
 
-\newpage
-\section{Der \textsc{SN-Markov}-Algorithmus}
-\label{sect:markov}
-
-Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
-Abschnitt verwendet 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, kombiniert das aktuelle Netzwerk
-\emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller
-Leitungen, 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 $S_1$ durch die Rekombination von $S_0$ mit sich
-selbst erzeugt werden kann.
-
-Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl
-der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger
-sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der
-Nachfolger zwar noch unter 20.000, bei den untersuchten
-32-Sortier\-netz\-werken wurden jedoch bereits bis zu $2,6 \cdot 10^8$
-unterschiedliche Schnittmuster geschätzt.
-
-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. In Pseudocode lässt sich der
-Algorithmus wie folgt beschreiben:
+\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
 
-\begin{verbatim}
-  Netzwerk := Eingabe
-  
-  für n Iterationen
-  {
-    Nachfolger := kombiniere (Netzwerk, Netzwerk)
-    Netzwerk   := Nachfolger
-  }
-  
-  gib Netzwerk zurück
-\end{verbatim}
+Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene
+Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war
+(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise
+ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
+wie und warum es jede beliebige Eingabe sortiert.
 
-Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der
-Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem
-zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der
-\textsc{SN-Markov}-Algorithmus auf einem entsprechenden
-\emph{Odd-Even-Transpositionsort}-Netzwerk gestartet und hat mindestens
-1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der
-Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler
-erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende
-prozentuale Verteilung zu sehen.
+\begin{table}
+  \begin{center}
+    \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+\hline
+    &   8 &   9 &  10 &  11 &  12 &  13 &  14 &  15 &  16 &  17 &  18 &  19 &  20 &  21 &  22 &  23 \\
+\hline
+  9 &  20 &     &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 10 &  20 &  27 &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 11 &  20 &  28 &  32 &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 12 &  20 &  28 &  32 &  38 &     &     &     &     &     &     &     &     &     &     &     &     \\
+ 13 &  19 &  27 &  31 &  37 &  41 &     &     &     &     &     &     &     &     &     &     &     \\
+ 14 &  19 &  27 &  31 &  37 &  41 &  48 &     &     &     &     &     &     &     &     &     &     \\
+ 15 &  19 &  27 &  31 &  37 &  41 &  48 &  53 &     &     &     &     &     &     &     &     &     \\
+ 16 &  19 &  27 &  31 &  37 &  41 &  48 &  53 &  59 &     &     &     &     &     &     &     &     \\
+ 17 &  21 &  29 &  32 &  39 &  43 &  51 &  57 &  64 &  68 &     &     &     &     &     &     &     \\
+ 18 &  22 &  29 &  32 &  39 &  43 &  52 &  58 &  65 &  69 &  80 &     &     &     &     &     &     \\
+ 19 &  23 &  29 &  32 &  39 &  43 &  52 &  58 &  65 &  69 &  80 &  88 &     &     &     &     &     \\
+ 20 &  23 &  29 &  32 &  39 &  43 &  52 &  58 &  65 &  69 &  80 &  88 &  97 &     &     &     &     \\
+ 21 &  20 &  30 &  34 &  38 &  44 &  51 &  57 &  64 &  74 &  82 &  87 &  96 & 102 &     &     &     \\
+ 22 &  20 &  30 &  34 &  38 &  46 &  51 &  57 &  64 &  72 &  82 &  89 &  96 & 102 & 112 &     &     \\
+ 23 &  20 &  27 &  34 &  38 &  42 &  51 &  57 &  66 &  72 &  83 &  89 &  97 & 102 & 112 & 119 &     \\
+ 24 &  20 &  27 &  34 &  38 &  42 &  51 &  57 &  64 &  72 &  82 &  89 &  96 & 102 & 112 & 119 & 127 \\
+\hline
+\ps{m}&19 &  27 &  32 &  38 &  42 &  48 &  53 &  59 &  63 &  79 &  88 &  97 & 103 & 112 & 119 & 127 \\
+\hline
+\end{tabular}
+  \end{center}
+  \caption{Anzahl der Komparatoren der Ergebnisse von
+    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+    \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$.
+    Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
+    Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+    Ausgabenetzwerks.}
+  \label{tbl:ec-ps-speed}
+\end{table}
 
-Ebenfalls in die Graphen der Abbildung~\ref{fig:markov-comparators}
-eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen
-Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der
-um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde.
-Beispielsweise war die kleinste erreichte Komparatorzahl bei
-16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$
-gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$
-und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem
-Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$
-unter den Graphen angegeben.
+Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian
+Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
+definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit
+$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man
+ein Sortiernetzwerk, das die gleiche Anzahl 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.
 
 \begin{figure}
-  \centering
-  \subfigure[12 Leitungen, $k = 8,267$, $\theta = 0,962$, $\delta = 40$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-12-pct.pdf}}
-  \subfigure[14 Leitungen, $k = 9,522$, $\theta = 0,867$, $\delta = 52$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-14-pct.pdf}}
-  \subfigure[16 Leitungen, $k = 17,939$, $\theta = 1,091$, $\delta = 62$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-16-pct.pdf}}
-  \subfigure[18 Leitungen, $k = 10,724$, $\theta = 0,766$, $\delta = 81$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-18-pct.pdf}}
-  \caption{Anzahl der Komparatoren von Sortiernetzwerken,
-  die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet
-  ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der
-  gemessenen Daten darstellt.}
-  \label{fig:markov-comparators}
+  \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}
 
+Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht
+einsetzt und auch nicht auf einem Mischer basiert, ist das
+\emph{Odd-Even-Merge}-Netzwerk $\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 Sortiernetzwerke, die
+strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die
+Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
+
 \begin{figure}
   \begin{center}
-    \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf}
+    \input{images/32-pairwise-cut-16-pairwise.tex}
   \end{center}
-  \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von
-  \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem
-  \emph{Odd-Even}-Mischer und dem \emph{bitonen Mischer}) besaßen.}
-  \label{fig:comparison-comparators}
+  \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu
+    sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk
+    bilden.}
+  \label{fig:ps16-from-ps32}
 \end{figure}
 
-Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der
-\textsc{SN-Markov}-Algorithmus nicht schlechter ist als der
-\textsc{SN-Evolution}-Algo\-rith\-mus. Analog zu dem Versuch mit
-\textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die Anzahl
-der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als
-Startnetzwerk diente bei beiden Algorithmen das
-\emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der
-x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der
-ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt
-wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden sich außerdem je
-nach verwendetem Mischer-Netzwerk -- \oem{32}, beziehungsweise \bm{32}.
-
-Sowohl der \textsc{SN-Markov}-Algorithmus, der das
-\emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit
-\oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die
-bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind.
-Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger:
-Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit
-63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335
-\%$ rund 20~mal höher.
-
-Erwartungsgemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem
-\emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist
-jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die
-mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort}. \oet{16}
-ist aus 120~Komparatoren aufgebaut. Bei dem Lauf, der die Daten für
-Abbildung~\ref{fig:comparison-comparators} lieferte, trat auch jeweils ein
-Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so
-vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen
-Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das
-mit der Initialisierung durch das \emph{Odd-Even-Transpositionsort}-Netzwerk
-zusammenhängt.
+Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
+regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres
+schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das
+einfache Schnittmuster
+\begin{displaymath}
+\textit{Eingang}_i = \left\{ \begin{array}{rl}
+  -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\
+   \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\
+        ? & \quad \mathrm{sonst}
+  \end{array} \right.
+\end{displaymath}
+für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk
+$\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der
+dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das
+verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32}
+dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind
+diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden
+Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den
+„richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht
+werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende
+Netzwerk in schwarz gut zu erkennen.
 
-%\begin{figure}
-%  \begin{center}
-%  \includegraphics[viewport=0 0 425 262,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 425 262,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}
-%
-%\begin{figure}
-%  \begin{center}
-%  \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf}
-%  \end{center}
-%  \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen),
-%  die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
-%  \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.}
-%  \label{fig:markov-comparators-18}
-%\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}
 
-%\begin{figure}
-%  \begin{center}
-%  \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
-%  \end{center}
-%  \caption{Zyklen, die beim \textit{Random Walk} des
-%  \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die
-%  Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der
-%  y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale
-%  Start-Sortiernetzwerk war $\operatorname{OET}(16)$.}
-%  \label{fig:markov-cycles-16}
-%\end{figure}
+Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf
+$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein
+8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für
+größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise
+kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16}
+konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n}
+untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.
 
 \newpage
 \section{Fazit und Ausblick}