Evolutionäre Algorithmen: Etwas zur Mutation geschrieben.

[diplomarbeit.git] / diplomarbeit.tex

\documentclass[a4paper,11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{ngerman}
\usepackage{fancyhdr}
\usepackage{geometry}
\usepackage{amsmath, bbm}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{url}
%\usepackage{longtable}
\usepackage{subfigure}
\usepackage{icomma}

\usepackage{tikz}
\usetikzlibrary{arrows,shapes}

% Fuer mathtoolsset
\usepackage{mathtools}

\geometry{paper=a4paper,margin=30mm}

\pagestyle{fancy}
%\fancyhf{}
%\fancyhead[LO,LE]{"Ubung zu Computational Intelligence}
%\fancyhead[CO,CE]{2006-05-15}
%\fancyhead[RO,RE]{Florian Forster (2099894)}

\title{Evolutionäre Optimierung von Sortiernetzwerken}
\author{Florian Forster}
\date{\today}

\newcommand{\false}{\textsc{False}}
\newcommand{\true}{\textsc{True}}
\newcommand{\todo}[1]{{\bf TODO:} #1}
\newcommand{\qed}{\hfill $\Box$ \par \bigskip}

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

% Zeige Nummern nur bei referenzierten Gleichungen an.
\mathtoolsset{showonlyrefs=true}

\begin{document}

\tikzstyle{vertex}   = [circle,draw,thick,fill=black,minimum size=5,inner sep=0pt]
\tikzstyle{comp}     = [draw,thick,-]
\tikzstyle{compup}   = [draw,thick,->]
\tikzstyle{compdown} = [draw,thick,<-]
\tikzstyle{edge}     = [draw,thick,-]
\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]
\tikzstyle{gray box}  = [draw,-,color=black, top color=black!2,bottom color=black!10]

\maketitle
\begin{abstract}
Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
vorgestellt (Off-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
Evolutionäre Algorithmen werden beschrieben und ein evolutionärer
Algorithmus für die Optimierung von Sortiernetzwerken wird angegeben.
Die mindestens von diesem Algorithmus erreichte Güte wird angegeben und die
Transformation zu einer Markov-Kette wird gezeigt. {\em Natürlich: So fern ich
das hinbekomme bzw. Recht behalte.}
\end{abstract}
\newpage

\tableofcontents

\newpage
\section{Motivation und Einleitung}

\subsection{Motivation}\label{sect:motivation}

\begin{itemize}
\item Sortiernetzwerke sind toll, weil $\ldots$
\item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
\item Bisher noch kein evolutionärer Algorithmus zur automatischen
  Optimierung von Sortiernetzwerken bekannt. \textit{(Glaube ich zumindest.)}
\end{itemize}

\subsection{Einleitung}\label{sect:einleitung}

\subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke}

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

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}
\begin{center}
\input{images/einfaches_komparatornetzwerk.tex}
\end{center}
\caption{Einfaches Komparatornetzwerk mit vier Ein- bzw. Ausgängen, bestehend
aus 5~Komparatoren.}
\label{fig:einfaches_komparatornetzwerk}
\end{figure}

Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
\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.

Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
gleichzeitig angewandt werden. Das Beispiel in
Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
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 \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.

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

Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
$NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte
sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$
liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese
Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese
Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer
Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit
praktikablen Zeitkonstanten gefunden werden.

Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus
zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser
Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
beispielsweise immitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.

Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
ist es, bestehende Lösungen zu neuen, unter Umständen besseren Lösungen zu
kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem häufig
als {\em Individuum} bezeichnet.

Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen
ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
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 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. 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{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
${n = 8}$ Leitungen.

\begin{figure}
  \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}

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

\begin{figure}
  \centering
  \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}}
  \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}}
  \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}}
  \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}}
  \caption{Beispiele bitoner Folgen.}
  \label{fig:beispiel-biton}
\end{figure}

\begin{figure}
  \centering
  \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
  \qquad
  \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
  \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
  aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
  der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
  resultierenden Teilfolgen sind wiederum biton.}
  \label{fig:bitonic-merge-schema}
\end{figure}

Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und
$V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend
sortiert, die Folge $V$ sei absteigend sortiert:
\begin{eqnarray}
 u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
 v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
\end{eqnarray}
Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen
Positionen verglichen und ggf. vertauscht:
\begin{equation}
u_i \longleftrightarrow v_i, \quad 0 \leqq i < m
\end{equation}
Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die
durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass
Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$
gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1}
> 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 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.

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

\subsection{Das Odd-Even-Mergesort-Netzwerk}

Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk}
(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 \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 \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
$W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
\begin{equation}
w_i = \left\{ \begin{array}{ll}
        u_i,     & i < n \\
        v_{i-n}, & i \geqq n
      \end{array} \right.,
      \quad 0 \leqq i < N
\end{equation}

\begin{figure}
  \begin{center}
  \input{images/oe-merge.tex}
  \end{center}
  \caption{Schematischer Aufbau des {\em Odd-Even} Mischers. Im Vergleich zum
  bitonen Mischer für Acht kommt dieses Schema mit einem Komparator weniger
  aus. Der Effekt wird duch den rekursiven Aufbau noch verstärkt.}
  \label{fig:oe-merge}
\end{figure}

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) \\
  V_{\textrm{gerade}}   &=& \left(v_0, v_2, u_4, \ldots\right) \\
  V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
\end{eqnarray}

Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die
ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden
rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am
Ausgang der Mischer die Folgen
\begin{eqnarray}
  W_{\textrm{gerade}}   &=& \left(w_0, w_2, w_4, \ldots\right) \\
  W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
\end{eqnarray}
ergeben.

Anschließend werden die Komparatoren zwischen benachbarten Leitungen
hinzugefügt,
\begin{equation}
  w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
\end{equation}
die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em
Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}.

Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
Aufbau lauten:
\begin{itemize}
  \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
  \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
  einzelnen Komparator.
