-\documentclass[a4paper,10pt]{article}
+\documentclass[a4paper,11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{ngerman}
\usepackage{fancyhdr}
% Fuer mathtoolsset
\usepackage{mathtools}
-\geometry{paper=a4paper,margin=25mm}
+\geometry{paper=a4paper,margin=30mm}
\pagestyle{fancy}
%\fancyhf{}
\tikzstyle{diredge} = [draw,thick,->]
\tikzstyle{prob} = [font=\tiny]
+\tikzstyle{edge minimum} = [edge,color=blue!20]
+\tikzstyle{edge maximum} = [edge,color=red!20]
+\tikzstyle{vertex active minimum} = [vertex,color=blue!50, fill=blue!50]
+\tikzstyle{vertex active maximum} = [vertex,color=red!50, fill=red!50]
+\tikzstyle{vertex active minimum maximum} = [vertex,color=violet!50, fill=violet!50]
+\tikzstyle{vertex inactive minimum} = [vertex,color=blue!20, fill=blue!20]
+\tikzstyle{vertex inactive maximum} = [vertex,color=red!20, fill=red!20]
+\tikzstyle{vertex inactive minimum maximum} = [vertex,color=black!20, fill=black!20]
+\tikzstyle{comp active minimum} = [comp]
+\tikzstyle{comp active maximum} = [comp]
+\tikzstyle{comp active minimum maximum} = [comp,color=black!20]
+\tikzstyle{comp inactive minimum} = [comp,color=blue!20]
+\tikzstyle{comp inactive maximum} = [comp,color=red!20]
+\tikzstyle{comp inactive minimum maximum} = [comp,color=black!20]
+
\tikzstyle{red box} = [draw,-,color=red, top color=red!2,bottom color=red!10]
\tikzstyle{blue box} = [draw,-,color=blue,top color=blue!2,bottom color=blue!10]
\tikzstyle{green box} = [draw,-,color=teal,top color=teal!2,bottom color=teal!10]
\newpage
\tableofcontents
-\newpage
+\newpage
\section{Motivation und Einleitung}
\subsection{Motivation}\label{sect:motivation}
\subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke}
-{\em Komparatoren} sind die Bausteine, die {\em Sortiernetzwerken} zugrunde
-liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten können.
-Ausserdem besitzt ein {\em Komparator} zwei Ausgänge, die im Gegensatz zu den
-Eingängen unterscheidbar sind: Die grö"sere der beiden Zahlen wird immer auf
-dem einen, die kleinere der beiden Zahlen immer auf dem anderen Ausgang
-ausgegeben.
+\emph{Komparatoren} sind die Bausteine, die \emph{Komparatornetzwerken}
+zugrunde liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten
+können und zwei Ausgänge, auf denen die Zahlen wieder ausgegeben werden. Dabei
+sind die Ausgänge im Gegensatz zu den Eingängen unterscheidbar, da die größere
+der beiden Zahlen wird immer auf dem einen, die kleinere der beiden Zahlen
+immer auf dem anderen Ausgang ausgegeben ausgegeben wird.
-Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die
-Ausgänge von Komparatoren mit dem Eingängen anderer Komparatoren verbindet,
+Kombiniert man mehrere \emph{Komparatoren} miteinander, das heißt, dass die
+Ausgänge eines Komparators mit Eingängen weiterer Komparatoren verbunden sind,
erhält man ein {\em Komparatornetzwerk}.
\begin{figure}
\end{figure}
Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
-Komparatornetzwerk aus fünf Komparatoren in der üblichen Darstellungsweise:
-Die horizontalen Linien stellen Leitungen von den Eingängen auf der linken
-Seite zu den Ausgängen auf er rechten Seite dar. Die vertikalen Pfeile
-symbolisieren die Komparatoren, die die Werte "`auf den Leitungen"'
-vergleichen und ggf. vertauschen. Nach einem Komparator befindet sich die
+\emph{Komparatornetzwerk} aus fünf Komparatoren. Insgesamt gibt es vier
+verschiedene Eingänge und vier Ausgänge. Die Ein- und Ausgänge werden durch
+eine horizontale Linie dargestellt und als \emph{Leitung} bezeichnet. Die
+\emph{Komparatoren} sind durch vertikale Pfeile dargestellt und verbinden je
+zwei verschiedene \emph{Leitungen} miteinander. Die Verbindungsstellen von
+\emph{Leitungen} und \emph{Komparatoren} sind zur besseren Übersichlichkeit
+durch schwarze Punkte symbolisiert.
+
+Auf der linken Seite befinden sich die Eingänge. Hier wird eine Zahlenfolge in
+das Netzwerk hineingegeben. Jeder Komparator vergleicht die Zahlen „auf“ den
+beiden Leitungen, die er verbindet. Nach einem Komparator befindet sich die
kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
-befindet sich auf der Leitung auf der der Pfeil seinen Ursprung hat.
+befindet sich auf der Leitung, auf der der Pfeil seinen Ursprung hat.
Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
gleichzeitig angewandt werden. Das Beispiel in
Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
-vergleicht in einem ersten Schritt die zwei oberen und die zwei unteren
-Leitungen gleichzeitig. Eine Gruppe von Komparatoren, die gleichzeitig
-angewendet werden können, nennt man eine \emph{Schicht} des
-Komparatornetwerks. Die \emph{Verzögerung} eines Komparatornetzwerks ist
-gleichbedeutend mit der Anzahl der Schichten, in die sich die Komparatoren
-mindestens gruppieren lassen, da sie die Anzahl der benötigten parallelen
-Schritte darstellt.
-
-Komparatornetzwerke, die für jede beliebige Eingabepermutation eine
-Ausgabe erzeugen, die der Sortierung der Eingabe entspricht, heißen
-{\em Sortiernetzwerke}. Das in
+vergleicht die zwei oberen und die zwei unteren Leitungen gleichzeitig. Eine
+Gruppe von Komparatoren, die gleichzeitig angewendet werden können, nennt man
+eine \emph{Schicht} des Komparatornetwerks. Die \emph{Verzögerung} eines
+Komparatornetzwerks ist gleichbedeutend mit der Anzahl der Schichten, in die
+sich die Komparatoren mindestens gruppieren lassen, da sie die Anzahl der
+benötigten parallelen Schritte darstellt.
+
+\emph{Komparatornetzwerke}, die für \emph{jede} Eingabefolge eine Ausgabe
+erzeugen, die der Sortierung der Eingabe entspricht, heißen
+\emph{Sortiernetzwerke}. Das in
Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
-ist kein Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ würde zur Ausgabe
-${(2, 1, 3, 4)}$ führen -- die bestehenden Sortierung wird also sogar
+ist \emph{kein} Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur
+Ausgabe ${(2, 1, 3, 4)}$ -- die bestehenden Sortierung wird also sogar
zerstört.
-Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
-{\em nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich.
-Dieses Gegenbeispiel zu finden ist allerdings aufwendig.
-
-\todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein
-Netzwerk sortiert, ist doch NP-vollständig, also müsste doch das Finden eines
-Gegenbeispiels im Allgemeinen auch exponentialle Laufzeit haben..?}
-\todo{Wenn die {\em Entscheidung}, ob ein Netzwerk sortiert, NP-vollständig
-ist, müsse man dann nicht einen Zeugen für die Sortiereigenschaft angeben
-können?}
-
-\todo{$0-1$-Prinzip}
-
-Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft
-besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen
-ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle
-$2^n$~0-1-Folgen sortiert.
-
-Sortiernetzwerke:
-\begin{itemize}
-\item Ein Komparator-Netzwerk ist $\ldots$
-\item Ein Komparator-Netzwerk ist ein Sortiernetzwerk, wenn $\ldots$
-\item Die Frage nach der Sortiereigenschaft ist NP-vollständig.
-\end{itemize}
+\begin{figure}
+ \begin{center}
+ \input{images/09-e2-c24-allbut1.tex}
+ \end{center}
+ \caption{Ein \emph{Komparatornetzwerk} mit neun Eingängen und
+ 24~Komparatoren, die in 8~Schichten angeordnet sind. Das Netzwerk sortiert
+ alle Eingaben, bei denen das Minimum nicht auf dem mittleren Eingang liegt.}
+ \label{fig:09-e2-c24-allbut1}
+\end{figure}
+Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft {\em
+nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich. Das
+Komparatornetzwerk wird auf das Gegenbeispiel angewendet und anschließend wird
+überprüft, ob die Ausgabe sortiert ist. Ist sie es nicht heißt das, dass es
+mindestens eine Eingabefolge gibt, die nicht sortiert wird. Entsprechend der
+Definition handelt es sich bei dem \emph{Komparatornetzwerk} folglich
+\emph{nicht} um ein \emph{Sortiernetzwerk}. Ein solches Gegenbeispiel für ein
+gegebenes Komparatornetzwerk zu finden ist nach heutigem Kenntnisstand jedoch
+nicht \emph{effizient} möglich.
+
+Beispielsweise sortiert das Komparatornetzwerk in
+Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880 möglichen
+Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4, 8, 6)$
+lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die
+Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge
+$(1, 0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt.
+
+Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein
+Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese
+Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$
+über-exponentiell schnell, so dass ein Ausprobieren aller möglichen
+Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen
+ist.\footnote{1.307.674.368.000 Permutationen}
+
+Glücklicherweise reicht es aus, alle möglichen 0-1-Folgen zu überprüfen, wie
+\textit{Donald~E. Knuth} in \cite{KNUTH} zeigt. Die Beweisidee ist folgende:
+Angenommen ein Komparatornetzwerk sortiert alle 0-1-Folgen und es gibt eine
+Permutation $E = (e_0, \dots, e_{n-1})$ beliebiger Zahlen, die nicht sortiert
+wird. Die Ausgabefolge sei $A = (a_0, \dots, a_{n-1})$. Sei $i$ eine Position
+in der Ausgabe, die die Sortierbedingung verletzt:
+\begin{displaymath}
+ a_0 \leqq a_1 \leqq \dots \leqq a_{i-1} > a_i \dots
+\end{displaymath}
+Die Eingabe kann mittels
+\begin{displaymath}
+ \hat{e}_j = \left\{
+ \begin{array}{cl}
+ 0 & e_j \leqq a_i \\
+ 1 & e_j > a_i
+ \end{array} \right.
+\end{displaymath}
+auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme von
+Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das
+Verhalten jedes einzelnen Komparators nicht, so dass die Annahme auf einen
+Widerspruch geführt wird.
+
+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)$
+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,
+sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für
+aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung
+eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa
+4,3~Millarden Tests notwendig, die einen Rechner durchaus mehrere Minuten
+beschäftigen.
\subsubsection{Evolutionäre Algorithmen}
verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
-werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em
+werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
Gütefunktion}.
Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
-es oft einfach ist {\em irgendeine} Lösung anzugeben. Zum anderen muss eine
-Methode für die Rekombination existieren. Das insbesondere dann problematisch
-wenn {\em Nebenbedingungen} eingehalten werden müssen.
-
-\begin{itemize}
-\item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$
-\item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die
-Mutation \textit{(vermutlich)} nicht (effizient) möglich.
-\end{itemize}
+es oft einfach ist {\em irgendeine} Lösung anzugeben. Die angegebenen
+Algorithmen verwenden als einfache, initiale Lösung häufig das
+\emph{Odd-Even-Transpositionsort}-Netzwerk, das in
+Abschnitt~\ref{sect:odd_even_transpositionsort} beschrieben wird. Zum anderen
+muss eine Methode für die Rekombination existieren. Das ist insbesondere dann
+problematisch, wenn {\em Nebenbedingungen} eingehalten werden müssen.
+
+Beim Aussuchen von zufälligen Lösungen aus der Population, der
+\emph{Selektion}, werden gute Lösungen bevorzugt. Wie sehr diese Lösungen
+bevorzugt werden, hat einen starken Einfluss auf das Verhalten des
+Algorithmus. Werden gute Lösungen stark bevorzugt, konvergiert der Algorithmus
+schnell gegen ein (lokales) Optimum. Dieses \textit{Exploitation} (Englisch
+für „Ausnutzung“) genannte Verhalten sorgt dafür, dass sich der Algorithmus
+schnell auf eine Lösung festlegt und andere, möglicherweise bessere lokale
+Optima nicht mehr findet. Werden gute Lösungen hingegen nur wenig bevorzugt,
+erforscht der Algorithmus den Lösungsraum in viele Richtungen. Dieses
+\textit{Exploration} (Englisch für „Erforschung“) genannte Verhalten sorgt
+zwar dafür, dass der Algorithmus langsamer auf ein Optimum zusteuert, dafür
+findet er aber in der Regel bessere Lösungen.
+
+Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
+Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
+nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
+eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
+beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
+zwischen verschiedenen Leitungszahlen stark unterscheiden.
+
+Die \textit{Exploration} kann von einem weiteren Mechanismus unterstützt
+werden, der ebenfalls der Evolutionslehre entliehen ist, der \emph{Mutation}.
+Dabei werden Lösungen zufällig verändert, so dass auch andere Lösungen „in der
+Nähe“ von direkten Nachfolgern erreicht werden können. Das hilft insbesondere
+bei der intensiven Suche in der Nähe eines lokalen Optimums aber auch beim
+„Ausbrechen“ und finden noch besserer Lösungen.
+
+Bei \emph{Sortiernetzwerken} ist eine \emph{Mutation} leider immer damit
+verbunden, dass anschließend die Sortiereigenschaft des resultierenden
+\emph{Komparatornetzwerks} wieder überprüft werden muss, da selbst das
+Hinzufügen eines zufälligen Komparators diese Eigenschaft zerstören kann. Beim
+Suchen möglichst effizienter Netzwerke ist natürlich das zufällige Entfernen
+von Komparatoren interessanter, was die Sortiereigenschaft sehr oft aufhebt.
+
+Die im Folgenden beschriebenen Algorithmen mutieren (verändern) daher nicht
+die \emph{Sortiernetzwerke} selbst, sondern verzichten auf Mutation oder
+mutieren lediglich Transformationen von Sortiernetzwerken, die die
+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.
+\newpage
\section{Bekannte konstruktive Sortiernetzwerke}
+\label{sect:konstruktive_netzwerke}
Übersicht über bekannte konstruktive Sortiernetzwerke.
-\subsection{Odd-Even-Transpositionsort}
+\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der
einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
"`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
-Abbildung~\ref{fig:odd_even_transposition_08} zeigt das OET-Netzwerk für
+Abbildung~\ref{fig:odd-even-transposition-08} zeigt das OET-Netzwerk für
${n = 8}$ Leitungen.
\begin{figure}
-\begin{center}
-\input{images/oe-transposition-8.tex}
-\end{center}
-\caption{Das {\em Odd-Even-Transpositionsort-Netzwerk} für acht Eingänge.}
-\label{fig:odd_even_transposition_08}
+ \begin{center}
+ \input{images/oe-transposition-8.tex}
+ \end{center}
+ \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.}
+ \label{fig:odd-even-transposition-08}
\end{figure}
-\subsection{Batcher's Mergesort}
-
-Ein Netzwerk von K.~E.~Batcher. Siehe:
-K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring
-Joint Comput. Conf., Vol. 32, 307-314 (1968)
-\todo{Bibtex!}
+Dass das Odd-Even-Transporitionsort-Netzwerk tatsächlich jede beliegibe
+Eingabe sortiert ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass
+sowohl das Minimum als auch das Maximum durch das im Netzwerk enthaltene
+Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt. Beim
+Odd-Even-Transporitionsort-Netzwerk mit drei Eingängen,
+$\operatorname{OET}(3)$, ist die Ausgabe folglich sortiert.
+
+Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen,
+indem man $\operatorname{OET}(n)$ auf $\operatorname{OET}(n-1)$ durch
+Herausschneiden einer Leitung reduziert. In
+Abschnitt~\ref{sect:leitungen_entfernen} wird das Vorgehen im Detail
+beschrieben, Abbildung~\ref{fig:oe-transposition-cut} zeigt das
+Herausschneiden einer Leitung aus $\operatorname{OET}(8)$.
+
+Das Odd-Even-Transporitionsort-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. Andere Sortiernetzwerke benötigen deutlich weniger
+Komparatoren, beispielsweise $\mathcal{O}(n (\log n)^2)$, die in weniger
+Schichten, zum Beispiel $\mathcal{O}(\log n)$, angeordnet sind.
+
+Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
+folgenden Algorithmen benötigen ein möglichst einfaches Sortiernetzwerk als
+Starteingabe, auf dessen Basis sie versuchen optimierte Sortiernetzwerke zu
+finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
+Algorithmen.
+
+\subsection{Das bitone Mergesort-Netzwerk}
+
+Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
+Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968}
+veröffentlicht wurde. Es ist deutlich effizienter als das
+Odd-Even-Transposi\-tionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
+Komparatoren als auch bezüglich der benötigten Zeit, also der Anzahl der
+Schichten.
+
+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
+verleiht dem Sortiernetzwerk seinen Namen.
+
+Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
+Instanzen des Netzwerks, deren Leitungszahl $n = 2^t$ eine Zweierpotenz ist.
+Es ist jedoch möglich das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
\subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
-Das Netzwerk basiert auf dem {\em bitonen Mischer}, einem Komparator-Netzwerk,
-das eine beliebige bitone Folge in eine sortierte Listen umordnen kann. Eine
-{\em bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton
-fallenden Folge, oder ein zyklischer Shift davon.
-Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinipiellen Möglichkeiten
-die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für
-Batcher's Mergesort-Netzwerk zeigen die Abbildungen~\ref{fig:beispiel-biton-0}
+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
+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.
> v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
"`linken"' Folge, $u_{m-1}$, kleiner ist als das kleinste Element der
-"`rechten"' Folge, $v_{m-1}$. Daraus folgt, dass die entstehende Folge aus
-zwei bitonen Folgen besteht, die rekursiv zusammengeführt werden können.
-Abbildung~\ref{fig:bitonic-merge-normal} zeigt die Situationen vor und nach
-diesem Schritt des Mischers.
-
-Mit dem bitonen Mischer auch zwei aufsteigend sortierte Folgen sortiert
-werden. Dazu ist lediglich das "`Umbenennen"' der Leitungen notwendig.
-Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das Schema des bitonen
-Mischers für zwei aufsteigend sortierte Foglen. Durch das Umbenennen verändert
-sich das Muster der Komparatoren ein wenig: Statt an eine Treppe erinnert das
-Muster nun an einen Trichter.
+"`rechten"' Folge, $v_{m-1}$. Daraus folgt, dass das Resultat in zwei bitone
+Folgen aufteilen lässt: Eine aufsteigende~/ absteigende Folge und eine
+absteigende~/ aufsteigende Folge. Abbildung~\ref{fig:bitonic-merge-normal}
+zeigt die Situationen vor und nach diesem Schritt des Mischers.
+
+Um die Folge vollständig zu sortieren, müssen anschließend die beiden
+resultierenden bitonen Folgen sortiert werden. Die geschieht ebenfalls
+mithilfe des bitonen Mischers, mit zwei Instanzen von
+$\operatorname{BM}(\frac{n}{2})$. Diese rekursive Definition endet mit dem
+bitonen Mischer mit zwei Leitungen, $\operatorname{BM}(2)$, der als
+Komparator-Netzwerk mit einem Komparator zwischen den beiden Leitungen
+definiert ist.
+
+Der bitonen Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist
+lediglich eine etwas modifizierte Vergleichs-Kaskade im ersten Schritt
+notwendig. Die folgenden, kleineren Mischer erhalten als Eingabe wieder eine
+„echte“ bitone Folge. Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das
+Schema des bitonen Mischers für zwei aufsteigend sortierte Foglen. Durch das
+Umdrehen einer Folge verändert sich das Muster der Komparatoren ein wenig:
+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
+$\frac{1}{2} n \log(n) = \mathcal{O}\left(n \log(n)\right)$~Komparatoren
+besteht, die in $\log(n)$~Schichten angeordnet werden können.
+
+\subsubsection{Das bitone Mergesort-Netzwerk}
+
+Ebenso wie der bitone Mischer $\operatorname{BM}(n)$ ist auch das \emph{bitone
+Mergesort-Netzwerk} $\operatorname{BS}(n)$ rekursiv definiert. Es setzt sich
+zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe,
+$\operatorname{BS}(\frac{n}{2})$, für je die Hälfte der Eingänge, sowie dem
+bitonen Mischer für $n$~Leitungen, $\operatorname{BM}(n)$. Das Rekursionsende
+ist das bitone Mergesort-Netzwerk mit nur einer Leitung,
+$\operatorname{BS}(1)$, welches als leeres Komparatornetzwerk definiert ist.
+Entsprechend sind die Komparatornetzwerke $\operatorname{BM}(2)$ und
+$\operatorname{BS}(2)$ identisch.
+
+Bei der Konstruktion kommt die trichterförmige Anordnung der Komparatoren
+(Abbildung~\ref{fig:bitonic-merge-tricheter}) gelegen, weil so die beiden
+rekursiven Sortiernetzwerke in die gleiche Richtung sortieren können und so
+alle Komparatoren in die gleiche Richtung zeigen.
-\subsubsection{Batcher's Bitonic-Mergesort-Netzwerk}
-
-Das Sortiernetzwerk $S(n)$ mit $n$~Eingängen besteht aus zwei Instanzen von
-$S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen und dem bitonen
-Mischer~$M(n)$. Die Rekursion bricht bei ${n = 1}$~ab --~eine einelementige
-Liste ist immer sortiert.
-Das konkrete Netzwerk~$S(8)$ ist in Abbildung~\ref{fig:batcher_08} zu sehen.
-Eingezeichnet sind ebenfalls die beiden Instanzen des Netzwerks~$S(4)$ (rot)
-sowie der bitone Mischer~$M(8)$ (blau).
+\begin{figure}
+ \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
+ rekursiven Schritt hinzugefügt wurden (grün).}
+ \label{fig:bitonic-08}
+\end{figure}
+Das konkrete Netzwerk~$\operatorname{BS}(8)$ ist in
+Abbildung~\ref{fig:bitonic-08} zu sehen. Eingezeichnet sind ebenfalls die
+beiden Instanzen des Netzwerks~$\operatorname{BS}(4)$ (rot) sowie der bitone
+Mischer~$\operatorname{BM}(8)$ (blau). Die trichterförmige Komparator-Kaskade,
+die die bitone Eingabefolge in zwei bitone Ausgabefolgen transformiert, ist
+grün hinterlegt.
+Das \emph{bitone Mergesort-Netzwerk} $\operatorname{BS}(8)$ besteht aus
+$\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.
%\begin{figure}
%\begin{center}
%\label{fig:bms_rekursiver_aufbau}
%\end{figure}
-\begin{figure}
- \begin{center}
- \input{images/batcher-8.tex}
- \end{center}
- \caption{$S(8)$, Batcher's {\em bitone Mergesort-Netzwerk} für acht
- Eingänge. Markiert sind die beiden Instanzen von $S(4)$ (rot), die beiden
- bitonen Mischer~$M(4)$ (blau) und die Komparatoren, die im letzten rekursiven
- Schritt hinzugefügt wurden (grün).}
- \label{fig:batcher_08}
-\end{figure}
+\subsection{Das Odd-Even-Mergesort-Netzwerk}
-\subsection{Odd-Even-Mergesort}
-
-Obwohl der Name ähnlich klingt, haben {\em Odd-Even-Mergesort} (OEM) und
-{\em Odd-Even-Transpositionsort} (OET, siehe
-Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Auch dieses
-Netzwerk ist von K.~Batcher gefunden worden und wird rekursiv durch einen
-"`Mischer"' definiert.
+Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk}
+(OES) und das \emph{Odd-Even-Transpositionsort-Netzwerk} (siehe
+Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Vielmehr ist
+OES dem \emph{bitonen Mergesort-Netzwerk}, das im vorherigen Abschnitt
+vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von
+\textit{Kenneth~E. Batcher} gefunden worden und ist ebenfalls in~\cite{B1968}
+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}
-Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte
-Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit
-weniger Vergleichen aus als der {\em bitone Mischer}, der im
-Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde, aus.
+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}
+vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even-Mischer} unter
+Umständen mehr Schichten als der \emph{bitone Mischer}.~\cite{KNUTH}
-Der {\em 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
\label{fig:oe-merge}
\end{figure}
-Diese werden jetzt in insgesamt vier sortierte Folgen aufgeteilt, je eine
-Liste der geraden Indizes und je eine Liste der ungeraden Indizes.
+Diese werden in insgesamt vier sortierte Folgen aufgeteilt, je eine Liste der
+geraden Indizes und je eine Liste der ungeraden Indizes.
\begin{eqnarray}
U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\
U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
\end{itemize}
Dass die resultierende Folge sortiert ist, lässt sich mit dem
-{\em 0-1-Prinzip} leicht zeigen:
+{\em 0-1-Prinzip} zeigen:
Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden
Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder
gleich der Anzahl der Nullen in den ungeraden Teilfolgen
Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
-wenn $W_{\textrm{gerade}}$ $2$~Nullen mehr enthählt als
-$W_{\textrm{ungerade}}$, muss eine Vertauschung stattfinden, um die Ausgabe zu
-sortieren. Die jeweiligen Situationen sind in
-Abbildung~\ref{fig:oe-post-recursive} dargestellt.
+wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthählt als
+$W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die
+Ausgabe zu sortieren. Diese wird von den Komparatoren, die benachbarte
+Leitungen miteinander vergleichen, ausgeführt. Die jeweiligen Situationen sind
+in Abbildung~\ref{fig:oe-post-recursive} dargestellt.
\begin{figure}
\centering
\label{fig:oe-post-recursive}
\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)$
+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$.
+
+Die Anzahl der Komparatoren $K(n,m)$, die $\operatorname{OEM}(n,m)$ im
+allgemeinen Fall verwendet, ist Gemäß der rekursiven Definition in
+Abhängigkeit der Länge der Eingabefolgen, $n$ und $m$:
+\begin{displaymath}
+ K(n,m) = \left\{ \begin{array}{ll}
+ nm, & \mathrm{falls} \quad nm \leqq 1 \\
+ K\left(\left\lceil \frac{n}{2} \right\rceil, \left\lceil \frac{m}{2} \right\rceil\right)
+ + K\left(\left\lfloor \frac{n}{2} \right\rfloor, \left\lfloor \frac{m}{2} \right\rfloor\right)
+ + \left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor & \mathrm{falls} \quad nm > 1
+ \end{array} \right.
+\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.
+
+Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$, lässt sich die Anzahl
+der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der erste
+Rekursionsschritt der OEM-Konstruktion fügt
+$\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$
+Komparatoren ein -- einen Komparator weniger als der \emph{bitone Mischer} in
+diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer,
+$\operatorname{OEM}(\frac{n}{2}, \frac{n}{2})$ und so weiter bis
+einschließlich $\operatorname{OEM}(2, 2)$, von denen es $2, 4, \dots,
+\frac{N}{4} = 2^{\log(N)-2}$ Instanzen gibt. Insgesamt werden
+\begin{displaymath}
+ \sum_{i=0}^{\log(N)-2} 2^i = 2^{\log(N) - 1} - 1 = \frac{N}{2} - 1 = n - 1
+\end{displaymath}
+Komparatoren eingespart. Damit ergibt sich
+\begin{displaymath}
+ K\left(n = 2^{t-1}, n = 2^{t-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
+\end{displaymath}
+für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^t)$
+benötigt werden.
+
\subsubsection{Das Odd-Even-Mergesort-Netzwerk}
-Auch beim \emph{Odd-Even-Mergesort-Netzwerk} --~wie beim \emph{bitonen
-Mergesort-Netzwerk}~-- entsteht das Sortiernetzwerk aus dem {\em
-Odd-Even-Mischer} durch rekursives Anwenden auf einen Teil der Eingabe
-(üblicherweise die Hälfte der Leitungen) und anschließendes zusammenfügen.
-Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
+Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie
+das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
+sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die
+effizientesten Sortiernetzwerke in Bezuf auf Komparator- und Schichtzahl
+entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
+$\operatorname{OES}(n)$ aus
+$\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$,
+$\operatorname{OES}\left(\left\lfloor\frac{n}{2}\right\rfloor\right)$
+und $\operatorname{OEM}\left(\left\lceil\frac{n}{2}\right\rceil,
+\left\lfloor\frac{n}{2}\right\rfloor\right)$. Die Rekursion endet mit
+$\operatorname{OES}(1)$ und $\operatorname{OES}(0)$, die als leere
+Komparatornetzwerke definiert sind.
\begin{figure}
-\begin{center}
-\input{images/oe-mergesort-8.tex}
-\end{center}
-\caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
-sind die Instanzen von $S(4)$ (rot), die beiden \emph{Odd-Even-Mischer}
-$\mathit{OEM}(4)$ für gerade und ungerade Leitungen (blau) und die im letzten
-Rekursionsschritt hinzugefügten Komparatoren zwischen benachbarten Leitungen
-(grün).}
-\label{fig:odd_even_mergesort_08}
+ \begin{center}
+ \input{images/oe-mergesort-8.tex}
+ \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
+ Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
+ Komparatoren zwischen benachbarten Leitungen (grün).}
+ \label{fig:odd-even-mergesort-08}
\end{figure}
-\begin{itemize}
-\item Odd-Even-Transpositionsort
-\item Bitonic-Mergesort
-\item Odd-Even-Mergesort
-\item Pairwise sorting-network
-\end{itemize}
+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
+die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
+die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
+Im Allgemeinen ist die Anzahl der Komparatoren, die vom
+\emph{Odd-Even-Mergesort-Netzwerk} verwendet wird, $k(n)$, direkt aus der
+Definition beziehungsweise der Konstruktionsanleitung abzulesen:
+\begin{displaymath}
+ k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
+ + k\left(\left\lfloor\frac{n}{2}\right\rfloor\right)
+ + K\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor\right)
+\end{displaymath}
+Eine geschlossene Form dieser Formel ist schon alleine deshalb schwierig, weil
+sie für $K(n,m)$ schwierig anzugeben ist. Es ist allerdings bekannt, dass
+$k(n)$ in $\mathcal{O}\left(n \left(\log (n)\right)^2\right)$ enthalten ist.
+
+Für den wichtigen Spezialfall, dass $n = 2^t$ eine Zweierpotenz ist, kann die
+Anzahl der Komparatoren wieder explizit angegeben werden. \textit{Kenneth
+Batcher} zeigt in~\cite{B1968}, dass in diesem Fall
+\begin{displaymath}
+ k(n = 2^t) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
+\end{displaymath}
+gilt.
+
+% gnuplot:
+% oem(n,m) = ((n*m) <= 1) ? (n*m) : oem(ceil(.5*n), ceil(.5*m)) + oem(floor(.5*n), floor(.5*m)) + floor(.5*(n+m-1.0))
+% oem1(n) = oem(ceil(.5*n),floor(.5*n))
+% oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)
+
+%\begin{itemize}
+%\item Pairwise sorting-network
+%\end{itemize}
+
+\newpage
\section{Transformation von Sortiernetzwerken}
+\label{sect:tranformation}
\subsection{Komprimieren}
\subsection{Zwei Netzwerke kombinieren}
-\begin{itemize}
-\item Mit dem Bitonic-Merge
-\item Mit dem Odd-Even-Merge
-\item Nach dem Pairwise sorting-network Schema.
-\end{itemize}
+Um Sortiernetzwerke als \emph{Individuen} evolutionärer Algorithmen verwenden
+zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen
+Sortiernetzwerk zusammenzufassen.
+
+Wir haben diese Technik in den vorangegangen Abschnitten bereits verwendet,
+beispielsweise um zwei \emph{bitone Mergesort-Netzwerke} mit jeweils der
+halben Leitungszahl, $\operatorname{BS}\left(\frac{n}{2}\right)$, zu einem
+einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das
+\emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ wurde auf diese Art
+und Weise rekursiv aufgebaut.
+
+Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte
+Folgen. \emph{Wie} diese Folgen sortiert wurden, ist unerheblich. Entsprechend
+können wir beliebige Sortiernetzwerke einsetzen, um die beiden Eingabefolgen
+zu sortieren, und die Ausgaben mit einem der beschriebenen Mischer
+zusammenfügen.
+
+Beispielsweise kann man die Ausgabe von zwei \emph{bitonen
+Mergesort-Netzwerken} $\operatorname{BS}(8)$ mit je acht Leitungen mit dem
+\emph{Odd-Even-Merge} $\operatorname{OEM(8,8)}$ zu einer sortierten
+Gesamtfolge zusammenfügen. Das resultierende Sortiernetzwerk besitzt
+73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
+80~Komparatoren, $\operatorname{OES}(16)$ nur 63).
+
+Verbesserungen in der Anzahl der benötigten Komparatoren beziehungsweise der
+Schichten eines „kleinen“ Sortiernetzwerks übertragen sich direkt auf das
+resultierende Gesamtnetzwerk. Das \emph{Odd-Even-Mergesort-Netzwerk}
+$\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
+\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.
+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.
+
+% 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
+Aneinanderreihung der Art „die ersten $x$~Schichten des einen, dann die
+letzten $y$~Schichten des anderen Sortiernetzwerks“ zerstören im Allgemeinen
+die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden
+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}
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
+Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung
„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
\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}}
- \caption{Eine Leitung wird aus dem {\em Odd-Even-Transpositionsort} Netzwerk
- $\textrm{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 $\textrm{OET}(7)$ markiert.}
+ \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.}
+ \label{fig:oe-transposition-cut}
\end{figure}
Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
Ausgabe und kann entfernt werden.
+\subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
+\label{sect:anzahl_schnittmuster}
+
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.
+$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
+nacheinander angewendet ein $n$-Sortiernetzwerk auf ein
+${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als
+\emph{$k$-Schnittmuster}.
+
+Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
+auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
+Schnittmuster \emph{unterschiedlich} bezüglich~$S$.
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!}
+ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
+ergeben sich insgesamt
+\begin{equation}\label{eqn:anzahl_schnittmuster}
+ \prod_{i=n}^{1+n-k} 2i = 2^k \frac{n!}{(n-k)!}
\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:
+\end{equation}
+\emph{mögliche} Schnittmuster. Diese Schnittmuster 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 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^{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)
+ 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
+ = 2^{k} \cdot \frac{n!}{k! (n-k)!}
+ = 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!}
+ \quad (1 \leqq k < n)
\end{displaymath}
-Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden
+Die Anzahl der möglichen Schnittmuster 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.
+ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schmittmuster mit
+16~Schnitten notwendig, für das 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.
+
+Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
+als die Anzahl der möglichen Schnittmuster. Für jeden Komparator auf der
+ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
+Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
+unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
+der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die
+Werte unterscheiden.
+
+Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe
+Ausgangmuster abgebildet, weil die Position des Minimums beziehungsweise des
+Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun
+unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster
+erzeugen. In der zweiten und allen folgenden Schichten kann man diesen
+Unterschied nicht mehr erkennen. In allen sechs Fällen, in denen sich die
+Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass
+sich die Resultate auch in der ersten Schicht nicht unterscheiden.
-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}. Mit diesem
-Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
-gute Schnittmuster gesucht.
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 360 216,width=15cm]{images/count-cuts-16.pdf}
+ \end{center}
+ \caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch
+ 8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
+ $\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}.}
+ \label{fig:count-cuts-16}
+\end{figure}
-In ihrer Arbeit “Improving Bitonic Sorting by Wire Elimination” zeigen Moritz
-Mühlenthaler und Rolf Wanka, wie man einen bitonen Mischer, der nach Batchers
-Methode konstruiert wurde, durch systematisches Entfernen von Leitungen in
-einen ebenfalls bitonen Mischer mit der Hälfte der Leitungen transformiert.
-Diese alternativen Mischer sparen im Vergleich zu den Mischern, die nach
-Batchers Methode konstruiert werden, Komparatoren ein.
+Alleine durch Betrachten der ersten Schicht von Komparatoren konnte die Anzahl
+der \emph{unterschiedlichen} Schnittmuster auf höchstens $\frac{2}{3}$ der
+\emph{möglichen} Schnittmuster reduziert werden. Um die Anzahl der
+\emph{unterschiedlichen} Schnittmuster experimentell zu ermitteln, wurden je
+eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke
+$\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$
+angewandt. Anschließend wurde mithilfe einer Hashtabelle überprüft, ob das
+resultierende Sortiernetzwerk schon von einem \emph{äquivalenten}
+Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk noch nicht in der
+Hashtabelle enthalten war, wurde der Zähler für unterschiedliche Schnittmuster
+erhöht und das Sortiernetzwerk eingefügt.
+
+Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
+\emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen
+Schnittmuster auf. Klar zu sehen ist, dass sich die Anzahl der erzeugten
+Sortiernetzwerke nach $500.000$~Iterationen nur noch gering verändert und der
+Wert nach $1.000.000$~Iterationen allem Anschein nach dem Endwert schon sehr
+nahe ist.
+
+Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der
+Formel~\ref{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 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
+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 benötigt mehr Arbeitsspeicher 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
+\emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von
+$k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
+zufällig erzeugt und überprüft, ob sie sich in der Menge~$S$ enthalten sind.
+Unter der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in
+$S$ enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der
+unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der
+unterschiedlichen Schnittmuster abschätzen.
-Beispeilsweise geben Mühlenthaler und Wanka ein Sortiernetzwerk mit
-16~Eingängen an, das mithilfe der alternativen Mischer konstruiert wurde.
-Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger als das
-bitone Mergesort-Netzwerk nach Batchers Methode.
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
+ \end{center}
+ \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der
+ \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und
+ $\operatorname{BS}(32)$.}
+ \label{fig:collisions-10000-1000000-32}
+\end{figure}
-Startet man {\sc SN-Evolution-Cut} mit dem bitonen Mergesort-Netzwerk
-$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
-Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
-16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in
-Abbildung~\ref{fig:16-ec-1277186619} zu sehen.
+In Abbildung~\ref{fig:collisions-10000-1000000-32} ist das Ergebnis des
+Monte-Carlo-Algorithmus für 16-Schnittmuster zu sehen, die auf
+$\operatorname{OES}(32)$ und $\operatorname{BS}(32)$ angewandt wurden: Von
+jedem Sortiernetzwerk wurden zunächst eine Menge~$S$ von 10.000
+\emph{unterschiedlichen} Schnittmustern erzeugt. Anschließend wurden 1.000.000
+zufällige Schnittmuster erzeugt und der Anteil der zufälligen Schnittmuster,
+die \emph{äquivalent} zu einem in~$S$ enthalten Schnittmuster sind, berechnet.
+Für $\operatorname{OES}(32)$ war dieser Anteil etwa $0,19 \%$, für
+$\operatorname{BS}(32)$ etwa $0,29 \%$. Das ergibt eine Abschätzung von $5,2
+\cdot 10^6$ unterschiedlichen Schnittmustern für $\operatorname{OES}(32)$ und
+$3,4 \cdot 10^6$ für $\operatorname{BS}(32)$.
-\begin{itemize}
- \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?
- \item Abschnitt „Optimierung der Schnitte“ hier einbauen.
-\end{itemize}
+\begin{figure}
+ \begin{center}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf}
+ \end{center}
+ \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der
+ \emph{Monte-Carlo-Methode} für $\operatorname{PS}(32)$. 385 von 1.000.000
+ zufälligen Schnittmustern waren äquivalent zu einem Schnittmuster in einer
+ Menge von 100.000. Daraus ergibt sich eine Schätzung von $2,6 \cdot 10^8$
+ unterschiedlichen Schnittmustern.}
+ \label{fig:collisions-100000-1000000-32-ps}
+\end{figure}
+
+Im vorherigen Abschnitt wurde das \emph{Pairwise-Sorting-Netzwerk}
+$\operatorname{PS}(32)$ nicht betrachtet, da es für dieses Netzwerk viel mehr
+unterschiedliche 16-Schnittmuster gibt als für $\operatorname{OES}(32)$ und
+$\operatorname{BS}(32)$. In Anbetracht der Tatsache, dass die Anzahl der
+unterschiedlichen 8-Schnittmuster für $\operatorname{PS}(16)$ in
+Abbildung~\ref{fig:count-cuts-16} bereits mehr als dreimal größer war als die
+Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$,
+ist dieser Umstand wenig verwunderlich. In einem kombinierten Graphen hätte
+man keine Details mehr erkennen können. Aufgrund der hohen Anzahl
+unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit
+$\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedilchen
+Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
+Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent
+sind. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$
+unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den
+vorherigen Sortiernetzwerken, aber immernoch fünf Zehnerpotenzen kleiner als
+die Anzahl der \emph{möglichen} Schnittmuster.
-\section{Der evolutionäre Ansatz}
+\newpage
+\section{Der \textsc{SN-Evolution}-Algorithmus}
-Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
-die vorgestellten Methoden kombiniert.
+Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
+Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
+(Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
+(Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
+Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
+in Abschnitt~\ref{sect:bewertung} behandelt.
\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,
-die interessant sind:
+die bei Sortiernetzwerken verfolgt werden können:
\begin{itemize}
- \item Möglichst wenige Komparatoren ("`klein"')
- \item Möglichst wenige Schichten ("`schnell"')
+ \item Möglichst wenige Komparatoren („billig“)
+ \item Möglichst wenige Schichten („schnell“)
\end{itemize}
Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
-kleinste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
+billigste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
9~Schichten.
-Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
+Eine Gütefunktion, die die beiden Ziele "`billig"' und "`schnell"'
berücksichtigen kann, hat die folgende allgemeine Form:
\begin{equation}
- \mathit{Guete}(S) = w_{\mathrm{Basis}}
+ \operatorname{Guete}(S) = w_{\mathrm{Basis}}
+ w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
+ w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
\end{equation}
dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
-jegliche Ergebnisse sind dann rein zufälliger Natur.
+jegliche Ergebnisse sind dann rein zufälliger Natur.\footnote{Dass dies nicht
+so schlecht ist wie man intuitiv vermuten könnte, zeigt der
+\textsc{SN-Markov}-Algorithmus in Abschnitt~\ref{sect:markov}.}
+
+Da möglichst billige und schnelle Sortiernetzwerke gefunden werden sollen, ist
+ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert. Das
+heißt, dass das Ziel von \textsc{SN-Evolution} ist, $\operatorname{Guete}(S)$
+zu \emph{minimieren}.
Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
genommen werden. Ist er groß, wird der relative Unterschied der Güten
verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
-klein, in Abhängigkeit von den anderen beiden Parametern sind auch negative
-Werte möglich, werden die relativen Unterschiede groß. Dadurch wird die {\em
-Exploitation}, das Finden lokaler Optima, bevorzugt.
+klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
+Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
+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
+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
+Leitungszahlen und Mischer-Typen experimentiert werden muss.
\subsection{Selektion}
-...
+Die \emph{Selektion} sorgt dafür, dass bessere Individuen eine größere
+Wahrscheinlichkeit haben, zur nächsten Generation beizutragen. Diese
+Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für das
+Streben des Algorithmus nach besseren Lösungen.
+
+Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint,
+ist es sehr häufig, dass die \emph{Exploitation} überhand gewinnt und der
+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}
+Guetesumme := 0
+Auswahl := (leer)
+
+fuer jedes Individuum in Population
+{
+ reziproke Guete := 1.0 / Guete(Individuum)
+ Wahrscheinlichkeit P := reziproke Guete / (reziproke Guete + Guetesumme)
+ Guetesumme := Guetesumme + reziproke Guete
+
+ mit Wahrscheinlichkeit P
+ {
+ Auswahl := Individuum
+ }
+}
+gebe Auswahl zurueck
+\end{verbatim}
\subsection{Rekombination}
\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.
+\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
\end{itemize}
-\section{Markov-Kette}
+%\input{shmoo-aequivalenz.tex}
+
+\newpage
+\section{Der \textsc{SN-Evolution-Cut}-Algorithmus}
+\label{sect:sn-evolution-cut}
+
+Das Programm \textsc{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}. Mit diesem
+Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
+gute Schnittmuster gesucht.
+
+Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster}
+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
+Schnitt-Richtung.
+
+\subsection{Versuche mit dem bitonen Mergesort-Netzwerk}
+
+In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka},
+wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
+durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen
+Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer
+sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert
+werden, Komparatoren ein.
+
+Beispeilsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
+Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
+konstruiert wurde. Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger
+als das bitone Mergesort-Netzwerk nach Batchers Methode. Gegenüber Batchers
+Methode sparen so konstruierte Sortiernetzwerke ${\frac{1}{4}n(\log n - 1)}$
+Komparatoren ein.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-bs32.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort-Netzwerk}
+ $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
+ \label{fig:16-ec-from-bs32}
+\end{figure}
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-bs32-normalized.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
+ $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
+ \label{fig:16-ec-from-bs32-normalized}
+\end{figure}
-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.
+Startet man {\sc SN-Evolution-Cut} mit dem bitonen Mergesort-Netzwerk
+$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
+Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
+16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den
+Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized}
+zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$
+und das
+${\operatorname{MIN}(0,5,9,11,15,17,20,22,26,29,30)}$-${\operatorname{MAX}(2,4,13,19,24)}$-Schnittmuster,
+das durch \textsc{SN-Evolution-Cut} gefunden wurde.
+Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk
+nachdem das Schnittmuster angewandt und das Netzwerk normalisiert wurde. Eine
+Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist in
+diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten des
+Netzwerks scheinen rein zufällig zu sein.
+
+\begin{figure}
+ % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX
+ % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX
+ % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX
+ % 63:MAX
+ \begin{center}
+ \input{images/32-ec-from-bs64.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in
+ 15~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
+ $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige
+ Schnittmuster ist
+ $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$,
+ $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37,
+ 40, 43, 47, 48, 49, 55, 56, 60, 63)$.}
+ \label{fig:32-ec-from-bs64}
+\end{figure}
+
+Das Ergebnis von \textit{Mühlenthaler} von \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
+Größen, beispielsweise wenn man $\operatorname{BS}(64)$ auf ein
+32-Sortiernetzwerk reduziert, kann das Ergebnis sogar noch übertroffen werden,
+wie in Abbildung~\ref{fig:32-ec-from-bs64} zu sehen: Ein nach Batchers Methode
+konstruiertes Sortiernetzwerk benötigt 240~Komparatoren, ein aus den
+optimierten Mischern aufgebautes Netzwerk verbessert die Kosten auf
+208~Komparatoren. Das in Abbildung~\ref{fig:32-ec-from-bs64} dargestellte
+Sortiernetzwerk benötigt lediglich 206~Komparatoren. Die Komparatoren aller
+dieser Netzwerke können in 15~Schichten angeordnet werden, so dass die
+Verzögerung dieser Sortiernetzwerke gleich ist.
+
+Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
+unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
+gute Schnittmuster anzugeben.
+
+Entscheidend für das Ergebnis eines Schnittmusters scheint beim bitonen
+Mergesort-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
+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
+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.
+
+Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur
+haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere
+von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
+\emph{Odd-Even-Transpositionsort-Netzwerk} $\operatorname{OET}(n)$ und
+$m$~Schnitten gestartet, so ist das beste Ergebnis immer das
+$\operatorname{OET}(n-m)$-Netzwerk.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-ps32.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk}
+ $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.}
+ \label{fig:16-ec-from-ps32}
+\end{figure}
+
+\subsection{Versuche mit dem Pairwise-Sorting-Netzwerk}
+
+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,
+16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, dass die gleiche
+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.
+
+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
+den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzerke, die
+strukturell identisch zu $\operatorname{PS}(8)$ sind -- lediglich die
+Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
+
+\begin{displaymath}
+\textit{Eingang}_i = \left\{ \begin{array}{rl}
+ -\infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{0, 6\} \\
+ \infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{2, 4\} \\
+ ? & \quad \mathrm{sonst}
+ \end{array} \right.
+\end{displaymath}
+
+\begin{figure}
+ \begin{center}
+ \input{images/32-pairwise-cut-16-pairwise.tex}
+ \end{center}
+ \caption{PS(32) mit 16 Schnitten zu PS(16).}
+ \label{fig:ps16-from-ps32}
+\end{figure}
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-pairwise.tex}
+ \end{center}
+ \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten
+ ($\operatorname{MIN}(0,2,4,6), \operatorname{MAX}(9,11,13,15)$). Das
+ resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.}
+ \label{fig:16-pairwise}
+\end{figure}
+
+Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann
+man $\operatorname{OES}(8)$ erhalten.
+
+\subsection{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
+
+\todo{Schreibe noch etwas zum Odd-Even-Mergesort-Netzwerk.}
+
+\begin{itemize}
+ \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? Oder andersrum: Wieviele
+ unterschiedliche Netzwerke kann ich erhalten? Wieviele Nachfolger hat ein
+ Netzwerk / Knoten in der Markov-Kette?
+ \item Abschnitt „Optimierung der Schnitte“ hier einbauen.
+\end{itemize}
+
+\newpage
+\section{Der \textsc{SN-Markov}-Algorithmus}
+\label{sect:markov}
+
+Der evolutionäre \textsc{SN-Evolution}-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
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
+(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
+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.
+Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben ist die Anzahl
+(unterschiedlicher) Schnittmuster und damit die Anzahl der Nachfolger sehr
+groß. Wenn $S_0$ ein Sortiernetzwerk mit $n$~Leitungen ist, so hat $S_0$ bis
+zu
+\begin{displaymath}
+ 2^n \cdot \left( \begin{array}{c} 2n \\ n \end{array} \right)
+\end{displaymath}
+Nachfolger.
+
+Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen
+zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem
+gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu
+gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich
+selbst und erhält so einen zufälligen Nachfolger.
\begin{itemize}
\item $n \leftarrow \mathrm{Input}$
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16.pdf}
+ \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf}
\end{center}
- \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden.}
- \label{fig:markov-comparators-16}
+ \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}
-%\input{shmoo-aequivalenz.tex}
-
-\section{Optimierung der Schnitte}
-
-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.
-
-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$.}
-
-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$.
-
-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-ec-1277186619.tex}
-\end{center}
-\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}
+ \begin{center}
+ \includegraphics[viewport=0 0 360 216,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}
-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/32-ec-1277190372.tex}
-\end{center}
-\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}
+ \begin{center}
+ \includegraphics[viewport=0 0 360 216,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}
-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
-
+\newpage
\section{Empirische Beobachtungen}
\begin{itemize}
\item $\ldots$
\end{itemize}
+\newpage
\section{Ausblick}
Das würde mir noch einfallen$\ldots$
-%\bibliography{references}
-%\bibliographystyle{plain}
+\newpage
+\section{Implementierung}
+
+So habe ich die ganzen Versuche durchgeführt.
+
+\newpage
+\bibliography{references}
+\bibliographystyle{plain}
%\listoffigures
projects / diplomarbeit.git / blobdiff