Diverses.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 7273cbe..b5d8a09 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -41,6 +41,7 @@
 \newcommand{\ps}[1]{\ensuremath{\operatorname{PS}(#1)}}
 \newcommand{\oem}[1]{\ensuremath{\operatorname{OEM}(#1)}}
 \newcommand{\bm}[1]{\ensuremath{\operatorname{BM}(#1)}}
 \newcommand{\ps}[1]{\ensuremath{\operatorname{PS}(#1)}}
 \newcommand{\oem}[1]{\ensuremath{\operatorname{OEM}(#1)}}
 \newcommand{\bm}[1]{\ensuremath{\operatorname{BM}(#1)}}

+\newcommand{\oet}[1]{\ensuremath{\operatorname{OET}(#1)}}

 
 \newtheorem{definition}{Definition}
 \newtheorem{satz}{Satz}
 
 \newtheorem{definition}{Definition}
 \newtheorem{satz}{Satz}


@@ -98,6 +99,7 @@ das hinbekomme bzw. Recht behalte.}
 
 \subsection{Motivation}\label{sect:motivation}
 
 
 \subsection{Motivation}\label{sect:motivation}
 

+\todo{Schreibe noch etwas zu …}

 \begin{itemize}
 \item Sortiernetzwerke sind toll, weil $\ldots$
 \item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
 \begin{itemize}
 \item Sortiernetzwerke sind toll, weil $\ldots$
 \item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.


@@ -327,12 +329,55 @@ Sortiereigenschaft erhält. Transformationen von Sortiernetzwerken werden in
 Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der Mutation
 einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
 
 Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der Mutation
 einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
 

+
+\begin{figure}
+  \begin{center}
+    \input{images/16-hillis.tex}
+  \end{center}
+  \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1992} angibt.
+  Es besteht aus 61~Komparatoren in 11~Schichten.}
+  \label{fig:16-hillis}
+\end{figure}
+Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
+Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete
+\emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“
+zu optimieren~\cite{H1992}. Diese \emph{Parasiten} genannten Eingaben wurden
+daran gemessen, bei wievielen Komparatornetzwerken sie beweisen konnten, dass
+sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen~/
+Komparatornetzwerken nicht alle 0-1-Folgen, sondern nur erfolgreiche
+Parasiten~/ schwierige Eingaben überprüft werden. Auf diese Art und Weise
+gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren
+anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist.
+
+\begin{figure}
+  \centering
+  \subfigure{\input{images/13-juille-0.tex}}
+  \subfigure{\input{images/13-juille-1.tex}}
+  \caption{13-Sortiernetzwerke, die von \textit{Hugues Juillé} mithilfe des
+  END-Algorithmus gefunden wurden. Sie bestehen jeweils aus 45~Komparatoren in
+  10~Schichten.}
+  \label{fig:13-juille}
+\end{figure}
+\textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving
+Non-Determinism} (END) nannte. Dabei handelt es sich nicht um einen
+\emph{Evolutionären Algorithmus}, wie sie hier vorgestellt wurden, sondern um
+eine verteilte, probabilistische Breitensuche, die an die \emph{Strahlsuche}
+(englisch: \textit{beam search}), ein Verfahren der Künstlichen Intelligenz,
+angelehnt ist. Die aufwendigste Operation bei diesem Ansatz ist die
+Bewertungsfunktion, die abschätzt, wieviele Komparatoren zu einem
+Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu
+erhalten. Mit diesem Ansatz gelang es \textit{Juillé} zwei 13-Sortiernetzwerke
+anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin
+Bekannten (Abbildung~\ref{fig:13-juille}).
+

 \newpage
 \section{Bekannte konstruktive Sortiernetzwerke}
 \label{sect:konstruktive_netzwerke}
 
 Übersicht über bekannte konstruktive Sortiernetzwerke.
 
 \newpage
 \section{Bekannte konstruktive Sortiernetzwerke}
 \label{sect:konstruktive_netzwerke}
 
 Übersicht über bekannte konstruktive Sortiernetzwerke.
 

+\todo{Einleitungssatz}
+

 \subsection{Das Odd-Even-Transpositionsort-Netzwerk}
 \label{sect:odd_even_transpositionsort}
 
 \subsection{Das Odd-Even-Transpositionsort-Netzwerk}
 \label{sect:odd_even_transpositionsort}
 


@@ -389,7 +434,7 @@ Schichten.
 
 Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei
 sortierte Listen zusammenfügen (englisch: \textit{to~merge}) kann. Dieser
 
 Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei
 sortierte Listen zusammenfügen (englisch: \textit{to~merge}) kann. Dieser

-\emph{„bitoner Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein
+\emph{„bitone Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein

 verleiht dem Sortiernetzwerk seinen Namen.
 
 Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
 verleiht dem Sortiernetzwerk seinen Namen.
 
 Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die


@@ -398,20 +443,20 @@ Es ist jedoch möglich das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
 
 \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
 
 
 \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
 

-Das \emph{bitone Mergesort-Netzwerk} basiert auf dem sogenannten \emph{bitonen
-Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine beliebige
-\emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine \emph{bitone
-Folge} ist eine monoton steigende Folge gefolgt von einer monoton absteigenden
-Folge, oder ein zyklischer Shift davon. Abbildung~\ref{fig:beispiel-biton}
-zeigt die vier prinzipiellen Möglichkeiten die durch zyklische Shifts
-entstehen können. Die wichtigsten Varianten für das \emph{bitone
-Mergesort-Netzwerk} zeigen die Abbildungen~\ref{fig:beispiel-biton-0}
-und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und
-eine absteigend sortierte Liste aneinanderhängt. Bei den anderen beiden Formen
-ist wichtig zu beachten, dass das letzte Element nicht größer
-(Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner
-(Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein
-darf.
+Das \emph{bitone Mergesort}-Netzwerk basiert auf dem sogenannten \emph{bitonen
+Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine
+beliebige \emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine
+\emph{bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton
+absteigenden Folge, oder ein zyklischer Shift davon.
+Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinzipiellen Möglichkeiten
+die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für das
+\emph{bitone Mergesort}-Netzwerk zeigen die
+Abbildungen~\ref{fig:beispiel-biton-0} und~\ref{fig:beispiel-biton-1}. Sie
+erhält man, wenn man eine aufsteigend und eine absteigend sortierte Liste
+aneinanderhängt. Bei den anderen beiden Formen ist wichtig zu beachten, dass
+das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) bzw.
+kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge
+sein darf.

 
 \begin{figure}
   \centering
 
 \begin{figure}
   \centering


@@ -503,10 +548,9 @@ alle Komparatoren in die gleiche Richtung zeigen.
   \begin{center}
   \input{images/batcher-8.tex}
   \end{center}
   \begin{center}
   \input{images/batcher-8.tex}
   \end{center}

-  \caption{$\operatorname{BS}(8)$, Batchers {\em bitones Mergesort-Netzwerk}
-  für acht Eingänge. Markiert sind die beiden Instanzen von
-  $\operatorname{BS}(4)$ (rot), die beiden bitonen
-  Mischer~$\operatorname{BM}(4)$ (blau) und die Komparatoren, die im letzten
+  \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für acht
+  Eingänge. Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden
+  bitonen Mischer~\bm{4} (blau) und die Komparatoren, die im letzten

   rekursiven Schritt hinzugefügt wurden (grün).}
   \label{fig:bitonic-08}
 \end{figure}
   rekursiven Schritt hinzugefügt wurden (grün).}
   \label{fig:bitonic-08}
 \end{figure}


@@ -523,15 +567,6 @@ $\frac{1}{4} n \log(n) \log(n+1) = \mathcal{O}\left(n (log (n))^2\right)$
 Komparatoren, die in $\frac{1}{2} \log(n) \log(n+1) = \mathcal{O}(\log(n))$
 Schichten angeordnet sind.
 
 Komparatoren, die in $\frac{1}{2} \log(n) \log(n+1) = \mathcal{O}(\log(n))$
 Schichten angeordnet sind.
 

-%\begin{figure}
-%\begin{center}
-%\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
-%\end{center}
-%\caption{Rekursiver Aufbau von $S(n)$: Es besteht aus zwei Instanzen von
-%$S(n/2)$ und dem Mischer $M(n)$.}
-%\label{fig:bms_rekursiver_aufbau}
-%\end{figure}
-

 \subsection{Das Odd-Even-Mergesort-Netzwerk}
 
 Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk}
 \subsection{Das Odd-Even-Mergesort-Netzwerk}
 
 Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk}


@@ -787,6 +822,7 @@ die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
 Komprimierung durchgeführt werden.
 
 \subsection{Normalisieren}
 Komprimierung durchgeführt werden.
 
 \subsection{Normalisieren}

+\label{sect:normalisieren}

 
 \begin{figure}
   \centering
 
 \begin{figure}
   \centering


@@ -859,18 +895,6 @@ Al-Haj Baddar} und \textit{Kenneth~E. Batcher} in ihrer Arbeit „An 11-Step
 Sorting Network for 18~Elements“~\cite{BB2009} vorstellen, benötigt aber
 6~Komparatoren weniger.
 
 Sorting Network for 18~Elements“~\cite{BB2009} vorstellen, benötigt aber
 6~Komparatoren weniger.
 

-% 9   9
-% 9  18
-% 9  27
-% 9  36
-% 9  45
-% 8  53
-% 8  61
-% 7  68
-% 7  75
-% 6  81
-% 5  86
-

 Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
 ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
 sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
 Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
 ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
 sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine


@@ -880,12 +904,6 @@ die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden
 Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
 nur mit exponentiellem Aufwand möglich ist.
 
 Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
 nur mit exponentiellem Aufwand möglich ist.
 

-%\begin{itemize}
-%\item Mit dem Bitonic-Merge
-%\item Mit dem Odd-Even-Merge
-%\item Nach dem Pairwise sorting-network Schema.
-%\end{itemize}
-

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


@@ -910,17 +928,20 @@ das {\em Odd-Even-Transpositionsort-Netzwerk}.
 
 \begin{figure}
   \centering
 
 \begin{figure}
   \centering

-  \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
-  \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
-  \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
-  \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
+  \subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad
+  durch das Sortiernetzwerk eindeutig festgelegt.]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
+  \subfigure[Komparatoren, die einen wechsel der Leitungen bewirken, werden
+  durch sich kreuzende Leitungen ersetzt.]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
+  \subfigure[Leitung~4 wurde entfernt. Übrig bleibt ein Sortiernetzwerk mit
+  7~Leitungen.]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
+  \subfigure[Die Leitungen wurden wieder gerade eingezeichnet und die
+  Komparatoren regelmäßig angeordnet. Blau eingezeichnet ist \oet{7}.]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}

   \caption{Eine Leitung wird aus dem
   \caption{Eine Leitung wird aus dem

-  \emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(8)$ entfernt:
-  Auf der rot markierten Leitung wird $\infty$ angelegt. Da der Wert bei jedem
-  Komparator am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die
-  restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
-  Pfad herausgetrennt werden. In der letzten Abbildung ist
-  $\operatorname{OET}(7)$ markiert.}
+  \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{8} entfernt: Auf der rot
+  markierten Leitung wird $-\infty$ angelegt. Da der Wert bei jedem Komparator
+  am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die restlichen
+  Werte trotzdem noch richtig sortiert werden müssen, kann dieser Pfad
+  herausgetrennt werden. In der letzten Abbildung ist \oet{7} markiert.}

   \label{fig:oe-transposition-cut}
 \end{figure}
 
   \label{fig:oe-transposition-cut}
 \end{figure}
 


@@ -943,19 +964,25 @@ auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage
 getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
 mit $(n-1)$~Elementen darstellen.
 
 getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
 mit $(n-1)$~Elementen darstellen.
 

-Wenn wir die Minimum- beziehungsweise Maximum-Leitung entfernen
-(Abbildung~\ref{fig:oe-transposition-cut2}), bleibt das Sortiernetzwerk für
-$(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung ein Minimum oder ein
-Maximum angenommen wird, bezeichnen wir das eliminieren einer Leitung als
-\emph{Minimum-Schnitt} beziehungsweise \emph{Maximum-Schnitt}.
+Wenn man die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in
+Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, bleibt das
+Sortiernetzwerk für $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung
+ein Minimum oder ein Maximum angenommen wird, bezeichnen wir das eliminieren
+einer Leitung als \emph{Minimum-Schnitt} beziehungsweise
+\emph{Maximum-Schnitt}.

 
 Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
 Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
 markierten Komparatoren wurden verschoben, so dass sich eine kompaktere
 Darstellung ergibt. Ausserdem ist das
 
 Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
 Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
 markierten Komparatoren wurden verschoben, so dass sich eine kompaktere
 Darstellung ergibt. Ausserdem ist das

-{\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der
-zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
-Ausgabe und kann entfernt werden.
+\emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der
+zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und
+kann entfernt werden.
+
+Durch das Ersetzen von Komparatoren durch gekreuzte Leitungen werden häufig
+\emph{Nicht-Standard-Sortiernetzwerke} erzeugt. Im Anschluss an einen
+\emph{Schnitt} empfiehlt es sich deshalb, das Sortiernetzwerk zu
+\emph{normalisieren}, wie in Abschnitt~\ref{sect:normalisieren} beschrieben.

 
 \subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
 \label{sect:anzahl_schnittmuster}
 
 \subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
 \label{sect:anzahl_schnittmuster}


@@ -963,8 +990,8 @@ Ausgabe und kann entfernt werden.
 Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
 Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
 $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und
 Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
 Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
 $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und

-Weise einen Sortiernetzwerke mit $2n$~Eingängen wieder auf Sortiernetzwerke
-mit $n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die
+Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit
+$n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die

 nacheinander angewendet ein $n$-Sortiernetzwerk auf ein
 ${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als
 \emph{$k$-Schnittmuster}.
 nacheinander angewendet ein $n$-Sortiernetzwerk auf ein
 ${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als
 \emph{$k$-Schnittmuster}.


@@ -1139,6 +1166,7 @@ die Anzahl der \emph{möglichen} Schnittmuster.
 
 \newpage
 \section{Der \textsc{SN-Evolution}-Algorithmus}
 
 \newpage
 \section{Der \textsc{SN-Evolution}-Algorithmus}

+\label{sect:sn-evolution}

 
 Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
 Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
 
 Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
 Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer


@@ -1216,7 +1244,7 @@ Auswahl := (leer)
 für jedes Individuum in Population
 {
   reziproke Güte := 1.0 / Guete(Individuum)
 für jedes Individuum in Population
 {
   reziproke Güte := 1.0 / Guete(Individuum)

-  Wahrscheinlichkeit P := reziproke Güte / (reziproke Güte + Gütesumme)
+  Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)

   Gütesumme := Gütesumme + reziproke Güte
 
   mit Wahrscheinlichkeit P
   Gütesumme := Gütesumme + reziproke Güte
 
   mit Wahrscheinlichkeit P


@@ -1326,12 +1354,7 @@ Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Ein Netzwerk, das
 $\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch
 nicht beobachtet werden.
 
 $\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch
 nicht beobachtet werden.
 

-\begin{itemize}
-\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der Schichten, kombiniert)
-\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \emph{Mischer} ab.
-\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
-\item Möglicherweise: Verwende den rekursiven Aufbau des \emph{Pairwise-Sorting}-Netzwerks um Sortiernetzwerke zu mergen.
-\end{itemize}
+\todo{Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.}

 
 %\begin{figure}
 %\begin{center}
 
 %\begin{figure}
 %\begin{center}


@@ -1379,11 +1402,11 @@ von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
 Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
 gute Schnittmuster gesucht.
 
 Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
 gute Schnittmuster gesucht.
 

-Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster},
-die in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als
-Individuen. Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte
-des einen Schnittmusters verwendet und die letzten ${c-r}$~Schnitte des
-zweiten Schmittmusters. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.
+Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
+in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
+Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte des einen
+Schnittmusters verwendet und die letzten ${c-r}$~Schnitte des zweiten
+Schmittmusters. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.

 
 Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
 auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
 
 Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
 auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die


@@ -1586,7 +1609,7 @@ wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit
 $\operatorname{OES}(32)$ sehr schnell ein gutes 16-Schnittmuster findet.
 
 Eines der eher zufälligen Schnittmuster ist $\operatorname{MIN}(1, 6, 11, 14,
 $\operatorname{OES}(32)$ sehr schnell ein gutes 16-Schnittmuster findet.
 
 Eines der eher zufälligen Schnittmuster ist $\operatorname{MIN}(1, 6, 11, 14,

-17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, 8, 13, 18, 21, 27, 31)$. Das
+17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, 8,$ $13, 18, 21, 27, 31)$. Das

 Schnittmuster ist in Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht,
 das resultierende Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
 
 Schnittmuster ist in Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht,
 das resultierende Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
 


@@ -1638,9 +1661,9 @@ selbst erzeugen kann.
 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
 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.
+Nachfolger zwar noch unter 20.000, bei den untersuchten
+32-Sortier\-netz\-werken 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
 
 Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen
 zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem


@@ -1661,6 +1684,27 @@ für n Iterationen
 gib Netzwerk zurück
 \end{verbatim}
 
 gib Netzwerk zurück
 \end{verbatim}
 

+Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der
+Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem
+zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der
+\textsc{SN-Markov}-Algorithmus auf einem entsprechenden
+\emph{Odd-Even-Transporitionsort}-Netzwerk gestartet hat mindestens
+1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der
+Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler
+erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende
+prezenturale Verteilung zu sehen.
+
+Ebenfalls in die Graphen in Abbildung~\ref{fig:markov-comparators}
+eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen
+Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der
+um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde.
+Beispielsweise war die kleinste erreichte Komparatorzahl bei
+16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$
+gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$
+und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem
+Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$
+unter den Graphen angegeben.
+

 \begin{figure}
   \begin{center}
   \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
 \begin{figure}
   \begin{center}
   \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}


@@ -1673,7 +1717,7 @@ gib Netzwerk zurück
   \label{fig:markov-cycles-16}
 \end{figure}
 
   \label{fig:markov-cycles-16}
 \end{figure}
 

-
+\todo{Schreibe noch etwas zu …}

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


@@ -1682,60 +1726,114 @@ gib Netzwerk zurück
 \end{itemize}
 
 \begin{figure}
 \end{itemize}
 
 \begin{figure}

-  \begin{center}
-  \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
-  \emph{Gamma-Verteilung} $f(x - 40)$ mit $k = 8,267$ und $\theta = 0,962$.}
-  \label{fig:markov-comparators-12}
-\end{figure}
-
-\begin{figure}
-  \begin{center}
-  \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
-  \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.}
-  \label{fig:markov-comparators-14}
-\end{figure}
-
-\begin{figure}
-  \begin{center}
-  \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
-  \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.}
-  \label{fig:markov-comparators-16}
+  \centering
+  \subfigure[12 Leitungen, $k = 8,267$, $\theta = 0,962$, $\delta = 40$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-12-pct.pdf}}
+  \subfigure[14 Leitungen, $k = 9,522$, $\theta = 0,867$, $\delta = 52$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-14-pct.pdf}}
+  \subfigure[16 Leitungen, $k = 17,939$, $\theta = 1,091$, $\delta = 62$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-16-pct.pdf}}
+  \subfigure[18 Leitungen, $k = 10,724$, $\theta = 0,766$, $\delta = 81$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-18-pct.pdf}}
+  \caption{Anzahl der Komparatoren von Sortiernetzwerken,
+  die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet
+  ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der
+  gemessenen Daten darstellt.}
+  \label{fig:markov-comparators}

 \end{figure}
 
 \begin{figure}
   \begin{center}
 \end{figure}
 
 \begin{figure}
   \begin{center}

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

   \end{center}
   \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}
+  \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von
+  \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem
+  \emph{Odd-Even-Mischer} und dem \emph{bitonen Mischer}) gesaßen.}
+  \label{fig:comparison-comparators}

 \end{figure}
 
 \end{figure}
 

-\newpage
-\section{Empirische Beobachtungen}
-
-\begin{itemize}
-\item So schnell konvergiert der Algorithmus.
-\item $\ldots$
-\end{itemize}
+%\begin{figure}
+%  \begin{center}
+%  \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
+%  \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.}
+%  \label{fig:markov-comparators-14}
+%\end{figure}
+%
+%\begin{figure}
+%  \begin{center}
+%  \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
+%  \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.}
+%  \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{Ausblick}
 
 
 \newpage
 \section{Ausblick}
 

-Das würde mir noch einfallen$\ldots$
-
-- SN-Evolution mit Pairwise als „Mischer“.
-- Co-Evolution von Netzwerken und Schnittmustern.
+Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von
+Sortiernetzwerken bieten, sind durch die in dieser Arbeit vorgestellten
+Herangehensweisen bei weitem nicht erschöpft.
+
+Im Folgenden werden Ansätze umrissen, mit denen an die Untersuchungen in
+dieser Arbeit nahtlos angeknöpft werden könnte.
+
+\subsection{Verwendung des Pairwise-Sorting-Netzwerk in \textsc{SN-Evolution}}
+
+Die aktuelle Implementierung von \textsc{SN-Evolution}
+(Abschnitt~\ref{sect:sn-evolution}) kann sowohl den \emph{bitonen Mischer} als
+auch den \emph{Odd-Even-Mischer} verwenden, um zwei Individuen zu
+rekombinieren. Das \emph{Pairwise-Sorting}-Netzwerk verwendet zwar keinen
+Mischer, es ist aber ebenfalls rekursiv über kleinere Versionen von sich
+selbst definiert. Das heißt, dass \ps{n} aus zwei Instanzen von
+$\ps{\frac{n}{2}}$ und zusätzlichen Komparatoren besteht, die die Eingabe für
+die kleineren Sortiernetzwerke vorbereiten und anschließend für eine sortierte
+Ausgaben sorgen. Anstelle von $\ps{\frac{n}{2}}$ kann man natürlich beliebige
+Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwenden.
+
+Dies ließe sich für \textsc{SN-Evolution} nutzen, um zwei Individuen zu
+rekombinieren. Da es für das \emph{Pairwise-Sorting}-Netzwerk sehr viele
+\emph{unterscheidliche} Schnittmuster gibt
+(Abbschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die
+Verwendung dieser Rekombinationsmethode neue Ergebnisse ermöglicht. Leider
+wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine
+$n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren
+$n$-Sortiernetzwerken als \ps{n} führen.
+
+\subsection{Kooperation von \textsc{SN-Evolution} und
+\textsc{SN-Evolution-Cut}}
+
+Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis}
+in~\cite{H1992} beschreibt, könnte man die Algorithmen \textsc{SN-Evolution}
+und \textsc{SN-Evolution-Cut} versuchen zu kombinieren. Nach dem Zusammenfügen
+von zwei $n$-Sortiernetzwerken könnte der Algorithmus
+\textsc{SN-Evolution-Cut} beispielsweise einen möglichst guten Schnitt für
+\emph{dieses} Netzwerk ermitteln. Da sich die Lösungen, die Evolutionäre
+Algorithmen in ihre Population aufnehmen, in den ersten Schritten rasch
+verbessern, könnten selbst weniger Iterationen von \textsc{SN-Evolution-Cut}
+die Zwischenlösungen von \textsc{SN-Evolution} deutlich verbessern.
+
+Alternativ könnte man -- analog zur Herangehensweise von \textit{Hillis} --
+eine zweite Population von Schnittmustern evolvieren, die für die
+Sortiernetzwerke in der Population von \textsc{SN-Evolution} besonders gut
+funktionieren. In jeder Iteration wendet man alle oder eine zufällige Menge
+Schnittmuster auf das zusammengeführte Netzwerk an und gibt dem besten
+Ergebnis den Zuschlag. Anschließend erfährt das entsprechende Schnittmuster
+eine Aufwertung, so dass es wahrscheinlicher wird, dass \emph{dieses}
+Schnittmuster zur nächten Generation beiträgt. Im Gegensatz zum Ansatz der
+parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die
+das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern
+könnte.

 
 \newpage
 \section{Implementierung}
 
 \newpage
 \section{Implementierung}