Verwende Theta statt gross-O.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 6cd4078..24ae125 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -9,6 +9,7 @@
 \usepackage{listings}
 \usepackage{graphicx}
 \usepackage{url}
 \usepackage{listings}
 \usepackage{graphicx}
 \usepackage{url}

+\usepackage[table]{xcolor}

 %\usepackage{longtable}
 \usepackage{subfigure}
 \usepackage{icomma}
 %\usepackage{longtable}
 \usepackage{subfigure}
 \usepackage{icomma}


@@ -43,6 +44,9 @@
 \newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}}
 \newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}}
 
 \newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}}
 \newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}}
 

+\newcommand{\gcell}{\cellcolor{green!10}}
+\newcommand{\Gcell}{\cellcolor{green!10!white!95!black}}
+

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


@@ -266,8 +270,8 @@ 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

-$\mathcal{O}\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
-ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\mathcal{O}(2^n)$
+$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
+ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(2^n)$

 verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
 schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
 ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,
 verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
 schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
 ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,


@@ -454,7 +458,7 @@ $\operatorname{OET}(3)$ sortiert.
 Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die
 Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen
 sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n
 Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die
 Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen
 sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n

-(n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind.
+(n-1)} = \Theta(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind.

 Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren,
 ($\Theta(n \log (n)^2)$), die in weniger Schichten,
 ($\Theta(\log (n)^2)$), angeordnet sind.
 Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren,
 ($\Theta(n \log (n)^2)$), die in weniger Schichten,
 ($\Theta(\log (n)^2)$), angeordnet sind.


@@ -570,7 +574,7 @@ Statt an eine Treppe erinnert das Muster nun an einen Trichter.
 Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
 die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
 $\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus
 Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
 die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
 $\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus

-$\frac{1}{2} n \log(n) = \mathcal{O}\left(n \log(n)\right)$~Komparatoren
+$\frac{1}{2} n \log(n) = \Theta\left(n \log(n)\right)$~Komparatoren

 besteht, die in $\log(n)$~Schichten angeordnet werden können.
 
 \subsubsection{Das bitone Mergesort-Netzwerk}
 besteht, die in $\log(n)$~Schichten angeordnet werden können.
 
 \subsubsection{Das bitone Mergesort-Netzwerk}


@@ -742,7 +746,7 @@ in Abbildung~\ref{fig:oe-post-recursive} dargestellt.
 \end{figure}
 
 Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,
 \end{figure}
 
 Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,

-bricht die Rekursion nach $\mathcal{O}\left(\log (n) + \log (m)\right)$
+bricht die Rekursion nach $\Theta\left(\log (n) + \log (m)\right)$

 Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
 Schichten im Mischer-Netzwerk), hängt von der längeren der beiden
 Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.
 Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
 Schichten im Mischer-Netzwerk), hängt von der längeren der beiden
 Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.


@@ -760,7 +764,7 @@ Länge der Eingabefolgen, $n$ und $m$ ab:
 \end{displaymath}
 Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
 anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
 \end{displaymath}
 Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
 anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,

-dass $K(n,m)$ in $\mathcal{O}(N \log (N))$ enthalten ist.
+dass $K(n,m)$ in $\Theta(N \log (N))$ enthalten ist.

 
 Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die
 Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
 
 Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die
 Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der


@@ -1158,10 +1162,10 @@ die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
 vernachlässigbar klein ist.
 
 Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
 vernachlässigbar klein ist.
 
 Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses

-Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar.
-Die Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen
-Rechnern vorhanden ist, bevor ein entsprechender Graph den linearen Bereich
-für „kleine“ x-Werte verlässt.
+Experiment für größere Sortiernetzwerke nicht sinnvoll durchführbar. Die
+Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen Rechnern
+vorhanden ist, bevor ein entsprechender Graph den linearen Bereich 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


@@ -1248,10 +1252,20 @@ die bei Sortiernetzwerken verfolgt werden können:
   \item Möglichst wenige Schichten („schnell“)
 \end{itemize}
 
   \item Möglichst wenige Schichten („schnell“)
 \end{itemize}
 

-Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
-effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus
-60~Komparatoren in 10~Schichten. Das schnellste bekannte 16-Sortiernetzwerk
-besteht aus 61~Komparatoren in nur 9~Schichten.
+\begin{figure}
+  \centering
+  \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
+  \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
+  \caption{Das effizienteste und das schnellste Sortiernetzwerk für
+  16~Leitungen, das derzeit bekannt ist.}
+  \label{fig:16-best-known}
+\end{figure}
+Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken.
+Beispielsweise besteht das \emph{effizienteste} bekannte Sortiernetzwerk für
+16~Eingänge aus 60~Komparatoren in 10~Schichten. Es ist in
+Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte
+16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in
+Abbildung~\ref{fig:16-voorhis} zu sehen.

 
 Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
 berücksichtigen kann, hat die folgende allgemeine Form:
 
 Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
 berücksichtigen kann, hat die folgende allgemeine Form:


