X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=14d0e098928ead9cf605ab5621fb5fa3576cbb27;hb=10f7e26bc636055d9594e7bff4e62d3d93fbd6c9;hp=8123dab8546e4a7b0bfed199be75af1f5b163091;hpb=42ae6550a8bd011f6b987d518386362a8a9e0082;p=diplomarbeit.git

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 8123dab..14d0e09 100644
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -472,10 +472,49 @@ Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
 
 \section{Transformation von Sortiernetzwerken}
 
-\begin{itemize}
-\item Komprimieren (Alle Komparatoren so früh wie möglich anwenden).
-\item Normalisieren (Transformation zu Standard-Sortiernetzwerken).
-\end{itemize}
+\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
+Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
+\emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
+von \emph{Schichten} verstanden.
+
+Diese Anzahl ist insbesondere beim automatisierten Bewerten von
+Komparatornetzwerken interessant. \dots
+
+\subsection{Normalisieren}
+
+\begin{figure}
+  \centering
+  \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
+  \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
+  \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
+  transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
+  intuitiven Konstruktion und die normalisierte Variante.}
+  \label{fig:beispiel_normalisieren}
+\end{figure}
+
+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.
+
+Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
+bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
+zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
+Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
+die unter und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei
+Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist. 
+In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven
+Definition.
+
+In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
+Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche
+Richtung.
 
 \subsection{Zwei Netzwerke kombinieren}
 
@@ -487,24 +526,25 @@ Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
 
 \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
+ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen
+beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass
+sich die Anzahl der Eingänge nicht verändert. Das heißt, dass wir wieder ein
+Sortiernetzwerk mit $n$~Eingängen erhalten müssen.
+
 Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
 Sortiernetzwerk mit $(n-1)$~Leitungen verkleinern, indem man eine Leitung
-entfernt. Zunächst wird angenommen, dass das Minimum oder das Maximum an einem
-der Eingänge anliegt. Der Weg durch das Netzwerk zum entsprechenden Ausgang
-ist dadurch fest vorgegeben, insbesondere welche Komparatoren dafür sorgen,
-dass die Leitung gewechselt wird und welche nicht.
+„eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem
+bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maxim
+durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an einem der
+„Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten Index.
+Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und welche
+dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum jeden
+Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
 Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
 das {\em Odd-Even-Transpositionsort-Netzwerk}.
 
-Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
-ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt
-haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
-Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
-zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
-ersetzt. Das Resultat zeigt Abbildung~\ref{fig:oe-transposition-cut1}. Wenn
-man die Maximum-Leitung entfernt (Abbildung~\ref{fig:oe-transposition-cut2}),
-erhält man ein Sortiernetzwerk für $(n-1)$~Leitungen.
-
 \begin{figure}
   \centering
   \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
@@ -519,6 +559,31 @@ erhält man ein Sortiernetzwerk für $(n-1)$~Leitungen.
   letzten Abbildung ist $\textrm{OET}(7)$ markiert.}
 \end{figure}
 
+Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
+ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt
+haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
+Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
+zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
+ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
+das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
+auf die keine Komparatoren mehr berührt
+(Abbildung~\ref{fig:oe-transposition-cut1}).
+
+Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
+Komparatornetzwerk immernoch sortiert werden: Wir haben lediglich die Position
+des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss die
+Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum liegt.
+Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme
+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.
+
+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}.
+
 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
@@ -527,9 +592,58 @@ Darstellung ergibt. Ausserdem ist das
 zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
 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 wir auf diese Art und
+Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
+mit $n$~Eingängen reduzieren.
+
+Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
+Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
+auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
+ein $n$-Sortiernetzwerk auf ein $m$-Sortiernetzwerk zu reduzieren, ergeben
+sich insgesamt
+\begin{displaymath}
+  \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
+  \quad (n > m)
+\end{displaymath}
+Möglichkeiten. Diese Möglichkeiten sind nicht alle 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.
+
+\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass
+es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise
+Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnitte
+reduziert, die Menge der erreichbaren Sortiernetzwerke bleibt aber
+unverändert. Die Anzahl der möglichen „Schnittmuster“ setzt sich zusammen aus
+der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
+und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
+Formel:
+\begin{displaymath}
+  2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
+  = 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
+  = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!}
+  \quad (n > m)
+\end{displaymath}
+
+Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden
+Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
+ein Sortiernetzwerk mit 16~Eingängen zu reduzieren sind 16~Schnitte notwendig,
+für die es bereits etwa ${3,939 \cdot 10^{13}}$ Möglichkeiten gibt. Ein
+Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter
+erheblichem Ressourcenaufwand möglich.
+
+Das Programm {\sc SN-Evolution-Cut} implementiert einen evolutionären
+Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
+Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
+möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}.
+
 \begin{itemize}
