+\subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
+\label{sect:anzahl_schnittmuster}
+
+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 auf diese Art und
+Weise einen Sortiernetzwerke mit $2n$~Eingängen wieder auf Sortiernetzwerke
+mit $n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die
+nacheinander angewendet ein $n$-Sortiernetzwerk auf ein
+${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als
+\emph{$k$-Schnittmuster}.
+
+Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
+auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
+Schnittmuster \emph{unterschiedlich} bezüglich~$S$.
+
+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 ${(n-k)}$-Sortiernetzwerk zu reduzieren,
+ergeben sich insgesamt
+\begin{equation}\label{eqn:anzahl_schnittmuster}
+ \prod_{i=n}^{1+n-k} 2i = 2^k \frac{n!}{(n-k)!}
+ \quad (n > m)
+\end{equation}
+\emph{mögliche} Schnittmuster. Diese Schnittmuster 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 Schnittmuster reduziert,
+die Menge der so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die
+Anzahl der möglichen Schnittmuster setzt sich zusammen aus der Anzahl von
+Möglichkeiten, $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen
+Minimum-~/ Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl
+der möglichen Schnittmuster:
+\begin{displaymath}
+ 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
+ = 2^{k} \cdot \frac{n!}{k! (n-k)!}
+ = 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!}
+ \quad (1 \leqq k < n)
+\end{displaymath}
+
+Die Anzahl der möglichen Schnittmuster 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, ist ein Schmittmuster mit
+16~Schnitten notwendig, für das 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.
+
+Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
+als die Anzahl der möglichen Schnittmuster. Für jeden Komparator auf der
+ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
+Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
+unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
+der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die
+Werte unterscheiden.
+
+Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe
+Ausgangmuster abgebildet, weil die Position des Minimums beziehungsweise des
+Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun
+unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster
+erzeugen. In der zweiten und allen folgenden Schichten kann man diesen
+Unterschied nicht mehr erkennen. In allen sechs Fällen, in denen sich die
+Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass
+sich die Resultate auch in der ersten Schicht nicht unterscheiden.
+
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 360 216,width=15cm]{images/count-cuts-16.pdf}
+ \end{center}
+ \caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch
+ 8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
+ $\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der
+ unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das
+ \emph{Odd-Even-Mergesort-Netzwerk}, 4973 für das \emph{bitone
+ Mergesort-Netzwerk} und 18764 für das \emph{Pairwise-Sorting-Netzwerk}.}
+ \label{fig:count-cuts-16}
+\end{figure}
+
+Um die Anzahl der \emph{unterschiedlichen} Schnittmuster abschätzen zu können,
+wurden je eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke
+$\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$
+angewandt. Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
+\emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen
+Schnittmuster auf. Klar zu sehen ist, dass sich die Anzahl der erzeugten
+Sortiernetzwerke nach $500.000$~Iterationen nur noch gering verändert und der
+Wert nach $1.000.000$~Iterationen allem Anschein nach dem Endwert schon sehr
+nahe ist.
+
+Die Anzahl der 8-Schnittmuster ist entsprechend der
+Formel~\ref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen Schnittmuster
+führen aber nur zu wenigen \emph{unterschiedlichen} Sortiernetzwerken: 3519
+($\approx 0,1\%$) im Fall des \emph{Odd-Even-Mergesort-Netzwerks}, 4973
+($\approx 0,15\%$) beim \emph{bitonen Mergesort-Netzwerk} und 18764 ($\approx
+0,57\%$) beim \emph{Pairwise-Sorting-Netzwerk}. Zwar ist es möglich, dass mehr
+Iterationen die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt.
+Die Graphen in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der
+Annahme, dass die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
+vernachlässigbar klein ist.
+
+Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
+Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar. Um
+die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu können,
+kann man sich einer stochastischen Methode bedienen, der sogenannten
+\emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von
+$k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
+zufällig erzeugt und überprüft, ob sie sich in der Menge~$S$ enthalten sind.
+Unter der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$
+enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der
+unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der
+unterschiedlichen Schnittmuster abschätzen.
+
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
+ \end{center}
+ \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der
+ \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und
+ $\operatorname{BS}(32)$.}
+ \label{fig:collisions-10000-1000000-32}
+\end{figure}
+
+In Abbildung~\ref{fig:collisions-10000-1000000-32} ist das Ergebnis des
+Monte-Carlo-Algorithmus für 16-Schnittmuster zu sehen, die auf
+$\operatorname{OES}(32)$ und $\operatorname{BS}(32)$ angewandt wurden: Von
+jedem Sortiernetzwerk wurden zunächst eine Menge~$S$ von 10.000
+\emph{unterschiedlichen} Schnittmustern erzeugt. Anschließend wurden 1.000.000
+zufällige Schnittmuster erzeugt und der Anteil der zufälligen Schnittmuster,
+die \emph{äquivalent} zu einem in~$S$ enthalten Schnittmuster sind, berechnet.
+Für $\operatorname{OES}(32)$ war dieser Anteil etwa $0,19 \%$, für
+$\operatorname{BS}(32)$ etwa $0,29 \%$. Das ergibt eine Abschätzung von $5,2
+\cdot 10^6$ unterschiedlichen Schnittmustern für $\operatorname{OES}(32)$ und
+$3,4 \cdot 10^6$ für $\operatorname{BS}(32)$.
+
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf}
+ \end{center}
+ \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der
+ \emph{Monte-Carlo-Methode} für $\operatorname{PS}(32)$. 385 von 1.000.000
+ zufälligen Schnittmustern waren äquivalent zu einem Schnittmuster in einer
+ Menge von 100.000. Daraus ergibt sich eine Schätzung von $2,6 \cdot 10^8$
+ unterschiedlichen Schnittmustern.}
+ \label{fig:collisions-100000-1000000-32-ps}
+\end{figure}