Diverses.

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index b5d8a09..c4ac165 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -578,17 +578,17 @@ vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von
 beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht
 darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist.
 
 beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht
 darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist.
 

-\subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer}
+\subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer}

 
 

-Der \emph{Odd-Even-Mischer} $\operatorname{OEM}(n,m)$ ist ein
+Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein

 Komperatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$
 Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
 zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
 \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}
 Komperatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$
 Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
 zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
 \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}

-vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even-Mischer} unter
+vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even}-Mischer unter

 Umständen mehr Schichten als der \emph{bitone Mischer}.~\cite{KNUTH}
 
 Umständen mehr Schichten als der \emph{bitone Mischer}.~\cite{KNUTH}
 

-Der \emph{Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
+Der \emph{Odd-Even}-Mischer selbst ist ebenfalls rekursiv aufgebaut: Die

 Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
 sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
 Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
 sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei


@@ -622,7 +622,7 @@ geraden Indizes und je eine Liste der ungeraden Indizes.
 
 Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die
 ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden
 
 Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die
 ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden

-rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am
+rekursiv von kleineren \emph{Odd-Even}-Mischern zusammengefügt, so dass sich am

 Ausgang der Mischer die Folgen
 \begin{eqnarray}
   W_{\textrm{gerade}}   &=& \left(w_0, w_2, w_4, \ldots\right) \\
 Ausgang der Mischer die Folgen
 \begin{eqnarray}
   W_{\textrm{gerade}}   &=& \left(w_0, w_2, w_4, \ldots\right) \\


@@ -635,8 +635,8 @@ hinzugefügt,
 \begin{equation}
   w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
 \end{equation}
 \begin{equation}
   w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
 \end{equation}

-die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em
-Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}.
+die die Folge~$W$ sortieren. Den schematischen Aufbau des
+\emph{Odd-Even}-Mischers zeigt Abbildung~\ref{fig:oe-merge}.

 
 Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
 Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
 
 Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
 Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --


@@ -686,7 +686,7 @@ in Abbildung~\ref{fig:oe-post-recursive} dargestellt.
   \qquad
   \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
   \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
   \qquad
   \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
   \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der

-  kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der
+  kleineren \emph{Odd-Even}-Mischer entstehen können. Ist die Differenz der

   Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
   letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
   sortiert ist.}
   Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
   letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
   sortiert ist.}


@@ -737,7 +737,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
 
 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
+sich selbst und einem abschließenden \emph{Odd-Even}-Mischer. Die

 effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl
 entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
 $\operatorname{OES}(n)$ aus
 effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl
 entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
 $\operatorname{OES}(n)$ aus


@@ -754,7 +754,7 @@ Komparatornetzwerke definiert sind.
   \end{center}
   \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
   sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden
   \end{center}
   \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
   sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden

-  \emph{Odd-Even-Mischer} $\operatorname{OEM}(4)$ für gerade und ungerade
+  \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade

   Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
   Komparatoren zwischen benachbarten Leitungen (grün).}
   \label{fig:odd-even-mergesort-08}
   Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
   Komparatoren zwischen benachbarten Leitungen (grün).}
   \label{fig:odd-even-mergesort-08}


@@ -763,7 +763,7 @@ Komparatornetzwerke definiert sind.
 In Abbildung~\ref{fig:odd-even-mergesort-08} ist das konkrete Sortiernetzwerk
 $\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven
 Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den
 In Abbildung~\ref{fig:odd-even-mergesort-08} ist das konkrete Sortiernetzwerk
 $\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven
 Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den

-\emph{Odd-Even-Mischer} für acht Leitungen dar: Die beiden blauen Blöcke sind
+\emph{Odd-Even}-Mischer für acht Leitungen dar: Die beiden blauen Blöcke sind

 die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
 die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
 
 die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
 die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
 