@@ -1283,8 +1297,8 @@ Exploitation}, das Finden (lokaler) Optima, bevorzugt.
 
 Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
 der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
 
 Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
 der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute

-Lösungen findet oder sich in \emph{lokalen} Optima verrennt. Leider gibt es
-kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
+Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt
+es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene

 Leitungszahlen und Mischer-Typen experimentiert werden muss.
 
 Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
 Leitungszahlen und Mischer-Typen experimentiert werden muss.
 
 Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden


@@ -1330,12 +1344,12 @@ Pseudocode wie folgt beschreiben:
 \label{sect:sn-evolution:rekombination}
 
 Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
 \label{sect:sn-evolution:rekombination}
 
 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
-\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
-beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
-Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in
-Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
+einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu
+einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em
+bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der
+\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}),
+Anschließend werden $n$~Leitungen mit einem zufälligen $n$-Schnittmuster wie
+in Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.

 
 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
 erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
 
 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
 erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das


@@ -1380,15 +1394,63 @@ wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet.
   \label{fig:16-e1-bitonic-1296542566}
 \end{figure}
 
   \label{fig:16-e1-bitonic-1296542566}
 \end{figure}
 

-Verwendet man den \emph{bitonen Mischer} in der Rekombinationsphase von
-\textsc{SN-Evolution}, so erhält man Netzwerke wie das in
-Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte: Der Algorithmus
-wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als triviale
-Initiallösung gestartet. Das Ergebnis ist ein Netzwerk, das effizienter ist
-als das \emph{bitone Mergesort}-Netzwerk: \bs{16} benötigt 80~Komparatoren,
-das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt
-lediglich~67. Die Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks wurde
-leider mit keiner Leitungszahl erreicht.
+Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk
+als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen
+Mischer} verwendet, gibt der Algorithmus Sortiernetzwerke wie das in
+Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte zurück.
+
+Viele der Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser
+Konfiguration gefunden werden, sind effizienter als das \emph{bitone
+Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen
+Merge}-Netzwerk \bm{n} beruht. Das in
+Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk
+benötigt 67~Komparatoren, 13~Komparatoren weniger als \bs{n}.
+
+Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke
+bevorzugt, können Netzwerke zurückgegeben werden, die schneller als \bs{n}
+sind. Viele der schnellen Sortiernetzwerke sind außerdem effizienter als
+\bs{n}. Das Sortiernetzwerk mit $n = 23$ Leitungen benötigt mit
+134~Komparatoren jedoch einen Komparator mehr als \bs{23}. Die Daten von
+schnellen Sortiernetzwerken, die \textsc{SN-Evolution} mit dem \emph{bitonen
+Merge}-Netzwerk erzeugt hat, sind in Tabelle~\ref{tbl:sn-ev-bm-fast}
+aufgelistet.
+
+\begin{table}\label{tbl:sn-ev-bm-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l|}{\bs{n}} \\
+\cline{2-5}
+    ($n$) & Komp. & Schichten & Komp. & Schichten \\
+\hline
+        8 & \gcell  20 &         6 &         24 &         6 \\
+        9 & \Gcell  26 &         8 &         28 &         8 \\
+       10 & \gcell  31 & \gcell  8 &         33 &         9 \\
+       11 & \Gcell  37 & \Gcell  9 &         39 &        10 \\
+       12 & \gcell  42 & \gcell  9 &         46 &        10 \\
+       13 & \Gcell  48 &        10 &         53 &        10 \\
+       14 & \gcell  54 &        10 &         61 &        10 \\
+       15 & \Gcell  61 &        10 &         70 &        10 \\
+       16 & \gcell  67 &        10 &         80 &        10 \\
+       17 & \Gcell  76 &        12 &         85 &        12 \\
+       18 & \gcell  87 & \gcell 12 &         91 &        13 \\
+       19 & \Gcell  93 & \Gcell 13 &         98 &        14 \\
+       20 & \gcell 104 & \gcell 13 &        106 &        14 \\
+       21 & \Gcell 109 & \Gcell 14 &        114 &        15 \\
+       22 & \gcell 118 & \gcell 14 &        123 &        15 \\
+       23 &        134 & \Gcell 14 & \Gcell 133 &        15 \\
+       24 & \gcell 133 &        15 &        144 &        15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+  unter Verwendung des \emph{bitonen Merge}-Netzwerks \bm{n}. Der Algorithmus
+  wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet
+  und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die
+  Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
+  $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}

 
 \subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
 
 
 \subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
 


@@ -1403,17 +1465,25 @@ leider mit keiner Leitungszahl erreicht.
   \label{fig:16-e1-oddeven-1296543330}
 \end{figure}
 
   \label{fig:16-e1-oddeven-1296543330}
 \end{figure}
 