\end{itemize}

Dass die resultierende Folge sortiert ist, lässt sich mit dem
{\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
$U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ --~die Einsen verhalten
sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen
$W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu:
\begin{eqnarray}
  \left|W_{\textrm{gerade}}\right|_0
  &=& \left|U_{\textrm{gerade}}\right|_0
    + \left|V_{\textrm{gerade}}\right|_0
   =  \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
   +  \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
  \left|W_{\textrm{ungerade}}\right|_0
  &=& \left|U_{\textrm{ungerade}}\right|_0
    + \left|V_{\textrm{ungerade}}\right|_0
   =  \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
   +  \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
\end{eqnarray}
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}}$ 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
  \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
  \qquad
  \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
  \qquad
  \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
  \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
  kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der
  Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
  letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
  sortiert ist.}
  \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}

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

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}

\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. Statt dem typischen "`Treppenmuster"' sind abwechselnd das Treppen-
und das Trichtermuster zu sehen.

\subsection{Zwei Netzwerke kombinieren}

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}

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
„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}.

\begin{figure}
  \centering
  \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
  \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
  \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
  \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
  \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.
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
Darstellung ergibt. Ausserdem ist das
{\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der
zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
Ausgabe und kann entfernt werden.

\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 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 ${(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{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^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 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, 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.

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

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.

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

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

\newpage
\section{Der \textsc{SN-Evolution}-Algorithmus}

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 bei Sortiernetzwerken verfolgt werden können:
\begin{itemize}
  \item Möglichst wenige Komparatoren („billig“)
  \item Möglichst wenige Schichten („schnell“)
\end{itemize}

Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
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 "`billig"' und "`schnell"'
berücksichtigen kann, hat die folgende allgemeine Form:
\begin{equation}
  \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}
Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
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.\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.

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}

Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
{\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
Anschließend entfernen wir zufällig $n$~Leitungen wie in
Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.

Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
erhält.

\subsection{Mutation}

Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine Mutation
--~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
Sortiernetzwerk zufällig zu verändern aber trotzdem die Sortiereigenschaft zu
erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
Eigenschaft zerstören.

Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
Ausprobieren aller $2^n$~Bitmuster.

Um das Potenzial einer Mutation abzuschätzen habe ich in den evolutionären
Algorithmus eine Überprüfung eingebaut. Unmittelbar vor dem Einfügen in die
Population überprüft das Programm die Notwendigkeit jedes einzelnen
Komparators. Dazu wurde nacheinander jeder Komparator entfernt und überprüft,
ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt.

\begin{itemize}
\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
Schichten, kobiniert)
\item Rekombination: Merge Anhängen und Leitungen entfernen.
\end{itemize}

Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt
Abbildung~\ref{fig:evolutionary_08}.

\begin{figure}
\begin{center}
\input{images/evolutionary-08.tex}
\end{center}
\caption{Ein mit dem evolutionären Algorithmus erzeugtes Sortiernetzwerk mit
acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
\label{fig:evolutionary_08}
\end{figure}

\begin{figure}
\begin{center}
\input{images/08-e2-1237993371.tex}
\end{center}
\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
\label{fig:08-e2-1237993371}
\end{figure}

\begin{figure}
\begin{center}
\input{images/09-e2-1237997073.tex}
\end{center}
\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
\label{fig:09-e2-1237997073}
\end{figure}

\begin{figure}
\begin{center}
\input{images/09-e2-1237999719.tex}
\end{center}
\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten}
\label{fig:09-e2-1237999719}
\end{figure}

\begin{figure}
\begin{center}
\input{images/10-e2-1239014566.tex}
\end{center}
\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
\label{fig:10-e2-1239014566}
\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.
\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
\end{itemize}

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

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

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}$
  \item \texttt{while} \textit{true}
  \begin{itemize}
    \item $n \leftarrow \operatorname{recombine} (n, n)$
  \end{itemize}
\end{itemize}

\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}
  \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf}
  \end{center}
  \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen),
  die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
  \emph{Gamma-Verteilung} $f(x - 40)$ mit $k = 8,267$ und $\theta = 0,962$.}
  \label{fig:markov-comparators-12}
\end{figure}

\begin{figure}
  \begin{center}
  \includegraphics[viewport=0 0 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}

\begin{figure}
  \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}

\newpage
\section{Empirische Beobachtungen}

\begin{itemize}
\item So schnell konvergiert der Algorithmus.
\item $\ldots$
\end{itemize}

\newpage
\section{Ausblick}

Das würde mir noch einfallen$\ldots$

\newpage
\section{Implementierung}

So habe ich die ganzen Versuche durchgeführt.

\newpage
\bibliography{references}
\bibliographystyle{plain}

%\listoffigures

\end{document}

% vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 :