+Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
+Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
+$n-3$,~\dots Eingängen zu erzeugen. Insbesondere können wir auf diese Art und
+Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
+mit $n$~Eingängen reduzieren.
+
+Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
+Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
+auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
+ein $n$-Sortiernetzwerk auf ein $m$-Sortiernetzwerk zu reduzieren, ergeben
+sich insgesamt
+\begin{displaymath}
+ \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
+ \quad (n > m)
+\end{displaymath}
+Möglichkeiten. Diese Möglichkeiten sind nicht alle unterschiedlich. Legt man
+beispielsweise das Minimum auf die unterste Leitung und das Maximum auf die
+oberste Leitung eines Standard-Sortiernetzwerks, führen beide Reihenfolgen zum
+selben Ergebnis.
+
+\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass
+es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise
+Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnitte
+reduziert, die Menge der erreichbaren Sortiernetzwerke bleibt aber
+unverändert. Die Anzahl der möglichen „Schnittmuster“ setzt sich zusammen aus
+der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
+und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
+Formel:
+\begin{displaymath}
+ 2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
+ = 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
+ = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!}
+ \quad (n > m)
+\end{displaymath}
+
+Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden
+Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
+ein Sortiernetzwerk mit 16~Eingängen zu reduzieren sind 16~Schnitte notwendig,
+für die es bereits etwa ${3,939 \cdot 10^{13}}$ Möglichkeiten gibt. Ein
+Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter
+erheblichem Ressourcenaufwand möglich.
+
+Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
+Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
+Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
+möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
+Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
+gute Schnittmuster gesucht.
+
+Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die
+\emph{Schnitt-Sequenzen} als Individuen. Eine \emph{Schnitt-Sequenz} ist eine
+Liste mit $c$~Schnitten, die jeweils durch die Start-Leitung und die Richtung
+\textit{Min} beziehungsweise \textit{Max} gegeben ist. Der Algorithmus wendet
+jeden Schnitt einzeln an, so dass eine Leitungsnummer mehrfach in einer
+Schnittsequenz vorkommen kann. Die höchste zulässige Leitungsnummer ist
+abhängig von der Position des Schnitts in der Sequenz. Der Schnitt an
+Position~$i$ darf höchstens die Leitungsnummer~${n-i-1}$
+enthalten.\footnote{Die niedrigste Leitungsnummer ist $0$, die höchste
+Leitungsnummer eines $n$-Sortiernetzwerks ist $n-1$.}
+
+Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte der einen
+Schnitt-Sequenz verwendet und die letzten ${c-r}$~Schnitte der zweiten
+Sequenz. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.
+
+Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
+auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
+Schnitt-Richtung.
+
+In ihrer Arbeit \textit{“Improving Bitonic Sorting by Wire Elimination”}
+zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka}, wie man einen
+bitonen Mischer, der nach Batchers Methode konstruiert wurde, durch
+systematisches Entfernen von Leitungen in einen ebenfalls bitonen Mischer mit
+der Hälfte der Leitungen transformiert. Diese alternativen Mischer sparen im
+Vergleich zu den Mischern, die nach Batchers Methode konstruiert werden,
+Komparatoren ein.
+
+Beispeilsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
+Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
+konstruiert wurde. Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger
+als das bitone Mergesort-Netzwerk nach Batchers Methode. Gegenüber Batchers
+Methode sparen so konstruierte Sortiernetzwerke ${\frac{1}{4}n(\log n - 1)}$
+Komparatoren ein.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-1277186619.tex}
+ \end{center}
+ \caption{{\tt images/16-ec-1277186619.tex}: Sortiernetzwerk mit 16~Leitungen
+ und 68~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem
+ Algorithmus \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
+ $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
+ \label{fig:16-ec-1277186619}
+\end{figure}
+
+Startet man {\sc SN-Evolution-Cut} mit dem bitonen Mergesort-Netzwerk
+$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
+Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
+16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in
+Abbildung~\ref{fig:16-ec-1277186619} zu sehen.
+