\usepackage{listings}
\usepackage{graphicx}
\usepackage{url}
+\usepackage[table]{xcolor}
%\usepackage{longtable}
\usepackage{subfigure}
\usepackage{icomma}
\newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}}
\newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}}
+\newcommand{\gcell}{\cellcolor{green!10}}
+\newcommand{\Gcell}{\cellcolor{green!10!white!95!black}}
+
\newtheorem{definition}{Definition}
\newtheorem{satz}{Satz}
bewegten sich in der Regel in der Menge aller Komparatornetzwerke und suchten
dort nach Sortiernetzwerken. Nach dem Vorstellen der zwei Algorithmen
\textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} sowie einiger Ergebnisse,
-die diese Algorithmen erzielen konnten, wird -- basierend auf dem
+die mit diesen Algorithmen erzielt werden konnten, wird -- basierend auf dem
evolutionären Algorithmus \textsc{SN-Evolution} -- eine Markov-Kette für
Sortiernetzwerke angegeben.
\end{abstract}
\subsection{Motivation}\label{sect:motivation}
\emph{Sortiernetzwerke} sind ein theoretisches Konstrukt, dass auch von
-Personen ohne Zugang zum Thema beziehungsweise der theoretischen Informatik
+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
Um effiziente und schnelle Sortiernetzwerke zu finden, wurden schon wiederholt
Computer und automatische Suchverfahren eingesetzt. Bisherige Ansätze
-versuchen meist, in der Menge aller Komparatornetzwerke jene zu finden, die
+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
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
+der beiden Zahlen immer auf dem einen, die kleinere der beiden Zahlen
immer auf dem anderen Ausgang ausgegeben wird.
-Kombiniert man mehrere \emph{Komparatoren} miteinander, das heißt, dass die
+Kombiniert man mehrere \emph{Komparatoren} in der Form miteinander, dass die
Ausgänge eines Komparators mit Eingängen weiterer Komparatoren verbunden sind,
erhält man ein {\em Komparatornetzwerk}.
\begin{center}
\input{images/einfaches_komparatornetzwerk.tex}
\end{center}
-\caption{Einfaches Komparatornetzwerk mit vier Ein- bzw. Ausgängen, bestehend
+\caption{Einfaches Komparatornetzwerk mit vier Ein- beziehungsweise Ausgängen, bestehend
aus 5~Komparatoren.}
\label{fig:einfaches_komparatornetzwerk}
\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
+ü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
1 & e_j > a_i
\end{array} \right.
\end{displaymath}
-auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme vom
+auf eine 0-1-Folge abgebildet werden, die entsprechend der Annahme vom
Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das
Verhalten jedes einzelnen Komparators nicht: Wenn bei der Permutation eine
Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen
Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
-$\mathcal{NP}$. Das heißt, dass keine Verfahren bekannt sind, diese Probleme
-effizient exakt lösen. Sollte sich herausstellen, dass diese Probleme nicht
-in der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine Konsequenz, dass es
-effiziente exakte Algorithmen für diese Probleme nicht gibt. Falls sich
-hingegen herausstellt, dass diese Probleme in der
-Komplexitätsklasse~\textit{P} liegen, gibt es effiziente Algorithmen. Es ist
-jedoch wahrscheinlich, dass die Zeitkonstanten solcher Algorithmen sehr groß
-sein würden, so dass der praktische Nutzen fraglich bleibt.
+$\mathcal{NP}$. Das heißt, dass keine Verfahren bekannt sind, die diese
+Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese Probleme
+außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine Konsequenz,
+dass es effiziente exakte Algorithmen für diese Probleme nicht gibt. Falls
+sich hingegen herausstellt, dass diese Probleme neben $\mathcal{NP}$ auch in
+der Komplexitätsklasse~\textit{P} liegen, gibt es effiziente Algorithmen. Es
+ist jedoch wahrscheinlich, dass die Zeitkonstanten solcher Algorithmen sehr
+groß sein würden, so dass der praktische Nutzen fraglich bleibt.
Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
-die beziehungsweise 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 imitieren 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
+die \emph{optimale Lösung}, beziehungsweise eine der \emph{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 imitieren 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, bekannte 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 als {\em
Individuen} bezeichnet.
-Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
+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
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
+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
+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
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“ aus lokalen Optima und finden noch besserer Lösungen.
+Die Erforschung (\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“ aus lokalen Optima 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 zer\-stö\-ren kann.
-Beim Suchen möglichst effizienter Netzwerke ist natürlich das zufällige
-Entfernen von Komparatoren interessanter, was die Sortiereigenschaft fast
-immer aufhebt.
+Beim Suchen möglichst effizienter Netzwerke ist das zufällige Entfernen von
+Komparatoren interessanter, was die Sortiereigenschaft fast immer 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 erhalten. Transformationen von Sortiernetzwerken werden in
-Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der Mutation
-einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
-
-\begin{figure}
- \begin{center}
- \input{images/16-hillis.tex}
- \end{center}
- \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1992} angibt.
- Es besteht aus 61~Komparatoren in 11~Schichten.}
- \label{fig:16-hillis}
-\end{figure}
-Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
+die \emph{Sortiernetzwerke} selbst, sondern verzichten entweder ganz auf
+Mutation oder mutieren lediglich Transformationen von Sortiernetzwerken, die
+die Sortiereigenschaft erhalten. Transformationen von Sortiernetzwerken werden
+in Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der
+Mutation einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
+
+\begin{figure} \begin{center} \input{images/16-hillis.tex} \end{center}
+\caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1990} angibt.
+Es besteht aus 61~Komparatoren in 11~Schichten.} \label{fig:16-hillis}
+\end{figure} Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete
\emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“
-zu optimieren~\cite{H1992}. Diese \emph{Parasiten} genannten Eingaben wurden
+zu optimieren~\cite{H1990}. Diese \emph{Parasiten} genannten Eingaben wurden
daran gemessen, bei wie vielen Komparatornetzwerken sie beweisen konnten, dass
-sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen~/
-Komparatornetzwerken nicht alle 0-1-Folgen, sondern nur erfolgreiche
-Parasiten~/ schwierige Eingaben überprüft werden. Auf diese Art und Weise
+sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen
+(Komparatornetzwerken) nicht alle 0-1-Folgen, sondern nur erfolgreiche
+Parasiten (schwierige Eingaben) überprüft werden. Auf diese Art und Weise
gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren
anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist.
\end{figure}
\textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving
Non-Determinism} (END) nannte~\cite{J1995}. Dabei handelt es sich nicht um
-einen \emph{Evolutionären Algorithmus}, wie sie hier vorgestellt wurden,
+einen der \emph{Evolutionären Algorithmen}, 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
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}).
+bekannten (Abbildung~\ref{fig:13-juille}).
\newpage
-\section[Konstruktionsverfahren]{Bekannte konstruktive Sortiernetzwerke}
+\section[Konstruktionsverfahren]{Konstruktionsverfahren für Sortiernetzwerke}
\label{sect:konstruktive_netzwerke}
Die bekannten Konstruktionsverfahren für Sortiernetzwerke, insbesondere ein
"`Mischer"' in der Literatur sehr weit verbreitet ist, werden diese Begriffe
in dieser Arbeit trotzdem verwendet.}, bilden die Grundlage für die
beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
-Eingabe. Im Folgenden werden daher drei Konstruktionsverfahren vorgestellt.
+Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt.
+
+% \todo{Drei oder vier Verfahren?}
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
Dass das \emph{Odd-Even-Transpositionsort}-Netzwerk tatsächlich jede beliebige
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-Transpositionsort-Netzwerk mit drei Eingängen,
-$\operatorname{OET}(3)$, ist die Ausgabe folglich sortiert.
+Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt.
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)$.
+Herausschneiden einer Leitung aus $\operatorname{OET}(8)$. Die Rekursion endet
+beim \emph{Odd-Even-Transpositionsort}-Netzwerk mit drei Eingängen, bei dem
+das Minimum auf der untersten, das Maximum auf der obersten und der mittlere
+Wert auf der mittleren Leitung landet. Folglich ist die Ausgabe bei
+$\operatorname{OET}(3)$ sortiert.
Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die
Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen
sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n
(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.
+Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren,
+($\Theta(n \log (n)^2)$), die in weniger Schichten,
+($\Theta(\log (n)^2)$), angeordnet sind.
Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
folgenden Algorithmen benötigen ein möglichst einfaches Sortiernetzwerk als
finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
Algorithmen.
-Außerdem bedienen sich die Algorithmen der Technik des Herausschneidens einer
+Außerdem bedienen sich die Algorithmen der Technik des Herausschneidens einer,
beziehungsweise mehrerer Leitungen, um die Anzahl der Leitungen eines
Sortiernetzwerks zu reduzieren. Die Technik wird in Detail im
Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
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.
+Komparatoren als auch 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
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
+beliebige \emph{bitone Folge} in eine sortierte Liste 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.
+das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) beziehungsweise
kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge
sein darf.
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
+"`linken"' Folge $u_{m-1}$ kleiner ist als das kleinste Element der
+"`rechten"' Folge $v_{m-1}$. Daraus folgt, dass sich 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 schematisch.
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,
-\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
+zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe
+$\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.
\label{fig:bitonic-08}
\end{figure}
-Das konkrete Netzwerk~$\operatorname{BS}(8)$ ist in
+Das Sortiernetzwerk~$\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 $\bs{n = 2^d}$ 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.
+Das \emph{bitone Mergesort}-Netzwerk mit einer Leitungszahl $n = 2^d$, die
+eine Zweierpotenz ist, besteht aus $\frac{1}{4} n \log(n) \log(n+1) =
+\Theta\left(n (log (n))^2\right)$ Komparatoren, die in $\frac{1}{2}
+\log(n) \log(n+1) = \Theta(\log(n)^2)$ Schichten angeordnet sind.
\subsection{Das Odd-Even-Mergesort-Netzwerk}
\subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer}
Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein
-Komparatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$
+Komparatornetzwerk, das 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}
\input{images/oe-merge.tex}
\end{center}
\caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Im
- Vergleich zum bitonen Mischer für Acht Leitungen kommt dieses Schema mit
+ Vergleich zum bitonen Mischer für acht Leitungen kommt dieses Schema mit
einem Komparator weniger aus. Der Effekt wird durch den rekursiven Aufbau
verstärkt.}
\label{fig:oe-merge}
V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
\end{eqnarray}
-Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$
+Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$,
beziehungsweise die ungeraden Folgen $U_{\textrm{ungerade}}$ und
$V_{\textrm{ungerade}}$ werden rekursiv von kleineren \emph{Odd-Even}-Mischern
zusammengefügt, so dass sich am Ausgang der Mischer die Folgen
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:
+Mit dem {\em 0-1-Prinzip} lässt sich zeigen, sass die resultierende Folge
+sortiert ist. Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den
+geraden Teilfolgen $U_{\textrm{gerade}}$, beziehungsweise
+$V_{\textrm{gerade}}$ größer oder gleich der Anzahl der Nullen in den
+ungeraden Teilfolgen $U_{\textrm{ungerade}}$ beziehungsweise
+$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
Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthält 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
+Ausgabe zu sortieren. Diese wird von den Komparatoren ausgeführt, die
+benachbarte Leitungen miteinander vergleichen. Die jeweiligen Situationen sind
in Abbildung~\ref{fig:oe-post-recursive} dargestellt.
\begin{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
+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$:
+allgemeinen Fall verwendet, hängt gemäß der rekursiven Definition von der
+Länge der Eingabefolgen, $n$ und $m$ ab:
\begin{displaymath}
K(n,m) = \left\{ \begin{array}{ll}
nm, & \mathrm{falls} \quad nm \leqq 1 \\
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
+Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die
+Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
+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,
+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
\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
+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 Bezug auf Komparator- und Schichtzahl
entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
\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
+In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk
+zu sehen. Rot markiert sind die beiden rekursiven Instanzen
+$\operatorname{OES}(4)$. Die anderen Blöcke 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 im ersten Rekursionsschritt hinzugefügt werden.
Im Allgemeinen ist die Anzahl der Komparatoren, die vom
\emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der
-Definition beziehungsweise der Konstruktionsanleitung abzulesen:
+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.
+Da es schwierig ist für $K(n,m)$ eine geschlossene Form anzugeben, ist eine
+geschlossene Darstellung von $k(n)$ ebenfalls nicht ohne weiteres möglich. Es
+ist allerdings bekannt, dass $k(n)$ in $\Theta\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
Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
gleichzeitig ausgewertet werden, wie bereits in
Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Durch manche
-Transformationen, insbesondere das Entfernen einer Leitung, das in
-Abschnitt~\ref{sect:leitungen_entfernen} beschrieben wird, kann es vorkommen,
-dass die Komparatoren eines Sortiernetzwerks nicht mehr in der
-kleinstmöglichen Anzahl von \emph{Schichten} angeordnet sind. Unter
-\emph{Komprimierung} wird eine (Neu-)Gruppierung der Komparatoren verstanden,
-die jeden Komparator so früh wie möglich ausführt. So entsteht die
-kleinstmögliche Anzahl von \emph{Schichten}, in die sich ein Sortiernetzwerk
-unterteilen lässt.
+Transformationen, insbesondere das Entfernen einer Leitung wie in
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben, kann es vorkommen, dass
+die Komparatoren eines Sortiernetzwerks nicht mehr in der kleinstmöglichen
+Anzahl von \emph{Schichten} angeordnet sind. Unter \emph{Komprimierung} wird
+eine (Neu-)Gruppierung der Komparatoren verstanden, die jeden Komparator so
+früh wie möglich ausführt. So entsteht die kleinstmögliche Anzahl von
+\emph{Schichten}, in die sich ein Sortiernetzwerk unterteilen lässt.
Diese Anzahl ist insbesondere beim automatisierten Bewerten von
Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung}
normaliesierte Variante transformiert werden. Dazu gibt beispielsweise
\emph{Donald~E. Knuth} in~\cite{KNUTH} einen Algorithmus an.
-Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das \emph{bitone
-Mergesort}-Netzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
+Abbildung~\ref{fig:beispiel_normalisieren} stellt das \emph{bitone
+Mergesort}-Netzwerk in zwei Varianten dar. 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 untere 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.
+die untere 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
+Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die selbe
Richtung. Statt dem typischen „Treppenmuster“ sind abwechselnd das Treppen-
und das Trichtermuster zu sehen.
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,
+Diese Technik wurde 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
und Weise rekursiv aufgebaut.
Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte
-Folgen. \emph{Wie} diese Folgen sortiert wurden, ist unerheblich. Entsprechend
+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
+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
+Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken}
+$\operatorname{BS}(8)$ mit je acht Leitungen mit dem
\emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten
-Gesamtfolge zusammenfügen. Das resultierende Sortiernetzwerk besitzt
+Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt
73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
80~Komparatoren, $\operatorname{OES}(16)$ nur 63).
-Verbesserungen der Effizienz (die Anzahl der benötigten Komparatoren)
+Verbesserungen der Effizienz (die Anzahl der benötigten Komparatoren),
beziehungsweise der Geschwindigkeit (die Anzahl der Schichten) eines „kleinen“
-Sortiernetzwerks übertragen sich direkt auf das resultierende Gesamtnetzwerk.
+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
+beispielsweise 26~Komparatoren, die 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 --
+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
+das resultierende Netzwerk genauso 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.
\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
+Im vorherigen Abschnitt wurde gezeigt, 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.
+sich die Anzahl der Eingänge nicht verändert. Es soll wieder ein
+Sortiernetzwerk mit $n$~Eingängen entstehen.
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
+„eliminiert“. Dazu wird angenommen, dass das Minimum oder das Maximum an einem
bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das
Maximum 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
+welche dafür sorgen, dass der Wert die Leitung wechselt, 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 \emph{Odd-Even-Transpositionsort}-Netzwerk.
+Im ersten Schritt wird eine Leitung ausgewählt und Maximum oder Minimum auf
+dieser Leitung angenommen. Dadurch ist der Weg durch das Sortiernetzwerk
+eindeutig festgelegt.
+
\begin{figure}
\centering
\subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad
\caption{Eine Leitung wird aus dem
\emph{Odd-Even-Transpositionsort}-Netzwerk \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
- heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.}
+ nach unten weiter gegeben wird, ist der Pfad fest vorgegeben. Da die
+ restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
+ Pfad heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.}
\label{fig:oe-transposition-cut}
\end{figure}
-Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht
+Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht,
beziehungsweise 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
+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 immer noch 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 nur angefangen, das Sortiernetzwerk unter diese Annahme
-auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage
+Komparatornetzwerk immer noch sortiert werden: Es wurde lediglich die
+\emph{Position} des Minimums oder des Maximums in der Eingabe angenommen. Ein
+Sortiernetzwerk muss die Eingabe sortieren, unabhängig davon auf welcher
+Leitung das Minimum oder das Maximum liegt. Das Sortiernetzwerk unter diese
+Annahme auszuwerten -- über die verbleibenden Eingänge wurde keine Aussage
getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
mit $(n-1)$~Elementen darstellen.
-Wenn man die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in
+Wird die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in
Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, 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 auf diese Art und Weise als \emph{Minimum-Schnitt}
-beziehungsweise \emph{Maximum-Schnitt}.
+ein Minimum oder ein Maximum angenommen wird, wird das eliminieren einer
+Leitung auf diese Art und Weise als \emph{Minimum-Schnitt}, beziehungsweise
+\emph{Maximum-Schnitt} bezeichnet.
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
+markierten Komparatoren sind verschoben, so dass sich eine kompaktere
Darstellung ergibt. Außerdem ist das
\emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der
zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und
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 Sortiernetzwerke mit $2n$~Eingängen 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}.
+$n$~Eingängen reduziert werden. Als \emph{$k$-Schnittmuster} bezeichnet man
+die $k$~Minimum- und Maximum-Schnitte, die nacheinander angewendet ein
+$n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetz\-werk reduzieren.
Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
\quad (n > m)
\end{displaymath}
\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.
+unterschiedlich. Wird beispielsweise das Minimum auf der untersten Leitung
+und das Maximum auf der obersten Leitung eines Standard-Sortiernetzwerks
+angenommen, führen beide möglichen Schnitt-Reihenfolgen zum selben Ergebnis.
\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es
möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
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
+als die Anzahl der \emph{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
vernachlässigbar klein ist.
Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
-Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar.
-Die Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen
-Rechnern vorhanden ist, bevor ein entsprechender Graph den linearen Bereich
-für „kleine“ x-Werte verlässt.
+Experiment für größere Sortiernetzwerke nicht sinnvoll durchführbar. Die
+Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen Rechnern
+vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für
+„kleine“ x-Werte verlässt.
Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
können, kann man sich einer stochastischen Methode bedienen, der sogenannten
\item Möglichst wenige Schichten („schnell“)
\end{itemize}
+\begin{figure}
+ \centering
+ \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
+ \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
+ \caption{Das effizienteste und das schnellste Sortiernetzwerk für
+ 16~Leitungen, die derzeit bekannt sind.}
+ \label{fig:16-best-known}
+\end{figure}
Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus
-60~Komparatoren in 10~Schichten. Das schnellste bekannte 16-Sortiernetzwerk
-besteht aus 61~Komparatoren in nur 9~Schichten.
+60~Komparatoren in 10~Schichten. Es ist in Abbildung~\ref{fig:16-green}
+dargestellt. Das schnellste bekannte 16-Sortiernetzwerk besteht aus
+61~Komparatoren in nur 9~Schichten.
Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
berücksichtigen kann, hat die folgende allgemeine Form:
Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
-Lösungen findet oder sich in \emph{lokalen} Optima verrennt. Leider gibt es
-kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
+Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt
+es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
Leitungszahlen und Mischer-Typen experimentiert werden muss.
Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
\label{sect:sn-evolution:rekombination}
Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
-einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
-den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
-\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
-beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
-Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in
-Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
+einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu
+einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em
+bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der
+\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}),
+Anschließend werden $n$~Leitungen mit einem zufälligen $n$-Schnittmuster wie
+in Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
\label{fig:16-e1-bitonic-1296542566}
\end{figure}
-Verwendet man den \emph{bitonen Mischer} in der Rekombinationsphase von
-\textsc{SN-Evolution}, so erhält man Netzwerke wie das in
-Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte: Der Algorithmus
-wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als triviale
-Initiallösung gestartet. Das Ergebnis ist ein Netzwerk, das effizienter ist
-als das \emph{bitone Mergesort}-Netzwerk: \bs{16} benötigt 80~Komparatoren,
-das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt
-lediglich~67. Die Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks wurde
-leider mit keiner Leitungszahl erreicht.
+Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk
+als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen
+Mischer} verwendet, gibt der Algorithmus Sortiernetzwerke wie das in
+Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte zurück.
+
+Viele der Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser
+Konfiguration gefunden werden, sind effizienter als das \emph{bitone
+Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen
+Merge}-Netzwerk \bm{n} beruht. Das in
+Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk
+benötigt 67~Komparatoren, 13~Komparatoren weniger als \bs{n}.
+
+Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke
+bevorzugt, können Netzwerke zurückgegeben werden, die schneller als \bs{n}
+sind. Viele der schnellen Sortiernetzwerke sind außerdem effizienter als
+\bs{n}. Das Sortiernetzwerk mit $n = 23$ Leitungen benötigt mit
+134~Komparatoren jedoch einen Komparator mehr als \bs{23}. Die Daten von
+schnellen Sortiernetzwerken, die \textsc{SN-Evolution} mit dem \emph{bitonen
+Merge}-Netzwerk erzeugt hat, sind in Tabelle~\ref{tbl:sn-ev-bm-fast}
+aufgelistet.
+
+\begin{table}\label{tbl:sn-ev-bm-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l|}{\bs{n}} \\
+\cline{2-5}
+ ($n$) & Komp. & Schichten & Komp. & Schichten \\
+\hline
+ 8 & \gcell 20 & 6 & 24 & 6 \\
+ 9 & \Gcell 26 & 8 & 28 & 8 \\
+ 10 & \gcell 31 & \gcell 8 & 33 & 9 \\
+ 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\
+ 12 & \gcell 42 & \gcell 9 & 46 & 10 \\
+ 13 & \Gcell 48 & 10 & 53 & 10 \\
+ 14 & \gcell 54 & 10 & 61 & 10 \\
+ 15 & \Gcell 61 & 10 & 70 & 10 \\
+ 16 & \gcell 67 & 10 & 80 & 10 \\
+ 17 & \Gcell 76 & 12 & 85 & 12 \\
+ 18 & \gcell 87 & \gcell 12 & 91 & 13 \\
+ 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\
+ 20 & \gcell 104 & \gcell 13 & 106 & 14 \\
+ 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\
+ 22 & \gcell 118 & \gcell 14 & 123 & 15 \\
+ 23 & 134 & \Gcell 14 & \Gcell 133 & 15 \\
+ 24 & \gcell 133 & 15 & 144 & 15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+ unter Verwendung des \emph{bitonen Merge}-Netzwerks \bm{n}. Der Algorithmus
+ wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet
+ und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die
+ Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
+ $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}
\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
\label{fig:16-e1-oddeven-1296543330}
\end{figure}
-Leider lies sich das Ergebnis des bitonen Mischers -- die von
-\textsc{SN-Evolution} ausgegebenen Netzwerke waren effizienter als das
-rekursiv aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem
-\emph{Odd-Even-Merge}-Netzwerk nicht wiederholen. Zwar erreichen die
-Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
-\emph{Odd-Even}-Mischers findet, das \emph{Odd-Even-Mergesort}-Netzwerk
-bezüglich Geschwindigkeit und Effizienz, ein Beispiel hierfür ist in
-Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Sortiernetzwerkde, die
-effizienter als $\operatorname{OES}(n)$ sind, konnten leider nicht beobachtet
-werden. Wenn $n$ keine Zweietpotenz ist, kann \textsc{SN-Evolution} unter
-Umständen Sortiernetzwerke ausgeben, die schneller als \oes{n} sind.
+Im vorherigen Abschnitt wurde gezeigt, dass der
+\textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
+Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
+\emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind.
+Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht
+erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
+\emph{Odd-Even-Merge}-Netzwerks findet, erreichen das
+\emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
+nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
+Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen.
+
+Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch
+mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution}
+Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht
+beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt
+\textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen.
+\oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der
+Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet
+sich in Tabelle~\ref{tbl:sn-ev-oem-fast}.
%\begin{figure}
%\begin{center}
%\label{fig:10-e2-1239014566}
%\end{figure}
+\begin{table}\label{tbl:sn-ev-oem-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\
+\cline{2-5}
+ & Komp. & Schichten & Komp. & Schichten \\
+\hline
+ 8 & 19 & 6 & 19 & 6 \\
+ 9 & 26 & 8 & 26 & 8 \\
+ 10 & 31 & 9 & 31 & 9 \\
+ 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\
+ 12 & 43 & \gcell 9 & \gcell 41 & 10 \\
+ 13 & 48 & 10 & 48 & 10 \\
+ 14 & 53 & 10 & 53 & 10 \\
+ 15 & 59 & 10 & 59 & 10 \\
+ 16 & 63 & 10 & 63 & 10 \\
+ 17 & 74 & 12 & 74 & 12 \\
+ 18 & 82 & 13 & 82 & 13 \\
+ 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\
+ 20 & 97 & 14 & 97 & 14 \\
+ 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\
+ 22 & 117 & \gcell 14 & \gcell 114 & 15 \\
+ 23 & 129 & \Gcell 14 & \Gcell 122 & 15 \\
+ 24 & 128 & 15 & \gcell 127 & 15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+ unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der
+ Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n}
+ gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion
+ nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} =
+ 1$, $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}
+
+\subsection{Zufälliger Mischer}
+
+Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige
+Leitungszahlen der \emph{bitone Mischer} und für andere Leitungszahlen der
+\emph{Odd-Even}-Mischer bessere Ergebnisse liefert. Beispielsweise hat das
+Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur
+12~Schichten, bei Verwendung des \emph{Odd-Even}-Mischers hingegen nur
+82~Komparatoren. Daher liegt die Idee nahe, beide Mischer-Netzwerke zu nutzen,
+um das beste Ergebnis beider Konstruktionen zu erreichen.
+\textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier
+Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem
+\emph{Odd-Even}-Mischer wählen. \todo{Daten noch in eine Tabelle einfügen.}
+
%\input{shmoo-aequivalenz.tex}
\newpage
Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
-die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks
-leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und
-der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden.
+die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
+Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
+mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
\begin{figure}
\centering
$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
Pairwise Sorting Network“ \cite{P1992} definiert. Startet man
\textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
-16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, dass die gleiche
+16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, das die gleiche
Anzahl Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und
$\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
\end{figure}
Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
-regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk einen kleineres
+regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres
schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das
einfache Schnittmuster
\begin{displaymath}
16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten
-angeordnet sind. Das heißt, dass das resultierende Netzwerk zwar nicht so
-effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12} ist.
+angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie
+\oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
\begin{figure}
\centering
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$.
+Macht man diesen Spezialfall zum Regelfall, kombiniert das aktuelle Netzwerk
+\emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller
+Leitungen, 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.
+$S_0$ ist, das heißt, dass $S_1$ durch die Rekombination von $S_0$ mit sich
+selbst erzeugt werden kann.
Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl
der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger
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. In Pseudocode lässt dich der
+selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt sich der
Algorithmus wie folgt beschreiben:
\begin{verbatim}
Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem
zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der
\textsc{SN-Markov}-Algorithmus auf einem entsprechenden
-\emph{Odd-Even-Transpositionsort}-Netzwerk gestartet hat mindestens
+\emph{Odd-Even-Transpositionsort}-Netzwerk gestartet und hat mindestens
1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der
Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler
erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende
prozentuale Verteilung zu sehen.
-Ebenfalls in die Graphen in Abbildung~\ref{fig:markov-comparators}
+Ebenfalls in die Graphen der Abbildung~\ref{fig:markov-comparators}
eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen
Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der
um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde.
\label{fig:comparison-comparators}
\end{figure}
-Dass der \textsc{SN-Markov}-Algorithmus nicht schlechter als der
-\textsc{SN-Evolution}-Algo\-rith\-mus ist, ist aus dem Graphen in
-Abbildung~\ref{fig:comparison-comparators} ersichtlich. Analog zu dem Versuch
-mit \textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die
-Anzahl der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als
+Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der
+\textsc{SN-Markov}-Algorithmus nicht schlechter ist als der
+\textsc{SN-Evolution}-Algo\-rith\-mus. Analog zu dem Versuch mit
+\textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die Anzahl
+der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als
Startnetzwerk diente bei beiden Algorithmen das
\emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der
x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der
ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt
-wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden außerdem nach
-dem verwendeten Mischer-Netzwerk -- \oem{32} beziehungsweise \bm{32}.
+wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden sich außerdem je
+nach verwendetem Mischer-Netzwerk -- \oem{32}, beziehungsweise \bm{32}.
Sowohl der \textsc{SN-Markov}-Algorithmus, der das
\emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit
Erwartungsgemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem
\emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist
jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die
-mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort} -- \oet{16}
-ist aus 120~Komparatoren aufgebaut, bei dem Lauf, der die Daten für
+mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort}. \oet{16}
+ist aus 120~Komparatoren aufgebaut. Bei dem Lauf, der die Daten für
Abbildung~\ref{fig:comparison-comparators} lieferte, trat auch jeweils ein
-Sortiernetzwerk mit 121 und 124~Komparatoren auf. Da Sortiernetzwerke mit so
+Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so
vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen
-Iterationen nicht noch einmal erzeugt wurden, handelt es sich vermutlich um
-ein Phänomen, das mit der Initialisierung mit dem
-\emph{Odd-Even-Transpositionsort}-Netzwerk zusammenhängt.
+Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das
+mit der Initialisierung durch das \emph{Odd-Even-Transpositionsort}-Netzwerk
+zusammenhängt.
%\begin{figure}
% \begin{center}
\newpage
\section{Fazit und Ausblick}
-Dass sich mithilfe des Entfernens von Leitungen aus bekannten Sortiernetzwerke
-interessante Ergebnisse erzielen lassen, zeige \textit{Moritz Mühlenthaler}
+Mit dem Entfernen von Leitungen aus bekannten Sortiernetzwerken lassen sich
+interessante Ergebnisse erzielen. Dies zeigte \textit{Moritz Mühlenthaler}
bereits in~\cite{M2009}. Die in dieser Arbeit vorgestellten Methoden und
Resultate machen deutlich, dass sich mit diesem Verfahren noch weitere
interessante Beobachtungen machen lassen.
zurückgegeben werden, keine Struktur auf, die sich zur Angabe einer
Konstruktionsanweisung eigenen würde. Für das \emph{Pairwise-Sorting}- und das
\emph{Odd-Even-Mergesort}-Netzwerk mit Zweierpotenzen als Leitungszahl wurden
-regelmäßige Schnittmuster angegeben, die Sortiernetzwerke ergeben, die so
+regelmäßige Schnittmuster angegeben. Diese ergeben Sortiernetzwerke, die so
schnell und effizient sind wie die vergleichbaren \oes{n} und \ps{n}
Netzwerke.
bedeutet im Umkehrschluss, dass die gewonnenen Sortiernetzwerke mit mehreren
Schnittmustern erreicht werden können.
-Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von
-Sortiernetzwerken bieten, sind durch die in dieser Arbeit vorgestellten
+Die Möglichkeiten der Optimierung von Sortiernetzwerken mit
+\emph{Evolutionären Algorithmen} sind durch die in dieser Arbeit vorgestellten
Herangehensweisen bei weitem nicht erschöpft. Im Folgenden werden Ansätze
-umrissen, mit denen an die Untersuchungen in dieser Arbeit nahtlos angeknöpft
+umrissen, mit denen an die Untersuchungen in dieser Arbeit nahtlos angeknüpft
werden könnte.
\subsection{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \textsc{SN-Evolution}}
selbst definiert. Das heißt, dass \ps{n} aus zwei Instanzen von
$\ps{\frac{n}{2}}$ und zusätzlichen Komparatoren besteht, die die Eingabe für
die kleineren Sortiernetzwerke vorbereiten und anschließend für eine sortierte
-Ausgaben sorgen. Anstelle von $\ps{\frac{n}{2}}$ kann man natürlich beliebige
-Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwenden.
+Ausgabe sorgen. Anstelle von $\ps{\frac{n}{2}}$ können beliebige
+Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwendet werden.
Dies ließe sich für \textsc{SN-Evolution} nutzen, um zwei Individuen zu
rekombinieren. Da es für das \emph{Pairwise-Sorting}-Netzwerk sehr viele
\subsection{Ausblick: Kooperation von \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut}}
Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis}
-in~\cite{H1992} beschreibt, könnte man die Algorithmen \textsc{SN-Evolution}
-und \textsc{SN-Evolution-Cut} versuchen zu kombinieren. Nach dem Zusammenfügen
-von zwei $n$-Sortiernetzwerken könnte der Algorithmus
+in~\cite{H1990} beschreibt, könnte man versuchen, die Algorithmen
+\textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} zu kombinieren. Nach dem
+Zusammenfügen von zwei $n$-Sortiernetzwerken könnte der Algorithmus
\textsc{SN-Evolution-Cut} beispielsweise einen möglichst guten Schnitt für
\emph{dieses} Netzwerk ermitteln. Da sich die Lösungen, die Evolutionäre
Algorithmen in ihre Population aufnehmen, in den ersten Schritten rasch
projects / diplomarbeit.git / blobdiff