@@ -887,7 +887,7 @@ $\operatorname{OES}(9)$ benötigt beispielsweise 26~Komparatoren, die in in
 neun Schichten angeordnet sind. Es sind allerdings Sortiernetzwerke mit neun
 Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten
 benötigen. Kombiniert man zwei dieser Netzwerke mit dem
 neun Schichten angeordnet sind. Es sind allerdings Sortiernetzwerke mit neun
 Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten
 benötigen. Kombiniert man zwei dieser Netzwerke mit dem

-\emph{Odd-Even-Mischer} erhält man ein Sortiernetzwerk mit 18~Eingängen, das
+\emph{Odd-Even}-Mischer erhält man ein Sortiernetzwerk mit 18~Eingängen, das

 80~Komparatoren in 11~Schichten benötigt -- $\operatorname{OES}(18)$ benötigt
 82~Komparatoren in 13~Schichten. Damit ist das resultierende Netzwerk so
 schnell wie das Sortiernetzwerk mit 18~Eingängen, das \textit{Sherenaz~W.
 80~Komparatoren in 11~Schichten benötigt -- $\operatorname{OES}(18)$ benötigt
 82~Komparatoren in 13~Schichten. Damit ist das resultierende Netzwerk so
 schnell wie das Sortiernetzwerk mit 18~Eingängen, das \textit{Sherenaz~W.


@@ -1016,12 +1016,13 @@ führen beide Reihenfolgen zum selben Ergebnis.
 
 \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es
 möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
 
 \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
-Anzahl der möglichen Schnittmuster setzt sich zusammen aus der Anzahl von
-Möglichkeiten, $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen
-Minimum-~/ Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl
-der möglichen Schnittmuster:
+vorzubelegen, ohne die Menge der erreichbaren Sortiernetzwerke einzuschränken.
+Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, die Menge der
+so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die Anzahl der
+möglichen Schnittmuster setzt sich zusammen aus der Anzahl von Möglichkeiten,
+$k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen Minimum-~/
+Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl der möglichen
+Schnittmuster:

 \begin{displaymath}
   2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
   = 2^{k} \cdot \frac{n!}{k! (n-k)!}
 \begin{displaymath}
   2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
   = 2^{k} \cdot \frac{n!}{k! (n-k)!}


@@ -1061,8 +1062,8 @@ sich die Resultate auch in der ersten Schicht nicht unterscheiden.
   8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
   $\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der
   unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das
   8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
   $\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der
   unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das

-  \emph{Odd-Even-Mergesort-Netzwerk}, 4973 für das \emph{bitone
-  Mergesort-Netzwerk} und 18764 für das \emph{Pairwise-Sorting-Netzwerk}.}
+  \emph{Odd-Even-Mergesort}-Netzwerk, 4973 für das \emph{bitone
+  Mergesort}-Netzwerk und 18764 für das \emph{Pairwise-Sorting}-Netzwerk.}

   \label{fig:count-cuts-16}
 \end{figure}
 
   \label{fig:count-cuts-16}
 \end{figure}
 


@@ -1088,9 +1089,9 @@ Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der
 Formel~\eqref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen
 Schnittmuster führen aber nur zu wenigen \emph{unterschiedlichen}
 Sortiernetzwerken: 3519 ($\approx 0,1\%$) im Fall des
 Formel~\eqref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen
 Schnittmuster führen aber nur zu wenigen \emph{unterschiedlichen}
 Sortiernetzwerken: 3519 ($\approx 0,1\%$) im Fall des

-\emph{Odd-Even-Mergesort-Netzwerks}, 4973 ($\approx 0,15\%$) beim
-\emph{bitonen Mergesort-Netzwerk} und 18764 ($\approx 0,57\%$) beim
-\emph{Pairwise-Sorting-Netzwerk}. Zwar ist es möglich, dass mehr Iterationen
+\emph{Odd-Even-Mergesort}-Netzwerks, 4973 ($\approx 0,15\%$) beim
+\emph{bitonen Mergesort}-Netzwerk und 18764 ($\approx 0,57\%$) beim
+\emph{Pairwise-Sorting}-Netzwerk. Zwar ist es möglich, dass mehr Iterationen

 die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. Die Graphen
 in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der Annahme, dass
 die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
 die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. Die Graphen
 in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der Annahme, dass
 die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster


