\maketitle
\begin{abstract}
Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
-vorgestellt (Off-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
+vorgestellt (Odd-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
Evolutionäre Algorithmen werden beschrieben und ein evolutionärer
Algorithmus für die Optimierung von Sortiernetzwerken wird angegeben.
gegebenes Komparatornetzwerk zu finden ist nach heutigem Kenntnisstand jedoch
nicht \emph{effizient} möglich.
-Beispielsweise sortiert das Komparatornetzwerk in
-Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880 möglichen
-Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4, 8, 6)$
-lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die
-Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge
-$(1, 0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt.
+Beispielsweise sortiert das im Rahmen dieser Arbeit entdeckte
+Komparatornetzwerk in Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880
+möglichen Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4,
+8, 6)$ lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die
+Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge $(1,
+0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt.
Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein
Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese
Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen
ist.\footnote{1.307.674.368.000 Permutationen}
+\label{sect:0-1-prinzip}
Glücklicherweise reicht es aus, alle möglichen 0-1-Folgen zu überprüfen, wie
\textit{Donald~E. Knuth} in \cite{KNUTH} zeigt. Die Beweisidee ist folgende:
Angenommen ein Komparatornetzwerk sortiert alle 0-1-Folgen und es gibt eine
1 & e_j > a_i
\end{array} \right.
\end{displaymath}
-auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme von
+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
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
\subsection{Mutation}
-Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine Mutation
+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
erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
-Ausprobieren aller $2^n$~Bitmuster.
+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
sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert
werden, Komparatoren ein.
-Beispeilsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
+Beispielsweise 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
$S_0$ ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
selbst erzeugen kann.
-Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben ist die Anzahl
-(unterschiedlicher) Schnittmuster und damit die Anzahl der Nachfolger sehr
-groß. Wenn $S_0$ ein Sortiernetzwerk mit $n$~Leitungen ist, so hat $S_0$ bis
-zu
-\begin{displaymath}
- 2^n \cdot \left( \begin{array}{c} 2n \\ n \end{array} \right)
-\end{displaymath}
-Nachfolger.
+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 20000, bei den untersuchten 32-Sortiernetzwerken
+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.
+selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt dich der
+Algorithmus wie folgt beschreiben:
\begin{verbatim}
- Netzwerk := Eingabe
+Netzwerk := Eingabe
- für n Iterationen
- {
- Nachfolger := kombiniere (Netzwerk, Netzwerk)
- Netzwerk := Nachfolger
- }
+für n Iterationen
+{
+ Nachfolger := kombiniere (Netzwerk, Netzwerk)
+ Netzwerk := Nachfolger
+}
- gib Netzwerk zurück
+gib Netzwerk zurück
\end{verbatim}
+\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}
+
+
\begin{itemize}
\item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
\item Anzahl der erreichbaren Sortiernetzwerke.
projects / diplomarbeit.git / blobdiff