+Referenz zu 0-1-Prinzip.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index a1145c4..316954c 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -75,7 +75,7 @@
 \maketitle
 \begin{abstract}
 Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
 \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.
 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.


@@ -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}
 
 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
 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,7 +207,7 @@ Die Eingabe kann mittels
       1 & e_j > a_i
     \end{array} \right.
 \end{displaymath}
       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.
 Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das
 Verhalten jedes einzelnen Komparators nicht, so dass die Annahme auf einen
 Widerspruch geführt wird.


@@ -1012,7 +1013,7 @@ sich die Resultate auch in der ersten Schicht nicht unterscheiden.
 
 \begin{figure}
   \begin{center}
 
 \begin{figure}
   \begin{center}

-    \includegraphics[viewport=0 0 360 216,width=15cm]{images/count-cuts-16.pdf}
+    \includegraphics[viewport=0 0 425 262,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
   \end{center}
   \caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch
   8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und


@@ -1071,7 +1072,7 @@ unterschiedlichen Schnittmuster abschätzen.
 
 \begin{figure}
   \begin{center}
 
 \begin{figure}
   \begin{center}

-    \includegraphics[viewport=0 0 360 216,width=15cm]{images/collisions-10000-1000000-32.pdf}
+    \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
   \end{center}
   \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der
   \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und


@@ -1194,21 +1195,21 @@ Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert.
 Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von
 Pseudocode wie folgt beschreiben:
 \begin{verbatim}
 Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von
 Pseudocode wie folgt beschreiben:
 \begin{verbatim}

-Guetesumme := 0
+Gütesumme := 0

 Auswahl := (leer)
 
 Auswahl := (leer)
 

-fuer jedes Individuum in Population
+für jedes Individuum in Population

 {
 {

-  reziproke Guete := 1.0 / Guete(Individuum)
-  Wahrscheinlichkeit P := reziproke Guete / (reziproke Guete + Guetesumme)
-  Guetesumme := Guetesumme + reziproke Guete
+  reziproke Güte := 1.0 / Guete(Individuum)
+  Wahrscheinlichkeit P := reziproke Güte / (reziproke Güte + Gütesumme)
+  Gütesumme := Gütesumme + reziproke Güte

 
   mit Wahrscheinlichkeit P
   {
     Auswahl := Individuum
   }
 }
 
   mit Wahrscheinlichkeit P
   {
     Auswahl := Individuum
   }
 }

-gebe Auswahl zurueck
+gib Auswahl zurück

 \end{verbatim}
 
 \subsection{Rekombination}
 \end{verbatim}
 
 \subsection{Rekombination}


@@ -1226,7 +1227,7 @@ erhält.
 
 \subsection{Mutation}
 
 
 \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
 --~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 +1236,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
 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
 
 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 +1336,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.
 
 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
 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,28 +1530,44 @@ 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.
 
 $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
 
 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
+
+für n Iterationen
+{
+  Nachfolger := kombiniere (Netzwerk, Netzwerk)
+  Netzwerk   := Nachfolger
+}
+
+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 $n \leftarrow \mathrm{Input}$
-  \item \texttt{while} \textit{true}
-  \begin{itemize}
-    \item $n \leftarrow \operatorname{recombine} (n, n)$
-  \end{itemize}
-\end{itemize}

 
 \begin{itemize}
   \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
 
 \begin{itemize}
   \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).


@@ -1560,7 +1578,7 @@ selbst und erhält so einen zufälligen Nachfolger.
 
 \begin{figure}
   \begin{center}
 
 \begin{figure}
   \begin{center}

-  \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf}
+  \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-12-pct.pdf}

   \end{center}
   \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen),
   die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
   \end{center}
   \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen),
   die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die


@@ -1570,7 +1588,7 @@ selbst und erhält so einen zufälligen Nachfolger.
 
 \begin{figure}
   \begin{center}
 
 \begin{figure}
   \begin{center}

-  \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-14-pct.pdf}
+  \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf}

   \end{center}
   \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen),
   die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
   \end{center}
   \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen),
   die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die


@@ -1580,7 +1598,7 @@ selbst und erhält so einen zufälligen Nachfolger.
 
 \begin{figure}
   \begin{center}
 
 \begin{figure}
   \begin{center}

-  \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16-pct.pdf}
+  \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf}

   \end{center}
   \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen),
   die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
   \end{center}
   \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen),
   die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die


@@ -1588,6 +1606,16 @@ selbst und erhält so einen zufälligen Nachfolger.
   \label{fig:markov-comparators-16}
 \end{figure}
 
   \label{fig:markov-comparators-16}
 \end{figure}
 

+\begin{figure}
+  \begin{center}
+  \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf}
+  \end{center}
+  \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen),
+  die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
+  \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.}
+  \label{fig:markov-comparators-18}
+\end{figure}
+

 \newpage
 \section{Empirische Beobachtungen}
 
 \newpage
 \section{Empirische Beobachtungen}