BibTeX für Moritz Arbeit.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 5af502f..c0213f2 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.


@@ -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.
 
 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
 
 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}
 
 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,10 +207,19 @@ 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
 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
 
 Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
 Komplexitätsklasse


@@ -228,34 +238,35 @@ beschäftigen.
 
 Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
 entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
 
 Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
 entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse

-$NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte
-sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$
-liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese
-Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese
-Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer
-Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit
-praktikablen Zeitkonstanten gefunden werden.
+\textit{NP}, das heißt das keine Verfahren bekannt sind, die das Problem
+effizient exakt lösbar. Sollte sich herausstellen, dass diese Probleme nicht
+in der Komplexitätsklasse~\textit{P} liegen, wäre eine Konsequenz, dass es
+effiziente exakte Algorithmen für diese Probleme nicht geben kann. Falls sich
+hingegen herausstellt, dass diese Probleme in der
+Komplexitätsklasse~\textit{P} liegen, wird es mit großer Wahrscheinlichkeit
+noch einige Zeit dauern, bis auch Algorithmen mit praktikablen Zeitkonstanten
+gefunden werden.

 
 Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
 
 Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt

-die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus
-zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser
-Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
-beispielsweise immitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
+die beziehungsweise eine der {\em optimalen} Lösungen als einzige Ausgabe des
+Algorithmus zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele
+dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
+beispielsweise imitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen

 auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
 
 Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
 auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
 
 Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee

-ist es, bestehende Lösungen zu neuen, unter Umständen besseren Lösungen zu
+ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu

 kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
 kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten

-Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem häufig
-als {\em Individuum} bezeichnet.
+Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem als {\em
+Individuen} bezeichnet.

 
 Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
 
 Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer

-bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen
+bestehenden Lösungsmenge, der {\em Population}, werden zufällig Lösungen

 ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
 Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
 verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
 ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
 Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
 verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge

-integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
-Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
+eingefügt wird. Die verwendeten Wahrscheinlichkeiten, beispielsweise bei der
+{\em Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise

 werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
 Gütefunktion}.
 
 werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
 Gütefunktion}.
 


@@ -686,7 +697,7 @@ benötigt werden.
 Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie
 das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
 sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die
 Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie
 das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
 sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die

-effizientesten Sortiernetzwerke in Bezuf auf Komparator- und Schichtzahl
+effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl

 entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
 $\operatorname{OES}(n)$ aus
 $\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$,
 entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
 $\operatorname{OES}(n)$ aus
 $\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$,


@@ -716,7 +727,7 @@ die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
 die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
 
 Im Allgemeinen ist die Anzahl der Komparatoren, die vom
 die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
 
 Im Allgemeinen ist die Anzahl der Komparatoren, die vom

-\emph{Odd-Even-Mergesort-Netzwerk} verwendet wird, $k(n)$, direkt aus der
+\emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der

 Definition beziehungsweise der Konstruktionsanleitung abzulesen:
 \begin{displaymath}
   k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
 Definition beziehungsweise der Konstruktionsanleitung abzulesen:
 \begin{displaymath}
   k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)


@@ -750,16 +761,24 @@ gilt.
 
 \subsection{Komprimieren}
 
 
 \subsection{Komprimieren}
 

-\todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}
-

 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
 gleichzeitig ausgewertet werden, wie bereits in
 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
 gleichzeitig ausgewertet werden, wie bereits in

-Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
-\emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
-von \emph{Schichten} verstanden.
+Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Durch manche
+Transformationen, insbesondere das Entfernen einer Leitung, das in
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben wird, kann es vorkommen,
+dass die Komparatoren eines Sortiernetzwerks nicht mehr in der
+kleinstmöglichen Anzahl von \emph{Schichten} angeordnet sind. Unter
+\emph{Komprimierung} wird eine (Neu-)Gruppierung der Komparatoren verstanden,
+die jeden Komparator so früh wie möglich ausführt. So entsteht die
+kleinstmögliche Anzahl von \emph{Schichten}, in die sich ein Sortiernetzwerk
+unterteilen lässt.

 
 Diese Anzahl ist insbesondere beim automatisierten Bewerten von
 
 Diese Anzahl ist insbesondere beim automatisierten Bewerten von

