+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[\textsc{SN-Evolution-Cut}]{Der \textsc{SN-Evolution-Cut}-Algorithmus}
+\label{sect:sn-evolution-cut}
+
+Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
+Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
+Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
+möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:sn-evolution:bewertung}.
+
+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 ungleich Null.
+
+Um zwei Individuen zu rekombinieren werden die ersten $r$~Werte des einen
+Schnittmusters und die letzten ${n-r}$~Schnitte des zweiten Schnittmusters
+verwendet. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq n$. Anschließend
+werden zufällig Werte auf Null beziehungsweise 1 oder $-1$ gesetzt, um die
+Anzahl der Schnitte zu korrigieren.
+
+Die Mutation vertauscht entweder die Werte von zwei zufälligen Positionen oder
+multipliziert den Wert einer Leitung mit $-1$, um die Schnittrichtung zu
+invertieren.
+
+Die Eingabe für \textsc{SN-Evolution-Cut} ist ein $n$-Sortiernetzwerk und eine
+Zahl $k$, $1 \leqq k < n$, die angibt wie viele Leitungen entfernt werden
+sollen. Der Rückgabewert des \textsc{SN-Evolution-Cut}-Algorithmus ist ein
+\emph{$k$-Schnittmuster}. Wird das Schnittmuster auf das Sortiernetzwerk, mit
+dem der Algorithmus gestartet wurde, angewendet, entsteht ein möglichst
+schnelles und effizientes Sortiernetzwerk mit $m = n - k$ Leitungen. Da mit
+dem Eingabe-Netzwerk und dem zurückgegebenen $k$-Schnittmuster das
+$m$-Sortiernetzwerk eindeutig bestimmt ist, werden im Folgenden sowohl das
+$k$-Schnittmuster als auch das $m$-Sortiernetzwerk als Ausgabe von
+\textsc{SN-Evolution-Cut} bezeichnet.
+
+\subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:bs}
+
+% Effizienz
+
+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.
+
+% Beispiel Effizienz
+
+\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.
+
+% Geschwindigkeit
+
+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} ist die Anzahl der 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.
+
+% Beispiel Geschwindigkeit
+
+\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 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.
+
+% Detaillierte Betrachtung fuer m = 19
+
+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}
+
+% 2-er Potenz
+
+\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
+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}
+ \input{images/16-ec-from-bs32.tex}
+ \end{center}
+ \caption{Visualisierung eines 16-Schnittmusters, das von
+ \textsc{SN-Evolution-Cut} für das \emph{bitone Mergesort}-Netzwerk \bs{32}
+ berechnet wurde. Das resultierende Sortiernetzwerk besteht aus
+ 68~Komparatoren in 10~Schichten und ist in
+ Abbildung~\ref{fig:16-ec-from-bs32-normalized} als
+ Standard-Sortiernetzwerk dargestellt.}
+ \label{fig:16-ec-from-bs32}
+\end{figure}
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-bs32-normalized.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde mit einem 16-Schnittmuster, das von
+ \textsc{SN-Evolution-Cut} berechnet wurde, aus dem \emph{bitone
+ Mergesort}-Netzwerk \bs{32} erzeugt. Das Schnittmuster ist in
+ Abbildung~\ref{fig:16-ec-from-bs32} dargestellt.}
+ \label{fig:16-ec-from-bs32-normalized}
+\end{figure}
+
+Startet man {\sc SN-Evolution-Cut} mit dem \emph{bitonen Mergesort}-Netzwerk
+$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
+Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
+16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den
+Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized}
+zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$
+und das 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 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
+ % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX
+ % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX
+ % 63:MAX
+ \begin{center}
+ \input{images/32-ec-from-bs64.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in
+ 15~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
+ $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige
+ Schnittmuster ist
+ $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$,
+ $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37,
+ 40, 43, 47, 48, 49, 55, 56, 60, 63)$.}
+ \label{fig:32-ec-from-bs64}
+\end{figure}
+
+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
+gute Schnittmuster anzugeben.
+
+Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen
+Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
+Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
+Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
+ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
+ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
+die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
+Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
+mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
+
+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.
+
+\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:oes}
+
+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
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+\hline
+ 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
+\oes{m}&19& 26 & 31 & 37 & 41 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\
+\hline
+\end{tabular}
+ \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}
+ \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}
+
+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.
+
+Wie beim \emph{bitonen Mergesort}-Netzwerk reicht auch beim
+\emph{Odd-Even-Mergesort}-Netzwerk ein einziger Schnitt nicht aus, um die
+Geschwindigkeit gegenüber \oes{m} zu verbessern. Bei $m = 11$ und $m = 12$ war
+jeweils mindestens ein 6-Schnittmuster notwendig, um eine höhere
+Geschwindigkeit zu erreichen.
+
+In Tabelle~\ref{tbl:ec-oes-19} sind die Ergebnisse von
+\textsc{SN-Evolution-Cut} für \oes{n}, $n = 20$ und $m = 19$ ($k = 1 \dots
+19$) aufgelistet. Mit $k = 10$ wird das erste mal ein schnelles
+19-Sortiernetzwerk mit 13~Schichten ausgegeben. Mit $k \geqq 11$ sind die
+resultierenden Netzwerke mit 93~Komparatoren effizienter als das Ergebnis mit
+$k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des
+\emph{bitonen Mergesort}-Netzwerks erreicht wurde (92~Komparatoren in
+13~Schichten, siehe Tabelle~\ref{tbl:ec-bs-19}), wird nicht erreicht.
+
+\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}
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $n$ & Komp. & Schichten \\
+ \hline
+ 20 & 91 & 14 \\
+ 21 & 91 & 14 \\
+ 22 & 91 & 14 \\
+ 23 & 91 & 14 \\
+ 24 & 91 & 14 \\
+ 25 & 91 & 14 \\
+ 26 & 91 & 14 \\
+ 27 & 91 & 14 \\
+ 28 & 91 & 14 \\
+ 29 & 95 & 13 \\
+ \rowcolor{green!10}
+ 30 & 93 & 13 \\
+ \rowcolor{green!10!white!95!black}
+ 31 & 93 & 13 \\
+ \rowcolor{green!10}
+ 32 & 93 & 13 \\
+ \rowcolor{green!10!white!95!black}
+ 33 & 93 & 13 \\
+ \rowcolor{green!10}
+ 34 & 93 & 13 \\
+ \rowcolor{green!10!white!95!black}
+ 35 & 93 & 13 \\
+ \rowcolor{green!10}
+ 36 & 93 & 13 \\
+ \rowcolor{green!10!white!95!black}
+ 37 & 93 & 13 \\
+ \rowcolor{green!10}
+ 38 & 93 & 13 \\
+ \hline
+ \bs{19} & 98 & 14 \\
+ \oes{19} & 91 & 14 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Komparatoren und Schichten von Sortiernetzwerken, die von
+ \textsc{SN-Evolution-Cut} mit \oes{n} und $k = n - 19$ ermittelt wurden. Erst mit $k = 10$
+ ist es möglich gegenüber \oes{19} eine Schicht einzusparen. Dafür ist die
+ Effizienz von 91~Komparatoren nicht mehr erreichbar.}
+ \label{tbl:ec-oes-19}
+\end{table}
+
+% 2-er Potenzen
+
+In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
+viele \emph{unterschiedliche} 16-Schnittmuster die konstruierten
+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{Ein
+entsprechendes Ergebnis wird meist nach 20.000 bis 100.000 Iterationen
+geliefert. Bei dieser Problemgröße erreicht die Implementierung (siehe
+Abschnitt~\ref{sect:implementierung}) etwa 20.000 Iterationen pro Sekunde auf
+derzeitigen Computern.} ein gutes 16-Schnittmuster findet.
+
+Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
+bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} ist, 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}
+ \end{center}
+ \caption{Visualisierung eines 16-Schnittmusters, das auf
+ $\operatorname{OES}(32)$ angewendet ein Sortiernetzwerk ergibt, das
+ bezüglich Geschwindigkeit und Effizienz identisch zu \oes{16} ist. Das
+ resultierende Sortiernetzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32}
+ dargestellt.}
+ \label{fig:16-ec-from-oes32-cut}
+\end{figure}
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-oes32.tex}
+ \end{center}
+ \caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten.
+ Das Netzwerk wurde aus dem \emph{Odd-Even-Mergesort}-Netzwerk \oes{32} mit
+ einem 16-Schnittmuster erzeugt, das von \textsc{SN-Evolution-Cut}
+ berechnet wurde. Das Schnittmuster ist in
+ Abbildung~\ref{fig:16-ec-from-oes32-cut} dargestellt.}
+ \label{fig:16-ec-from-oes32}
+\end{figure}
+
+% Regelmaessiges Schnittmuster fuer n = 2^d
+
+Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3,
+4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser
+Beobachtung kann das regelmäßige Schnittmuster