\newcommand{\todo}[1]{{\bf TODO:} #1}
\newcommand{\qed}{\hfill $\Box$ \par \bigskip}
+\newcommand{\oes}[1]{\ensuremath{\operatorname{OES}(#1)}}
+\newcommand{\bs}[1]{\ensuremath{\operatorname{BS}(#1)}}
+\newcommand{\ps}[1]{\ensuremath{\operatorname{PS}(#1)}}
+\newcommand{\oem}[1]{\ensuremath{\operatorname{OEM}(#1)}}
+\newcommand{\bm}[1]{\ensuremath{\operatorname{BM}(#1)}}
+
\newtheorem{definition}{Definition}
\newtheorem{satz}{Satz}
\end{displaymath}
auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme vom
Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das
-Verhalten jedes einzelnen Komparators nicht, so dass die Annahme auf einen
-Widerspruch geführt wird.
+Verhalten jedes einzelnen Komparators nicht: Wenn bei der Permutation eine
+Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen
+wurden, liegen jetzt entsprechend eine Null und eine Eins an, die genauso
+vertauscht werden oder nicht, wie das bei der Permutation der Fall war. Liegen
+zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als $a_i$
+oder zwei Zahlen größer oder gleich $a_i$. Da im Fall der 0-1-Folge zwei
+gleiche Zahlen am Komparator anliegen, dürfen wir davon ausgehen, dass sich
+der Komparator so verhält, wie er sich bei der Permutation verhalten hat --
+ohne das Ergebnis zu beeinflussen. Entsprechend kommen an den Ausgängen $i-1$
+und $i$ eine Null und eine Eins in der falschen Reihenfolge an. Das steht im
+Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden.
Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
Komplexitätsklasse
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)!}
+ \prod_{i=n}^{1+n-k} 2i = 2^k \cdot \frac{n!}{(n-k)!}
\quad (n > m)
\end{equation}
\emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
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
+\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, 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
der \emph{unterschiedlichen} Schnittmuster auf höchstens $\frac{2}{3}$ der
\emph{möglichen} Schnittmuster reduziert werden. Um die Anzahl der
\emph{unterschiedlichen} Schnittmuster experimentell zu ermitteln, wurden je
-eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke
-$\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$
-angewandt. Anschließend wurde mithilfe einer Hashtabelle überprüft, ob das
-resultierende Sortiernetzwerk schon von einem \emph{äquivalenten}
-Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk noch nicht in der
-Hashtabelle enthalten war, wurde der Zähler für unterschiedliche Schnittmuster
-erhöht und das Sortiernetzwerk eingefügt.
+eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke \oes{16},
+\bs{16} und \ps{16} angewandt. Anschließend wurde mithilfe einer Hashtabelle
+überprüft, ob das resultierende Sortiernetzwerk schon von einem
+\emph{äquivalenten} Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk
+noch nicht in der Hashtabelle enthalten war, wurde der Zähler für
+unterschiedliche Schnittmuster erhöht und das Sortiernetzwerk eingefügt.
Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
\emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen
nahe ist.
Die Anzahl der möglichen 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
+Formel~\eqref{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.
-Die Hashtabelle benötigt mehr Arbeitsspeicher als in derzeitigen Rechnern
-vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für
-„kleine“ x-Werte verlässt.
+Die Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen
+Rechnern vorhanden ist, bevor ein entsprechender Graph den linearen Bereich
+für „kleine“ x-Werte verlässt.
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
+zufällig erzeugt und überprüft, ob sie 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.
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)$.
+\cdot 10^6$ unterschiedlichen 16-Schnittmustern für $\operatorname{OES}(32)$
+und $3,4 \cdot 10^6$ für $\operatorname{BS}(32)$.
\begin{figure}
\begin{center}
unterschiedlichen 8-Schnittmuster für $\operatorname{PS}(16)$ in
Abbildung~\ref{fig:count-cuts-16} bereits mehr als dreimal größer war als die
Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$,
-ist dieser Umstand wenig verwunderlich. In einem kombinierten Graphen hätte
-man keine Details mehr erkennen können. Aufgrund der hohen Anzahl
-unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit
+ist dieser Umstand wenig verwunderlich. Entsprechend hätte man in einem
+kombinierten Graphen keine Details mehr erkennen können. Aufgrund der hohen
+Anzahl unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit
$\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedilchen
Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent
Zu einem vollständigen evolutionären Algorithmus gehört außerdem die Mutation
--~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
-Sortiernetzwerk zufällig zu verändern aber trotzdem die Sortiereigenschaft zu
+Sortiernetzwerk zufällig zu verändern und dabei die Sortiereigenschaft zu
erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
Eigenschaft zerstören.
Ausprobieren aller $2^n$~Bitmuster, wie in Abschnitt~\ref{sect:0-1-prinzip}
beschrieben.
-Um das Potenzial einer Mutation abzuschätzen habe ich in den evolutionären
-Algorithmus eine Überprüfung eingebaut. Unmittelbar vor dem Einfügen in die
-Population überprüft das Programm die Notwendigkeit jedes einzelnen
-Komparators. Dazu wurde nacheinander jeder Komparator entfernt und überprüft,
-ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt.
+Um das Potenzial einer Mutation abzuschätzen wurde in \textsc{SN-Evolution}
+eine Überprüfung eingebaut: Unmittelbar vor dem Einfügen in die Population
+überprüft eine Funktion die Notwendigkeit jedes einzelnen Komparators. Dazu
+wird nacheinander jeder Komparator entfernt und überprüft, ob das verbleibende
+Netzwerk die Sortiereigenschaft noch besitzt.
-\begin{itemize}
-\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
-Schichten, kobiniert)
-\item Rekombination: Merge Anhängen und Leitungen entfernen.
-\end{itemize}
+Trotz des hohen Rechenaufwandes -- bei 16-Sortiernetzwerken sind gut
+4~Millionen Tests notwendig, um alle Komparatoren zu überprüfen -- waren die
+Ergebnisse ernüchternd: Nach circa 1~Million Iterationen mit
+16-Sortiernetzwerken fand der so modifizierte Algorithmus keinen einzigen
+Komparator, den er hätte entfernen können.
-Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt
-Abbildung~\ref{fig:evolutionary_08}.
+\subsection{Güte}
-\begin{figure}
-\begin{center}
-\input{images/evolutionary-08.tex}
-\end{center}
-\caption{Ein mit dem evolutionären Algorithmus erzeugtes Sortiernetzwerk mit
-acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
-\label{fig:evolutionary_08}
-\end{figure}
+Die Qualität der erreichten Sortiernetzwerke wurde mit eine Gütefunktion
+beurteilt, die entsprechend dem im Abschnitt~\ref{sect:bewertung}
+vorgestellten Muster definiert ist. Wie beschrieben müssen die Faktoren häufig
+an die aktuelle Problemgröße angepasst werden, damit \textsc{SN-Evolution}
+schnell gute Ergebnisse liefert. Als guter Standardansatz haben sich die
+folgenden Werte herausgestellt:
+\begin{eqnarray*}
+w_{\mathrm{Basis}} &=& 0 \\
+w_{\mathrm{Komparatoren}} &=& 1 \\
+w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
+\end{eqnarray*}
-\begin{figure}
-\begin{center}
-\input{images/08-e2-1237993371.tex}
-\end{center}
-\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
-\label{fig:08-e2-1237993371}
-\end{figure}
+\subsection{Versuche mit dem bitonen Mischer}
\begin{figure}
-\begin{center}
-\input{images/09-e2-1237997073.tex}
-\end{center}
-\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
-\label{fig:09-e2-1237997073}
+ \begin{center}
+ \input{images/16-e1-bitonic-1296542566.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers}
+ erzeugt.}
+ \label{fig:16-e1-bitonic-1296542566}
\end{figure}
-\begin{figure}
-\begin{center}
-\input{images/09-e2-1237999719.tex}
-\end{center}
-\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten}
-\label{fig:09-e2-1237999719}
-\end{figure}
+Verwendet man den \emph{bitonen Mischer} in der Rekombinationsphase von
+\textsc{SN-Evolution}, so erhält man Netzwerke wie das in
+Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte: Der Algorithmus
+wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als triviale
+Initiallösung gestartet. Das Ergebnis ist ein Netzwerk, das effizienter ist
+als das bitone Mergesort-Netzwerk: $\operatorname{BS}(16)$ benötigt
+80~Komparatoren, das Sortiernetzwerk in
+Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67.
+
+\subsection{Versuche mit dem Odd-Even-Mischer}
\begin{figure}
-\begin{center}
-\input{images/10-e2-1239014566.tex}
-\end{center}
-\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
-\label{fig:10-e2-1239014566}
+ \begin{center}
+ \input{images/16-e1-oddeven-1296543330.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even-Mischers}
+ erzeugt.}
+ \label{fig:16-e1-oddeven-1296543330}
\end{figure}
-\subsection{Güte}
+Leider lies sich das Ergebnis des bitonen Mischers -- das von
+\textsc{SN-Evolution} ausgegebene Netzwerk war effizienter als das rekursiv
+aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem
+\emph{Odd-Even-Mischer} nicht wiederholen. Zwar erreichen die
+Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
+\emph{Odd-Even-Mischers} findet, das \emph{Odd-Even-Mergesort}-Netzwerk
+bezüglich Schnelligkeit und Effizienz, ein Beispiel hierfür ist in
+Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Ein Netzwerk, das
+$\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch
+nicht beobachtet werden.
\begin{itemize}
-\item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}.
-\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
+\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der Schichten, kombiniert)
+\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \emph{Mischer} ab.
\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
+\item Möglicherweise: Verwende den rekursiven Aufbau des \emph{Pairwise-Sorting}-Netzwerks um Sortiernetzwerke zu mergen.
\end{itemize}
+%\begin{figure}
+%\begin{center}
+%\input{images/08-e2-1237993371.tex}
+%\end{center}
+%\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
+%\label{fig:08-e2-1237993371}
+%\end{figure}
+%
+%\begin{figure}
+%\begin{center}
+%\input{images/09-e2-1237997073.tex}
+%\end{center}
+%\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
+%\label{fig:09-e2-1237997073}
+%\end{figure}
+%
+%\begin{figure}
+%\begin{center}
+%\input{images/09-e2-1237999719.tex}
+%\end{center}
+%\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten}
+%\label{fig:09-e2-1237999719}
+%\end{figure}
+%
+%\begin{figure}
+%\begin{center}
+%\input{images/10-e2-1239014566.tex}
+%\end{center}
+%\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
+%\label{fig:10-e2-1239014566}
+%\end{figure}
+
%\input{shmoo-aequivalenz.tex}
\newpage
Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
gute Schnittmuster gesucht.
-Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster}
-als Individuen. Um zwei Individuen zu rekombinieren werden die ersten
-$r$~Schnitte des einen Schnittmusters verwendet und die letzten
-${c-r}$~Schnitte des zweiten Schmittmusters. $r$ ist eine Zufallsvariable mit
-$0 \leqq r \leqq c$.
+Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster},
+die in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als
+Individuen. Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte
+des einen Schnittmusters verwendet und die letzten ${c-r}$~Schnitte des
+zweiten Schmittmusters. $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
strukturell identisch zu $\operatorname{PS}(8)$ sind -- lediglich die
Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
-\begin{displaymath}
-\textit{Eingang}_i = \left\{ \begin{array}{rl}
- -\infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{0, 6\} \\
- \infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{2, 4\} \\
- ? & \quad \mathrm{sonst}
- \end{array} \right.
-\end{displaymath}
-
\begin{figure}
\begin{center}
\input{images/32-pairwise-cut-16-pairwise.tex}
\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}
\label{fig:16-pairwise}
\end{figure}
-Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann
-man $\operatorname{OES}(8)$ erhalten.
+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 Verwandschaft 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}
-\todo{Schreibe noch etwas zum 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 ein gutes 16-Schnittmuster findet.
-\begin{itemize}
- \item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort.
- \item Wie gut kann man durch wegschneiden werden?
- \item Wieviele Schnitte ergeben das selbe Netzwerk? Oder andersrum: Wieviele
- unterschiedliche Netzwerke kann ich erhalten? Wieviele Nachfolger hat ein
- Netzwerk / Knoten in der Markov-Kette?
- \item Abschnitt „Optimierung der Schnitte“ hier einbauen.
-\end{itemize}
+Eines der eher zufälligen Schnittmuster 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}
\newpage
\section{Der \textsc{SN-Markov}-Algorithmus}
projects / diplomarbeit.git / blobdiff