-Komparatornetzwerken interessant. \dots
+Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung}
+beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
+Komparatoren später angewandt werden. Deshalb sollte vor einer Bewertung, die
+die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
+Komprimierung durchgeführt werden.

 
 \subsection{Normalisieren}
 
 
 \subsection{Normalisieren}
 


@@ -776,8 +795,8 @@ Komparatornetzwerken interessant. \dots
 Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
 ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
 zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
 Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
 ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
 zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante

-transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis})
-einen Algorithmus an.
+transformiert werden. Dazu gibt beispielsweise \emph{Donald~E. Knuth}
+in~\cite{KNUTH} einen Algorithmus an.

 
 Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
 bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
 
 Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
 bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}


@@ -861,7 +880,8 @@ nur mit exponentiellem Aufwand möglich ist.
 %\item Nach dem Pairwise sorting-network Schema.
 %\end{itemize}
 
 %\item Nach dem Pairwise sorting-network Schema.
 %\end{itemize}
 

-\subsection{Leitungen entfernen}\label{sect:leitungen_entfernen}
+\subsection{Leitungen entfernen}
+\label{sect:leitungen_entfernen}

 
 Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von
 \emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
 
 Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von
 \emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen


@@ -961,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.
 
 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
 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


@@ -1002,7 +1022,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


@@ -1127,16 +1147,16 @@ Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
 {\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
 die bei Sortiernetzwerken verfolgt werden können:
 \begin{itemize}
 {\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
 die bei Sortiernetzwerken verfolgt werden können:
 \begin{itemize}

-  \item Möglichst wenige Komparatoren („billig“)
+  \item Möglichst wenige Komparatoren („effizient“)

   \item Möglichst wenige Schichten („schnell“)
 \end{itemize}
 
 Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
   \item Möglichst wenige Schichten („schnell“)
 \end{itemize}
 
 Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das

-billigste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
-in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
-9~Schichten.
+effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus
+60~Komparatoren in 10~Schichten. Das schnellste Netzwerk besteht aus
+61~Komparatoren in nur 9~Schichten.

 
 

-Eine Gütefunktion, die die beiden Ziele "`billig"' und "`schnell"'
+Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'

 berücksichtigen kann, hat die folgende allgemeine Form:
 \begin{equation}
   \operatorname{Guete}(S) = w_{\mathrm{Basis}}
 berücksichtigen kann, hat die folgende allgemeine Form:
 \begin{equation}
   \operatorname{Guete}(S) = w_{\mathrm{Basis}}


@@ -1151,10 +1171,10 @@ jegliche Ergebnisse sind dann rein zufälliger Natur.\footnote{Dass dies nicht
 so schlecht ist wie man intuitiv vermuten könnte, zeigt der
 \textsc{SN-Markov}-Algorithmus in Abschnitt~\ref{sect:markov}.}
 
 so schlecht ist wie man intuitiv vermuten könnte, zeigt der
 \textsc{SN-Markov}-Algorithmus in Abschnitt~\ref{sect:markov}.}
 

-Da möglichst billige und schnelle Sortiernetzwerke gefunden werden sollen, ist
-ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert. Das
-heißt, dass das Ziel von \textsc{SN-Evolution} ist, $\operatorname{Guete}(S)$
-zu \emph{minimieren}.
+Da möglichst effiziente und schnelle Sortiernetzwerke gefunden werden sollen,
+ist ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert.
+Das heißt, dass das Ziel von \textsc{SN-Evolution} ist,
+$\operatorname{Guete}(S)$ zu \emph{minimieren}.

 
 Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
 genommen werden. Ist er groß, wird der relative Unterschied der Güten
 
 Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
 genommen werden. Ist er groß, wird der relative Unterschied der Güten


@@ -1184,21 +1204,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}


@@ -1216,7 +1236,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


@@ -1225,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
 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


@@ -1324,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.
 
 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


@@ -1518,28 +1539,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}).


@@ -1550,7 +1587,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


@@ -1560,7 +1597,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


@@ -1570,7 +1607,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


@@ -1578,6 +1615,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}