@@ -1104,7 +1105,8 @@ für „kleine“ x-Werte verlässt.
 
 Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
 können, kann man sich einer stochastischen Methode bedienen, der sogenannten
 
 Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
 können, kann man sich einer stochastischen Methode bedienen, der sogenannten

-\emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von
+\emph{Monte-Carlo-Methode}, die \textit{Rolf Wanka} in~\cite{W2006} für
+schwierige Zählprobleme vorstellt. Zunächst generiert man eine Menge~$S$ von

 $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
 zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter
 der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$
 $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
 zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter
 der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$


@@ -1238,21 +1240,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}

-Gütesumme := 0
-Auswahl := (leer)
-
-für jedes Individuum in Population
-{
-  reziproke Güte := 1.0 / Guete(Individuum)
-  Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
-  Gütesumme := Gütesumme + reziproke Güte
-
-  mit Wahrscheinlichkeit P
+  Gütesumme := 0
+  Auswahl := (leer)
+  
+  für jedes Individuum in Population

   {
   {

-    Auswahl := Individuum
+    reziproke Güte := 1.0 / Guete(Individuum)
+    Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
+    Gütesumme := Gütesumme + reziproke Güte
+  
+    mit Wahrscheinlichkeit P
+    {
+      Auswahl := Individuum
+    }

   }
   }

-}
-gib Auswahl zurück
+  gib Auswahl zurück

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


@@ -1260,13 +1262,15 @@ gib Auswahl zurück
 Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
 einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
 den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
 Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
 einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
 den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den

-{\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
+\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), um die

 beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
 beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.

-Anschließend entfernen wir zufällig $n$~Leitungen wie in
-Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
+Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.

 
 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
 
 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft

-erhält.
+erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
+Komparatornetzwerk die Sortiereigenschaft besitzt. Der Nachteil ist, dass
+nicht alle Sortiernetzwerke auf diese Art und Weise erzeugt werden können.

 
 \subsection{Mutation}
 
 
 \subsection{Mutation}
 


@@ -1330,7 +1334,7 @@ als das bitone Mergesort-Netzwerk: $\operatorname{BS}(16)$ benötigt
 80~Komparatoren, das Sortiernetzwerk in
 Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67.
 
 80~Komparatoren, das Sortiernetzwerk in
 Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67.
 

-\subsection{Versuche mit dem Odd-Even-Mischer}
+\subsection{Versuche mit dem \emph{Odd-Even}-Mischer}

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


@@ -1338,7 +1342,7 @@ Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67.
   \end{center}
   \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
     10~Schichten. Das Netzwerk wurde von dem Algorithmus
   \end{center}
   \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
     10~Schichten. Das Netzwerk wurde von dem Algorithmus

-    \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even-Mischers}
+    \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers

     erzeugt.}
   \label{fig:16-e1-oddeven-1296543330}
 \end{figure}
     erzeugt.}
   \label{fig:16-e1-oddeven-1296543330}
 \end{figure}


@@ -1346,9 +1350,9 @@ Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67.
 Leider lies sich das Ergebnis des bitonen Mischers -- das von
 \textsc{SN-Evolution} ausgegebene Netzwerk war effizienter als das rekursiv
 aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem
 Leider lies sich das Ergebnis des bitonen Mischers -- das von
 \textsc{SN-Evolution} ausgegebene Netzwerk war effizienter als das rekursiv
 aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem

-\emph{Odd-Even-Mischer} nicht wiederholen. Zwar erreichen die
+\emph{Odd-Even}-Mischer nicht wiederholen. Zwar erreichen die

 Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
 Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des