-Leider lies sich das Ergebnis des bitonen Mischers -- die von
-\textsc{SN-Evolution} ausgegebenen Netzwerke waren effizienter als das
-rekursiv aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem
-\emph{Odd-Even-Merge}-Netzwerk nicht wiederholen. Zwar erreichen die
-Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
-\emph{Odd-Even}-Mischers findet, das \emph{Odd-Even-Mergesort}-Netzwerk
-bezüglich Geschwindigkeit und Effizienz, ein Beispiel hierfür ist in
-Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Sortiernetzwerkde, die
-effizienter als $\operatorname{OES}(n)$ sind, konnten leider nicht beobachtet
-werden. Wenn $n$ keine Zweietpotenz ist, kann \textsc{SN-Evolution} unter
-Umständen Sortiernetzwerke ausgeben, die schneller als \oes{n} sind.
+Im vorherigen Abschnitt wurde gezeigt, dass der
+\textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
+Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
+\emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind.
+Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht
+erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
+\emph{Odd-Even-Merge}-Netzwerks findet, erreichen das
+\emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
+nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
+Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen.
+
+Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch
+mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution}
+Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht
+beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt
+\textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen.
+\oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der
+Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet
+sich in Tabelle~\ref{tbl:sn-ev-oem-fast}.

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


@@ -1447,6 +1517,56 @@ Umständen Sortiernetzwerke ausgeben, die schneller als \oes{n} sind.
 %\label{fig:10-e2-1239014566}
 %\end{figure}
 
 %\label{fig:10-e2-1239014566}
 %\end{figure}
 

+\begin{table}\label{tbl:sn-ev-oem-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\
+\cline{2-5}
+          & Komp. & Schichten & Komp. & Schichten \\
+\hline
+        8 &   19 &         6 &         19 &         6 \\
+        9 &   26 &         8 &         26 &         8 \\
+       10 &   31 &         9 &         31 &         9 \\
+       11 &   38 & \Gcell  9 & \Gcell  37 &        10 \\
+       12 &   43 & \gcell  9 & \gcell  41 &        10 \\
+       13 &   48 &        10 &         48 &        10 \\
+       14 &   53 &        10 &         53 &        10 \\
+       15 &   59 &        10 &         59 &        10 \\
+       16 &   63 &        10 &         63 &        10 \\
+       17 &   74 &        12 &         74 &        12 \\
+       18 &   82 &        13 &         82 &        13 \\
+       19 &   93 & \Gcell 13 & \Gcell  91 &        14 \\
+       20 &   97 &        14 &         97 &        14 \\
+       21 &  108 & \Gcell 14 & \Gcell 107 &        15 \\
+       22 &  117 & \gcell 14 & \gcell 114 &        15 \\
+       23 &  129 & \Gcell 14 & \Gcell 122 &        15 \\
+       24 &  128 &        15 & \gcell 127 &        15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+  unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der
+  Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n}
+  gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion
+  nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} =
+  1$, $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}
+
+\subsection{Zufälliger Mischer}
+
+Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige
+Leitungszahlen der \emph{bitone Mischer} und für andere Leitungszahlen der
+\emph{Odd-Even}-Mischer bessere Ergebnisse liefert. Beispielsweise hat das
+Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur
+12~Schichten, bei Verwendung des \emph{Odd-Even}-Mischers hingegen nur
+82~Komparatoren. Daher liegt die Idee nahe, beide Mischer-Netzwerke zu nutzen,
+um das beste Ergebnis beider Konstruktionen zu erreichen.
+\textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier
+Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem
+\emph{Odd-Even}-Mischer wählen. \todo{Daten noch in eine Tabelle einfügen.}
+

 %\input{shmoo-aequivalenz.tex}
 
 \newpage
 %\input{shmoo-aequivalenz.tex}
 
 \newpage


@@ -1573,9 +1693,9 @@ Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
 Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
 ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
 ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
 Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
 ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
 ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich

-die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks
-leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und
-der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden.
+die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
+Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
+mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.

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


@@ -1642,7 +1762,7 @@ Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
 $\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
 Pairwise Sorting Network“ \cite{P1992} definiert. Startet man
 \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
 $\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
 Pairwise Sorting Network“ \cite{P1992} definiert. Startet man
 \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,

-16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, dass die gleiche
+16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, das die gleiche

 Anzahl 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.
 Anzahl 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.


@@ -1677,7 +1797,7 @@ Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
 \end{figure}
 
 Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
 \end{figure}
 
 Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach

-regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk einen kleineres
+regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres

 schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das
 einfache Schnittmuster
 \begin{displaymath}
 schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das
 einfache Schnittmuster
 \begin{displaymath}


@@ -1805,8 +1925,8 @@ werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
 16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
 dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
 sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten
 16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
 dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
 sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten

-angeordnet sind. Das heißt, dass das resultierende Netzwerk zwar nicht so
-effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12} ist.
+angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie
+\oes{12}, dafür aber schneller als \oes{12} und \bs{12}.

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