\maketitle
\begin{abstract}
+\todo{Einleitung schreiben.}
+
Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
vorgestellt (Odd-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
\subsection{Motivation}\label{sect:motivation}
-\todo{Schreibe noch etwas zu …}
-\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}
+\emph{Sortiernetzwerke} sind ein theoretisches Konstrukt, dass auch von
+Personen ohne Zugang zum Thema beziehungsweise der theoretischen Informatik
+schnell verstanden werden kann. Eine Einführung wird in
+Abschnitt~\ref{sect:einleitung_sortiernetzwerke} gegeben. Nichtsdestotrotz ist
+das Finden von Sortiernetzwerken sowie das Beweisen, dass ein
+Komparatornetzwerk jede beliegibe Eingabe sortiert, im Allgemeinen sehr
+schwierig und nach heutigem Kenntnisstand nur mit exponentiellem Aufwand zu
+bewältigen.
+
+Einfacher ist der Korrektheitsbeweis bei konstruktiven Verfahren, da hier die
+Konstruktionsvorschrift genutzt werden kann um die Korrektheit für beliebige
+Eingabegrößen zu beweisen. Im Abschnitt~\ref{sect:konstruktive_netzwerke}
+geschieht dies beispielsweise für zwei von \emph{Kenneth~E. Batcher} 1968
+gefundenen Konstruktionsvorschriften.
+
+Um effiziente und schnelle Sortiernetzwerke zu finden, wurden schon früh
+Computer und automatische Suchverfahren eingesetzt. Bisherige Ansätze
+versuchen meist, in der Menge aller Komparatornetzwerke jene zu finden, die
+die Sortiereigenschaft besitzen und aus wenigen Komparatoren bestehen. Die
+Eigenschaft, jede Eingabepermutation zu sortieren, ist also ein
+Optimierungsziel und nicht durch das Vorgehen gewährleistet. Dafür können
+theoretisch alle Sortiernetzwerke durch diese Algorithmen gefunden werden --
+genügend Laufzeit vorausgesetzt.
+
+In dieser Arbeit werden Methoden verwendet, die die Menge der Sortiernetzwerke
+nie verlassen, dafür aber auch nicht alle existierenden Sortiernetzwerke
+erzeugen können. So muss für ein gefundenes Komparatornetzwerk nicht mehr
+nachgewiesen werden, dass es jede beliebige Eingabe sortiert, weil diese
+Eigenschaft durch das Verfahren sichergestellt ist.
\subsection{Einleitung}\label{sect:einleitung}
\label{fig:13-juille}
\end{figure}
\textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving
-Non-Determinism} (END) nannte. Dabei handelt es sich nicht um einen
-\emph{Evolutionären Algorithmus}, wie sie hier vorgestellt wurden, sondern um
-eine verteilte, probabilistische Breitensuche, die an die \emph{Strahlsuche}
-(englisch: \textit{beam search}), ein Verfahren der Künstlichen Intelligenz,
-angelehnt ist. Die aufwendigste Operation bei diesem Ansatz ist die
-Bewertungsfunktion, die abschätzt, wieviele Komparatoren zu einem
-Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu
+Non-Determinism} (END) nannte~\cite{J1995}. Dabei handelt es sich nicht um
+einen \emph{Evolutionären Algorithmus}, wie sie hier vorgestellt wurden,
+sondern um eine verteilte, probabilistische Breitensuche, die an die
+\emph{Strahlsuche} (englisch: \textit{beam search}), ein Verfahren der
+Künstlichen Intelligenz, angelehnt ist. Die aufwendigste Operation bei diesem
+Ansatz ist die Bewertungsfunktion, die abschätzt, wieviele Komparatoren zu
+einem Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu
erhalten. Mit diesem Ansatz gelang es \textit{Juillé} zwei 13-Sortiernetzwerke
anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin
Bekannten (Abbildung~\ref{fig:13-juille}).
Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte: Der Algorithmus
wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als triviale
Initiallösung gestartet. Das Ergebnis ist ein Netzwerk, das effizienter ist
-als das bitone Mergesort-Netzwerk: $\operatorname{BS}(16)$ benötigt
-80~Komparatoren, das Sortiernetzwerk in
-Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67.
+als das \emph{bitone Mergesort}-Netzwerk: \bs{16} benötigt 80~Komparatoren,
+das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt
+lediglich~67.
\subsection{Versuche mit dem \emph{Odd-Even}-Mischer}
\subsection{Versuche mit dem bitonen Mergesort-Netzwerk}
-In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka},
+\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
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
Beispielsweise 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.
+als das \emph{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}
projects / diplomarbeit.git / blobdiff