-\emph{Odd-Even-Mischers} findet, das \emph{Odd-Even-Mergesort}-Netzwerk
+\emph{Odd-Even}-Mischers findet, das \emph{Odd-Even-Mergesort}-Netzwerk

 bezüglich Schnelligkeit und Effizienz, ein Beispiel hierfür ist in
 Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Ein Netzwerk, das
 $\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch
 bezüglich Schnelligkeit und Effizienz, ein Beispiel hierfür ist in
 Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Ein Netzwerk, das
 $\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch


@@ -1484,7 +1488,7 @@ Netzwerks scheinen rein zufällig zu sein.
   \label{fig:32-ec-from-bs64}
 \end{figure}
 
   \label{fig:32-ec-from-bs64}
 \end{figure}
 

-Das Ergebnis von \textit{Mühlenthaler} von \textit{Wanka}, die den bitonen
+Das Ergebnis von \textit{Mühlenthaler} und \textit{Wanka}, die den bitonen

 Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk
 konstruiert haben, kann demnach auch erreicht werden, wenn
 $\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen
 Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk
 konstruiert haben, kann demnach auch erreicht werden, wenn
 $\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen


@@ -1541,7 +1545,7 @@ Anzahl an Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und
 $\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
 Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
 
 $\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
 Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
 

-Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht
+Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht

 einsetzt und auch nicht auf einem Mischer basiert, ist der
 $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
 Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
 einsetzt und auch nicht auf einem Mischer basiert, ist der
 $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
 Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In


@@ -1673,15 +1677,15 @@ selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt dich de
 Algorithmus wie folgt beschreiben:
 
 \begin{verbatim}
 Algorithmus wie folgt beschreiben:
 
 \begin{verbatim}

-Netzwerk := Eingabe
-
-für n Iterationen
-{
-  Nachfolger := kombiniere (Netzwerk, Netzwerk)
-  Netzwerk   := Nachfolger
-}
-
-gib Netzwerk zurück
+  Netzwerk := Eingabe
+  
+  für n Iterationen
+  {
+    Nachfolger := kombiniere (Netzwerk, Netzwerk)
+    Netzwerk   := Nachfolger
+  }
+  
+  gib Netzwerk zurück

 \end{verbatim}
 
 Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der
 \end{verbatim}
 
 Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der


@@ -1706,26 +1710,6 @@ Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$
 unter den Graphen angegeben.
 
 \begin{figure}
 unter den Graphen angegeben.
 
 \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}
-
-\todo{Schreibe noch etwas zu …}
-\begin{itemize}
-  \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
-  \item Anzahl der erreichbaren Sortiernetzwerke.
-  \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen
-    Netzwerke. (Abbildung~\ref{fig:markov-comparators-16})
-\end{itemize}
-
-\begin{figure}

   \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}}
   \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}}


@@ -1744,10 +1728,43 @@ unter den Graphen angegeben.
   \end{center}
   \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von
   \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem
   \end{center}
   \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.}
+  \emph{Odd-Even}-Mischer und dem \emph{bitonen Mischer}) besaßen.}

   \label{fig:comparison-comparators}
 \end{figure}
 
   \label{fig:comparison-comparators}
 \end{figure}
 

+Dass der \textsc{SN-Markov}-Algorithmus nicht schlechter ist als der
+\textsc{SN-Evolution}-Algo\-rithmus, ist aus dem Graphen in
+Abbildung~\ref{fig:comparison-comparators} ersichtlich. Analog zu dem Versuch
+mit \textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die
+Anzahl der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als
+Startnetzwerk diente bei beiden Algorithmen das
+\emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der
+x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der
+ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt
+wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden außerdem nach
+dem verwendeten Mischer-Netzwerk -- \oem{32} beziehungsweise \bm{32}.
+
+Sowohl der \textsc{SN-Markov}-Algorithmus, der das
+\emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit
+\oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die
+bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind.
+Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger:
+Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit
+63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335
+\%$ rund 20~mal höher.
+
+Erwartunggemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem
+\emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist
+jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die
+mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort} -- \oet{16}
+ist aus 120~Komparatoren aufgebaut, bei dem Lauf, der die Daten für
+Abbildung~\ref{fig:comparison-comparators} lieferte, traten auch jeweils ein
+Sortiernetzwerk mit 121 und 124~Komparatoren auf. Da Sortiernetzwerke mit so
+vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen
+Iterationen nicht noch einmal erzeugt wurden, handelt es sich vermutlich um
+ein Phänomen, das mit der Initialisierung mit dem
+\emph{Odd-Even-Transpositionsort}-Netzwerk zusammenhängt.
+

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