-\item Min-Richtung
-\item Max-Richtung
+  \item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort.
+  \item Wie gut kann man durch wegschneiden werden?
+  \item Wieviele Schnitte ergeben das selbe Netzwerk?
 \end{itemize}
 
 \section{Der evolutionäre Ansatz}
@@ -537,7 +651,7 @@ Ausgabe und kann entfernt werden.
 Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
 die vorgestellten Methoden kombiniert.
 
-\subsection{Bewertungsfunktion}
+\subsection{Bewertungsfunktion}\label{sect:bewertung}
 
 Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
 {\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
@@ -659,254 +773,211 @@ acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
 \label{fig:10-e2-1239014566}
 \end{figure}
 
-% ============
-
-\section{Shmoo-Äquivalenz}
-
-Die folgenden 16-Eingang-Sortiernetzwerke wurden alle mit dem
-\emph{Algorithmus~1} gefunden. Sie haben alle 63~Komparatoren in 10~Schichten,
-jeweils die selbe Anzahl wie Odd-Even-Mergesort.
-
-Um wiederkehrende Muster in den hinteren Schichten der erzeugten
-Sortiernetzwerke besser untersuchen zu können, wurden die erzeugten Netzwerke
-in Gruppen aufgeteilt. Zwei Netzwerke befinden sich dann in der selben
-Gruppen, wenn die Nullen bzw. Einsen, die auf einer Leitung vorkommen können,
-nach der 5.~Schicht (Schicht~4, da bei Null mit dem Zählen begonnen wird)
-nicht mehr ändert. Das heißt, dass die Schichten 0--4 unterschiedlich
-aufgebaut sind, aber den selben Effekt erziehlen. Die Schichten 5--9 sind
-hingegen innerhalb einer Gruppe austauschbar und oft (immer?) identisch.
-
-Die Anzahl der Netzwerke in den jeweiligen Gruppen ist unterschiedlich. Zur
-Zeit sind in den Gruppen so viele Netzwerke:\\
-\begin{tabular}{|l|r|r|} \hline
-Gruppe~0 & 18 & $48,7\%$ \\
-Gruppe~1 & 9  & $24,3\%$ \\
-Gruppe~2 & 6  & $16,2\%$ \\
-Gruppe~3 & 3  & $8,1\%$ \\
-Gruppe~4 & 1  & $2,7\%$ \\ \hline
-\end{tabular}
-
-Die hinteren Schichten zwischen den Gruppen~1 und~3 schauen so aus, als wären
-sie nur gespiegelt. Warum kommt Gruppe~1 aber viel häufiger vor? Ggf. eine
-Konsequenz aus dem Normieren?
-
-Dito für die Gruppen~2 und~4. Warum ist die eine häufiger?
-
-Ist Gruppe~0 symmetrisch bzgl. der Leitungen?
-
-% Gruppe 0
-
-\begin{figure}
-\begin{center}
-\input{images/16-e1/group0/16-e1-1258009316.tex}
-\end{center}
-\caption{{\tt images/16-e1/group0/16-e1-1258009316.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1258009316}
-\end{figure}
-
-\begin{figure}
-\begin{center}
-\input{images/16-e1/group0/16-e1-1258010866.tex}
-\end{center}
-\caption{{\tt images/16-e1/group0/16-e1-1258010866.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1258010866}
-\end{figure}
-
-\begin{figure}
-\begin{center}
-\input{images/16-e1/group0/16-e1-1258011861.tex}
-\end{center}
-\caption{{\tt images/16-e1/group0/16-e1-1258011861.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1258011861}
-\end{figure}
-
-\begin{figure}
-\begin{center}
-\input{images/16-e1/group0/16-e1-1259060992.tex}
-\end{center}
-\caption{{\tt images/16-e1/group0/16-e1-1259060992.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1259060992}
-\end{figure}
-
-%\begin{figure}
-%\begin{center}
-%\input{images/16-e1/group0/16-e1-1259061148.tex}
-%\end{center}
-%\caption{{\tt images/16-e1/group0/16-e1-1259061148.tex}: 63~Komparatoren in
-%10~Schichten.}
-%\label{fig:16-e1-1259061148}
-%\end{figure}
-
-% Gruppe 1
-
-\begin{figure}
-\begin{center}
-\input{images/16-e1/group1/16-e1-1258009982.tex}
-\end{center}
-\caption{{\tt images/16-e1/group1/16-e1-1258009982.tex}: 63~Komparatoren in 10~Schichten.
-Schichten 4--9 identisch zu 16-e1-1258030047 (Gruppe~1).}
-\label{fig:16-e1-1258009982}
-\end{figure}
-
-\begin{figure}
-\begin{center}
-\input{images/16-e1/group1/16-e1-1258010023.tex}
-\end{center}
-\caption{{\tt images/16-e1/group1/16-e1-1258010023.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1258010023}
-\end{figure}
-
-\begin{figure}
-\begin{center}
-\input{images/16-e1/group1/16-e1-1258029734.tex}
-\end{center}
-\caption{{\tt images/16-e1/group1/16-e1-1258029734.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1258029734}
-\end{figure}
+\subsection{Güte}
 
-\begin{figure}
-\begin{center}
-\input{images/16-e1/group1/16-e1-1258030047.tex}
-\end{center}
-\caption{{\tt images/16-e1/group1/16-e1-1258030047.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1258030047}
-\end{figure}
+\begin{itemize}
+\item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}.
+\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
+\end{itemize}
 
-%\begin{figure}
-%\begin{center}
-%\input{images/16-e1/group1/16-e1-1258034768.tex}
-%\end{center}
-%\caption{{\tt images/16-e1/group1/16-e1-1258034768.tex}: 63~Komparatoren in
-%10~Schichten.}
-%\label{fig:16-e1-1258034768}
-%\end{figure}
+\section{Markov-Kette}
+
+Der evolutionäre Algorithmus aus dem vorherigen Abschnitt verwendete immer
+zwei zufällige Sortiernetzwerke („Individuen“) aus einer Population. Da die
+beiden „Eltern“ zufällig und unabhängig voneinander ausgewählt werden, kann es
+vorkommen, dass das selbe Sortiernetzwerk zweimal verwendet und mit sich
+selbst kombiniert wird.
+
+Macht man diesen Spezialfall zum Regelfall, indem man \emph{immer} das
+aktuelle Netzwerk mit sich selbst kombiniert und anschließend die Hälfte aller
+Leitungen eliminiert, lassen sich einige interessante Beobachtungen anstellen.
+Netzwerke, die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von
+$S_0$ mit sich selbst und anschließendem Eliminieren der Hälfte der Leitungen
+hervorgehen können, heißen \emph{Nachfolger} von $S_0$.
+
+Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
+gerichteten Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
+Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
+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.
+
+Der Algorithmus {\sc SN-Markov} legt auf diesem 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 er das aktuelle Sortiernetzwerk mit sich selbst und erhält so
+einen zufälligen Nachfolger.
 
-% Gruppe 2
+\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{figure}
-\begin{center}
-\input{images/16-e1/group2/16-e1-1258029063.tex}
-\end{center}
-\caption{{\tt images/16-e1/group2/16-e1-1258029063.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1258029063}
-\end{figure}
+\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}
-\begin{center}
-\input{images/16-e1/group2/16-e1-1258034821.tex}
-\end{center}
-\caption{{\tt images/16-e1/group2/16-e1-1258034821.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1258034821}
+  \begin{center}
+  \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16.pdf}
+  \end{center}
+  \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden.}
+  \label{fig:markov-comparators-16}
 \end{figure}
 
-\begin{figure}
-\begin{center}
-\input{images/16-e1/group2/16-e1-1259054993.tex}
-\end{center}
-\caption{{\tt images/16-e1/group2/16-e1-1259054993.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1259054993}
-\end{figure}
+%\input{shmoo-aequivalenz.tex}
 
-\begin{figure}
-\begin{center}
-\input{images/16-e1/group2/16-e1-1259058588.tex}
-\end{center}
-\caption{{\tt images/16-e1/group2/16-e1-1259058588.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1259058588}
-\end{figure}
+\section{Optimierung der Schnitte}
 
-%\begin{figure}
-%\begin{center}
-%\input{images/16-e1/group2/16-e1-1259063485.tex}
-%\end{center}
-%\caption{{\tt images/16-e1/group2/16-e1-1259063485.tex}: 63~Komparatoren in
-%10~Schichten.}
-%\label{fig:16-e1-1259063485}
-%\end{figure}
+Der \emph{evolution-cut}-Algorithmus nimmt ein gegebenes Sortiernetzwerk mit
+$n$~Leitungen und sucht die beste Sequenz von $c$~Min- und Max-Schnitten um
+ein ${(n-c)}$-Sortiernetzwerk zu erhalten.
 
-%\begin{figure}
-%\begin{center}
-%\input{images/16-e1/group2/16-e1-1259063618.tex}
-%\end{center}
-%\caption{{\tt images/16-e1/group2/16-e1-1259063618.tex}: 63~Komparatoren in
-%10~Schichten.}
-%\label{fig:16-e1-1259063618}
-%\end{figure}
-
-% Gruppe 3
+Bei diesem Algorithmus werden die \emph{Schnitt-Sequenzen} als Individuen
+verwendet. Eine \emph{Schnitt-Sequenz} ist eine Liste mit $c$~Schnitten, die
+jeweils durch die Start-Leitung und die Richtung \textit{Min} beziehungsweise
+\textit{Max} gegeben ist. Der Algorithmus wendet jeden Schnitt einzeln an, so
+dass eine Leitungsnummer mehrfach in einer Schnittsequenz vorkommen kann. Die
+höchste zulässige Leitungsnummer ist abhängig von der Position des Schnitts in
+der Sequenz. Der Schnitt an Position~$i$ darf höchstens die
+Leitungsnummer~${n-i-1}$ enthalten.\footnote{Die niedrigste Leitungsnummer ist
+$0$, die höchste Leitungsnummer eines $n$-Sortiernetzwerks ist $n-1$.}
 
-\begin{figure}
-\begin{center}
-\input{images/16-e1/group3/16-e1-1258012027.tex}
-\end{center}
-\caption{{\tt images/16-e1/group3/16-e1-1258012027.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1258012027}
-\end{figure}
+Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte der einen
+Schnitt-Sequenz verwendet und die letzten ${c-r}$~Schnitte der zweiten
+Sequenz. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.
 
-\begin{figure}
-\begin{center}
-\input{images/16-e1/group3/16-e1-1258037039.tex}
-\end{center}
-\caption{{\tt images/16-e1/group3/16-e1-1258037039.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1258037039}
-\end{figure}
+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
+Schnitt-Richtung.
 
 \begin{figure}
 \begin{center}
-\input{images/16-e1/group3/16-e1-1259065042.tex}
+\input{images/16-ec-1277186619.tex}
 \end{center}
-\caption{{\tt images/16-e1/group3/16-e1-1259065042.tex}: 63~Komparatoren in
-10~Schichten.}
-\label{fig:16-e1-1259065042}
+\caption{{\tt images/16-ec-1277186619.tex}: Sortiernetzwerk mit 16~Leitungen
+  und 68~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+  \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(32)$ durch
+  16~Schnitte erzeugt.}
+\label{fig:16-ec-1277186619}
 \end{figure}
 
-% Gruppe 4
+Wendet man den \emph{evolution-cut}-Algorithmus auf das
+Bitonic-Mergesort-Netzwerk $M(n)$ an und setzt die Anzahl der Schnitte~$c$ auf
+$\frac{n}{2}$, so erhält man Sortiernetzwerke, die weniger Komparatoren
+benötigen als $M(\frac{n}{2})$.
+
+Das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619} ist entstanden,
+indem der Algorithmus \emph{evolution-cut} auf das $M(32)$-Sortiernetzwerk
+angewendet wurde. Der Algorithmus fand eine Schnitt-Sequenz aus 16~Schnitten,
+die ein Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in 10~Schichten
+erzeugt. Das $M(16)$-Sortiernetzwerk besteht aus 80~Komparatoren in
+10~Schichten.
+
+Dieses Ergebnis deckt sich mit dem Sortiernetzwerk, dass
+\emph{Moritz Mühlenthaler} und \emph{Rolf Wanka} in ihrer Veröffentlichung
+„Improving Bitonic Sorting by Wire Elimination“ vorstellen. Sie verwenden
+Schnitte, um Komparatoren beim bitonen $(n,n)$-Mischer enizusparen. Ein
+sukzessive aus optimieren Mischern aufgebautes Sortiernetzwerk spart
+--~verglichen mit dem Bitonic-Mergesort-Netzwerk~-- $\frac{1}{4}n(\log n - 1)$
+Komparatoren ein. Bei einem Sortiernetzwerk mit 16~Leitungen also
+12~Komparatoren -- 68 statt 80.
 
 \begin{figure}
 \begin{center}
-\input{images/16-e1/group4/16-e1-1259060520.tex}
+\input{images/32-ec-1277190372.tex}
 \end{center}
-\caption{{\tt images/16-e1/group4/16-e1-1259060520.tex}: 63~Komparatoren in 10~Schichten.
-(Gruppe~4).}
-\label{fig:16-e1-1259060520}
+\caption{{\tt images/32-ec-1277190372.tex}: Sortiernetzwerk mit 32~Leitungen
+  und 206~Komparatoren in 15~Schichten. Das Netzwerk wurde von dem Algorithmus
+  \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(64)$ durch
+  32~Schnitte erzeugt.}
+\label{fig:32-ec-1277190372}
 \end{figure}
 
-\begin{figure}
-\begin{center}
-\input{images/16-e1/group4/16-e1-1259067171.tex}
-\end{center}
-\caption{{\tt images/16-e1/group4/16-e1-1259067171.tex}: 63~Komparatoren in 10~Schichten.
-(Gruppe~4).}
-\label{fig:16-e1-1259067171}
-\end{figure}
-
-\subsection{Güte}
-
-\begin{itemize}
-\item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}.
-\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
-\end{itemize}
-
-\subsection{Vom evolutionären Algorithmus zu einer Markov-Kette}
-
-\begin{itemize}
-\item Kombiniere immer das aktuelle Netzwerk mit sich selbst.
-\item Kann die Mindestgüte immernoch erreicht werden? ({\em Ich denke schon.})
-\item Anzahl der erreichbaren Sortiernetzwerke.
-\end{itemize}
+Abbildung~\ref{fig:32-ec-1277190372} zeigt ein 32-Sortiernetzwerk, dass vom
+\emph{evolution-cut}-Algorithmus aus dem $M(64)$-Netzwerk erzeugt wurde. Es
+besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als
+$M(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler
+und Wankas Methode konstruiert wird. Die Anzahl der Schichten ist bei allen
+Netzwerken gleich.
+
+\textbf{TODO:} $M(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten
+möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$
+Komparatoren; $M(64)$: 672~Komparatoren.
+
+Schnitt-Sequenz:
+MIN( 92)
+MAX( 80)
+MIN(100)
+MAX( 54)
+MAX(102)
+MAX( 53)
+MAX(105)
+MAX(  6)
+MAX( 99)
+MAX( 79)
+MAX( 26)
+MIN(111)
+MAX( 12)
+MIN( 22)
+MAX( 61)
+MAX( 72)
+MAX( 68)
+MIN( 80)
+MAX( 80)
+MAX( 99)
+MAX(105)
+MAX(  0)
+MIN(  8)
+MAX( 40)
+MAX( 74)
+MAX( 40)
+MAX( 40)
+MIN( 56)
+MAX( 27)
+MAX( 13)
+MAX(  1)
+MAX( 81)
+MAX( 17)
+MAX(  4)
+MIN( 36)
+MIN( 22)
+MAX( 13)
+MIN( 72)
+MAX( 24)
+MAX(  5)
+MIN( 10)
+MAX( 59)
+MIN( 37)
+MAX( 65)
+MAX( 46)
+MAX( 73)
+MAX( 58)
+MAX( 29)
+MAX( 65)
+MIN( 23)
+MAX( 56)
+MAX( 11)
+MIN( 75)
+MIN( 51)
+MIN( 46)
+MIN( 34)
+MAX( 32)
+MAX(  6)
+MAX( 37)
+MIN(  4)
+MIN( 28)
+MIN( 20)
+MAX( 33)
+MAX( 34)
+
+% images/32-ec-1277190372.tex
 
 \section{Empirische Beobachtungen}