+\begin{figure}
+ \begin{center}
+ \input{images/32-pairwise-cut-16-pairwise.tex}
+ \end{center}
+ \caption{PS(32) mit 16 Schnitten zu PS(16).}
+ \label{fig:ps16-from-ps32}
+\end{figure}
+
+Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
+regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk einen 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{Versuche mit dem Odd-Even-Mergesort-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.
+
+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}
+ \end{center}
+ \caption{Visualisierung eines 16-Schnittmusters, das auf
+ $\operatorname{OES}(32)$ angewendet wieder ein schnelles und effizientes
+ Sortiernetzwerk ergibt.}
+ \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 von dem Algorithmus \textsc{SN-Evolution-Cut} aus dem
+ \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(32)$ durch
+ 16~Schnitte erzeugt.}
+ \label{fig:16-ec-from-oes32}
+\end{figure}
+
+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 man das regelmäßige Schnittmuster
+\begin{displaymath}
+\textit{Eingang}_i = \left\{ \begin{array}{rl}
+ \infty & \quad \textrm{falls } i \bmod 4 = 0 \\
+ -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\
+ ? & \quad \mathrm{sonst}
+ \end{array} \right.
+\end{displaymath}
+ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der
+Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente
+Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein
+32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde,
+ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.
+
+\begin{figure}
+ \begin{center}
+ \input{images/32-ec-from-oes64.tex}
+ \end{center}
+ \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten.
+ Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem
+ \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.}
+ \label{fig:32-ec-from-oes64}
+\end{figure}
+
+Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so
+erzeugten Sortiernetzwerke die Effizienz des
+\emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster
+beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit
+43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit
+beider Sortiernetzwerke ist mit 10~Schichten identisch.
+
+Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24}
+und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der
+verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der
+Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20,
+22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in
+Abbildung~\ref{12-ec-from-oes24-efficient} zu sehen ist. Das resultierende
+Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet
+werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit
+gleichauf mit \oes{12}. Werden hingegen schnelle Sortiernetzwerke bevorzugt,
+werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
+16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
+dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
+sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten
+angeordnet sind. Das heißt, dass das resultierende Netzwerk zwar nicht so
+effizient wie \oes{12} ist, dafür aber schneller als \oes{12} und \bs{12}.
+
+\begin{figure}
+ \centering
+ \subfigure[Schnelles 12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten,
+ das von \textsc{SN-Evolution-Cut} aus dem \emph{Odd-Even-Mergesort}-Netzwerk
+ generiert
+ wurde.]{\input{images/12-ec-from-oes24-fast.tex}\label{fig:12-ec-from-oes24-fast}}
+ \subfigure[Effizientes 12-Sortiernetzwerk aus 41~Komparatoren in
+ 10~Schichten, das von \textsc{SN-Evolution-Cut} aus dem
+ \emph{Odd-Even-Mergesort}-Netzwerk generiert
+ wurde.]{\input{images/12-ec-from-oes24-efficient.tex}\label{fig:12-ec-from-oes24-efficient}}
+ \caption{Startet man \textsc{SN-Evolution-Cut} mit \oes{24}, hängt das
+ Ergebnis von der Bewertungsfunktion ab.}
+ \label{fig:12-ec-from-oes24}
+\end{figure}
+
+Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut}
+findet Sortiernetzwerke, die schneller sind als das entsprechende
+\emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das
+\emph{Odd-Even-Mergesort}-Netzwerk mit 22, 24, 38, 40, 42, 44 und 46
+Eingängen. In der folgenden Tabelle sind einige schnelle Netzwerke, die von
+\textsc{SN-Evolution-Cut} generiert werden können, charakterisiert. Die
+Eingabe für \textsc{SN-Evolution-Cut} war jeweils das
+\emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl.
+Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
+23-Sortiernetzwerk, das aus \oes{46} generiert wurde.
+\begin{center}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
+(Resultat) & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\
+\hline
+11 & 38 & 9 & 37 & 10 \\
+12 & 43 & 9 & 41 & 10 \\
+19 & 93 & 13 & 91 & 14 \\
+20 & 101 & 13 & 97 & 14 \\
+21 & 108 & 14 & 107 & 15 \\
+22 & 116 & 14 & 114 & 15 \\
+23 & 125 & 14 & 122 & 15 \\
+\hline
+\end{tabular}
+\end{center}
+
+\begin{figure}
+ \begin{center}
+ \input{images/23-ec-from-oes46-fast.tex}
+ \end{center}
+ \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten.
+ Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem
+ Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38,
+ 44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$
+ erzeugt.}
+ \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 verwendete immer zwei zufällige Sortiernetzwerke („Individuen“) aus
+einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander
+ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal
+verwendet und mit sich selbst kombiniert wird.