@@ -1778,8 +1795,40 @@ unter den Graphen angegeben.
 %  \label{fig:markov-comparators-18}
 %\end{figure}
 
 %  \label{fig:markov-comparators-18}
 %\end{figure}
 

+%\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}
+
+
+\todo{Schreibe noch etwas zu …}
+\begin{itemize}
+  \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
+  \item Anzahl der erreichbaren Sortiernetzwerke.
+  \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen
+    Netzwerke. (Abbildung~\ref{fig:markov-comparators-16})
+  \item \textsc{SN-Count-Markov} (ggf)
+\end{itemize}
+

 \newpage
 \newpage

-\section{Ausblick}
+\section{Fazit und Ausblick}
+
+\todo{Ausformulieren}
+\begin{itemize}
+\item Mit \textsc{SN-Evolution} und \oem{n} kann man nicht besser werden als
+  \oes{n}.
+\item Mit \textsc{SN-Evolution} und \bm{n} kann man besser werden als \bs{n}.
+\item Vermutlich kann man mit \textsc{SN-Evolution} und \bm{n} so gut werden
+wie \textsc{SN-Evolution-Cut}, wenn er mit \bs{2n} gestartet wird.
+\item Leider sind keine konstruktiven Methoden erkannt worden.
+\end{itemize}

 
 Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von
 Sortiernetzwerken bieten, sind durch die in dieser Arbeit vorgestellten
 
 Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von
 Sortiernetzwerken bieten, sind durch die in dieser Arbeit vorgestellten


@@ -1788,11 +1837,11 @@ 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.
 
 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}}
+\subsection{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \textsc{SN-Evolution}}

 
 Die aktuelle Implementierung von \textsc{SN-Evolution}
 (Abschnitt~\ref{sect:sn-evolution}) kann sowohl den \emph{bitonen Mischer} als
 
 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
+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
 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


@@ -1810,8 +1859,7 @@ 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.
 
 $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}}
+\subsection{Ausblick: 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}
 
 Ä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}


@@ -1863,7 +1911,7 @@ Beispielsweise eine \emph{normalisierte} Variante des \emph{bitonen
 Mergesort}-Netzwerks \bs{18} zu erzeugen, kann folgendes Kommando verwendet
 werden:
 \begin{verbatim}
 Mergesort}-Netzwerks \bs{18} zu erzeugen, kann folgendes Kommando verwendet
 werden:
 \begin{verbatim}

-$ sn-bitonicsort 18 | sn-normalize >sn-18
+  $ sn-bitonicsort 18 | sn-normalize >sn-18

 \end{verbatim}
 Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und
 es einfach zu ermöglichen, Programme zu verketten, ist eines der
 \end{verbatim}
 Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und
 es einfach zu ermöglichen, Programme zu verketten, ist eines der

diff --git a/references.bib b/references.bib
index 7bb306a..95d4959 100644 (file)
--- a/references.bib
+++ b/references.bib
@@ -86,3 +86,13 @@
        Publisher = {Addison-Wesley},
        Year = 1992
 }
        Publisher = {Addison-Wesley},
        Year = 1992
 }

+
+@inbook{W2006,
+       Author = {Rolf Wanka},
+       Title = {Approximationsalgorithmen},
+       Chapter = {8 Approximate Counting und die Monte-Carlo-Methode},
+       Pages = {151--186},
+       Year = 2006,
+       Publisher = {Teubner Verlag},
+       Address = {Wiesbaden}
+}