\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.
\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
projects / diplomarbeit.git / blobdiff