X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=c0213f2c4b4596093891772c68de0885916bc83c;hb=c145acd32aa61c8e213cd1a15ccf79bf30563a5e;hp=2f8aed20c51d4a8c79fecd497dd63e859b09d00a;hpb=32219a1257de0ea2fb64ac4e6146a60d23840929;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 2f8aed2..c0213f2 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -75,7 +75,7 @@ \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. @@ -175,12 +175,12 @@ Definition handelt es sich bei dem \emph{Komparatornetzwerk} folglich 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 @@ -189,6 +189,7 @@ Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$ 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 @@ -206,10 +207,19 @@ Die Eingabe kann mittels 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 @@ -971,7 +981,7 @@ 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 +\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 @@ -1226,7 +1236,7 @@ erhält. \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 @@ -1235,7 +1245,8 @@ Eigenschaft zerstören. 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 @@ -1334,7 +1345,7 @@ 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 +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 @@ -1528,33 +1539,45 @@ Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $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.