-\documentclass[a4paper,10pt]{article}
+\documentclass[a4paper,11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{ngerman}
\usepackage{fancyhdr}
\tikzstyle{diredge} = [draw,thick,->]
\tikzstyle{prob} = [font=\tiny]
+\tikzstyle{edge minimum} = [edge,color=blue!20]
+\tikzstyle{edge maximum} = [edge,color=red!20]
+\tikzstyle{vertex active minimum} = [vertex,color=blue!50, fill=blue!50]
+\tikzstyle{vertex active maximum} = [vertex,color=red!50, fill=red!50]
+\tikzstyle{vertex active minimum maximum} = [vertex,color=violet!50, fill=violet!50]
+\tikzstyle{vertex inactive minimum} = [vertex,color=blue!20, fill=blue!20]
+\tikzstyle{vertex inactive maximum} = [vertex,color=red!20, fill=red!20]
+\tikzstyle{vertex inactive minimum maximum} = [vertex,color=black!20, fill=black!20]
+\tikzstyle{comp active minimum} = [comp]
+\tikzstyle{comp active maximum} = [comp]
+\tikzstyle{comp active minimum maximum} = [comp,color=black!20]
+\tikzstyle{comp inactive minimum} = [comp,color=blue!20]
+\tikzstyle{comp inactive maximum} = [comp,color=red!20]
+\tikzstyle{comp inactive minimum maximum} = [comp,color=black!20]
+
\tikzstyle{red box} = [draw,-,color=red, top color=red!2,bottom color=red!10]
\tikzstyle{blue box} = [draw,-,color=blue,top color=blue!2,bottom color=blue!10]
\tikzstyle{green box} = [draw,-,color=teal,top color=teal!2,bottom color=teal!10]
\newpage
\tableofcontents
-\newpage
+\newpage
\section{Motivation und Einleitung}
\subsection{Motivation}\label{sect:motivation}
verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
-werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em
+werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
Gütefunktion}.
Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
Methode für die Rekombination existieren. Das 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.
+
\begin{itemize}
\item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$
\item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die
Mutation \textit{(vermutlich)} nicht (effizient) möglich.
\end{itemize}
+\newpage
\section{Bekannte konstruktive Sortiernetzwerke}
+\label{sect:konstruktive_netzwerke}
Übersicht über bekannte konstruktive Sortiernetzwerke.
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 (einfaches) Sortiernetzwerk als
+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{K.~E.~Batcher} veröffentlicht wurde. Es
-ist deutlich effizienter als das Odd-Even-Transporitionsort-Netzwerk -- sowohl
-in Bezug auf die Anzahl der Komparatoren als auch bezüglich der benötigten
-Zeit, also der Anzahl der Schichten.
+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
verleiht dem Sortiernetzwerk seinen Namen.
Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
-Instanzen des Netzwerks, deren Leitungszahl eine Zweierpotenz ist,
-$\operatorname{BS}(n = 2^t)$.
-
-Ein Netzwerk von K.~E.~Batcher. Siehe:
-K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring
-Joint Comput. Conf., Vol. 32, 307-314 (1968)
-\todo{Bibtex!}
+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}
\begin{center}
\input{images/batcher-8.tex}
\end{center}
- \caption{$S(8)$, Batcher's {\em bitone Mergesort-Netzwerk} für acht
- Eingänge. Markiert sind die beiden Instanzen von $S(4)$ (rot), die beiden
- bitonen Mischer~$M(4)$ (blau) und die Komparatoren, die im letzten rekursiven
- Schritt hinzugefügt wurden (grün).}
- \label{fig:batcher_08}
+ \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:batcher_08} zu sehen. Eingezeichnet sind ebenfalls die
+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
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{K.~Batcher} gefunden worden und wird rekursiv durch einen Mischer
-definiert.
+\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}
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}.\footnote{Knuth,
-“Bitonic Sorting”, Seite~230}
+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
\subsubsection{Das Odd-Even-Mergesort-Netzwerk}
-Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht, --~wie
-das \emph{bitonen 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 Bezuf auf Komparator- und Schichtzahl
entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
$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{K.~Batcher}
-zeigt in seiner Arbeit\footnote{\todo{Referenz!}}, dass in diesem Fall
+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}
%\item Pairwise sorting-network
%\end{itemize}
+\newpage
\section{Transformation von Sortiernetzwerken}
\subsection{Komprimieren}
\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{Baddar} und
-\textit{Batcher} in ihrer Arbeit „An 11-Step Sorting Network for 18~Elements“
-vorstellen, benötigt aber 6~Komparatoren weniger.
+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
zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
Ausgabe und kann entfernt werden.
+\subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
+\label{sect:anzahl_schnittmuster}
+
Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
-$n-3$,~\dots Eingängen zu erzeugen. Insbesondere können wir auf diese Art und
-Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
-mit $n$~Eingängen reduzieren.
+$n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und
+Weise einen Sortiernetzwerke mit $2n$~Eingängen wieder auf Sortiernetzwerke
+mit $n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die
+nacheinander angewendet ein $n$-Sortiernetzwerk auf ein
+${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als
+\emph{$k$-Schnittmuster}.
-\subsubsection{Der \textsc{SN-Evolution-Cut}-Algorithmus}
+Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
+auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
+Schnittmuster \emph{unterschiedlich} bezüglich~$S$.
Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
-ein $n$-Sortiernetzwerk auf ein $m$-Sortiernetzwerk zu reduzieren, ergeben
-sich insgesamt
-\begin{displaymath}
- \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
+ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
+ergeben sich insgesamt
+\begin{equation}\label{eqn:anzahl_schnittmuster}
+ \prod_{i=n}^{1+n-k} 2i = 2^k \frac{n!}{(n-k)!}
\quad (n > m)
-\end{displaymath}
-Möglichkeiten. Diese Möglichkeiten sind nicht alle unterschiedlich. Legt man
-beispielsweise das Minimum auf die unterste Leitung und das Maximum auf die
-oberste Leitung eines Standard-Sortiernetzwerks, führen beide Reihenfolgen zum
-selben Ergebnis.
-
-\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass
-es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise
-Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnitte
-reduziert, die Menge der erreichbaren Sortiernetzwerke bleibt aber
-unverändert. Die Anzahl der möglichen „Schnittmuster“ setzt sich zusammen aus
-der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
-und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
-Formel:
+\end{equation}
+\emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
+unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung
+und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks,
+führen beide Reihenfolgen zum selben Ergebnis.
+
+\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass es
+möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
+vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster reduziert,
+die Menge der so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die
+Anzahl der möglichen Schnittmuster setzt sich zusammen aus der Anzahl von
+Möglichkeiten, $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen
+Minimum-~/ Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl
+der möglichen Schnittmuster:
\begin{displaymath}
- 2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
- = 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
- = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!}
- \quad (n > m)
+ 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
+ = 2^{k} \cdot \frac{n!}{k! (n-k)!}
+ = 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!}
+ \quad (1 \leqq k < n)
\end{displaymath}
-Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden
+Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden
Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
-ein Sortiernetzwerk mit 16~Ein\-gängen zu reduzieren sind 16~Schnitte notwendig,
-für die es bereits etwa ${3,939 \cdot 10^{13}}$ Möglichkeiten gibt. Ein
-Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter
-erheblichem Ressourcenaufwand möglich.
-
-Das Programm \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{Schnitt-Sequenzen} als Individuen. Eine \emph{Schnitt-Sequenz} ist eine
-Liste mit $c$~Schnitten, die jeweils durch die Start-Leitung und die Richtung
-\textit{Min} beziehungsweise \textit{Max} gegeben ist. Der Algorithmus wendet
-jeden Schnitt einzeln an, so dass eine Leitungsnummer mehrfach in einer
-Schnittsequenz vorkommen kann. Die höchste zulässige Leitungsnummer ist
-abhängig von der Position des Schnitts in der Sequenz. Der Schnitt an
-Position~$i$ darf höchstens die Leitungsnummer~${n-i-1}$
-enthalten.\footnote{Die niedrigste Leitungsnummer ist $0$, die höchste
-Leitungsnummer eines $n$-Sortiernetzwerks ist $n-1$.}
-
-Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte der einen
-Schnitt-Sequenz verwendet und die letzten ${c-r}$~Schnitte der zweiten
-Sequenz. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.
+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.
-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.
-
-In ihrer Arbeit \textit{“Improving Bitonic Sorting by Wire Elimination”}
-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.
+\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}
-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.
+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}
- \input{images/16-ec-1277186619.tex}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
\end{center}
- \caption{{\tt images/16-ec-1277186619.tex}: Sortiernetzwerk mit 16~Leitungen
- und 68~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem
- Algorithmus \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
- $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
- \label{fig:16-ec-1277186619}
+ \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der
+ \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und
+ $\operatorname{BS}(32)$.}
+ \label{fig:collisions-10000-1000000-32}
\end{figure}
-Startet man {\sc SN-Evolution-Cut} mit dem bitonen Mergesort-Netzwerk
-$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
-Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
-16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in
-Abbildung~\ref{fig:16-ec-1277186619} zu sehen.
-
-\begin{itemize}
- \item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort.
- \item Wie gut kann man durch wegschneiden werden?
- \item Wieviele Schnitte ergeben das selbe Netzwerk?
- \item Abschnitt „Optimierung der Schnitte“ hier einbauen.
-\end{itemize}
+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}
- \input{images/16-ec-from-ps32.tex}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf}
\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-1277186619}
+ \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}
Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
berücksichtigen kann, hat die folgende allgemeine Form:
\begin{equation}
- \mathit{Guete}(S) = w_{\mathrm{Basis}}
+ \operatorname{Guete}(S) = w_{\mathrm{Basis}}
+ w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
+ w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
\end{equation}
\begin{itemize}
\item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}.
\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
+\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
\end{itemize}
-\section{Markov-Kette}
+%\input{shmoo-aequivalenz.tex}
+
+\newpage
+\section{Der \textsc{SN-Evolution-Cut}-Algorithmus}
+\label{sect:sn-evolution-cut}
+
+Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
+Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
+Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
+möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
+Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
+gute Schnittmuster gesucht.
+
+Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster}
+als Individuen. Um zwei Individuen zu rekombinieren werden die ersten
+$r$~Schnitte des einen Schnittmusters verwendet und die letzten
+${c-r}$~Schnitte des zweiten Schmittmusters. $r$ ist eine Zufallsvariable mit
+$0 \leqq r \leqq c$.
+
+Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
+auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
+Schnitt-Richtung.
+
+\subsection{Versuche mit dem bitonen Mergesort-Netzwerk}
+
+In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka},
+wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
+durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen
+Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer
+sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert
+werden, Komparatoren ein.
-Der evolutionäre Algorithmus aus dem vorherigen Abschnitt verwendete immer
-zwei zufällige Sortiernetzwerke („Individuen“) aus einer Population. Da die
-beiden „Eltern“ zufällig und unabhängig voneinander ausgewählt werden, kann es
-vorkommen, dass das selbe Sortiernetzwerk zweimal verwendet und mit sich
-selbst kombiniert wird.
+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}
+
+Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
+Abschnitt verwendete immer zwei zufällige Sortiernetzwerke („Individuen“) aus
+einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander
+ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal
+verwendet und mit sich selbst kombiniert wird.
Macht man diesen Spezialfall zum Regelfall, indem man \emph{immer} das
aktuelle Netzwerk mit sich selbst kombiniert und anschließend die Hälfte aller
hervorgehen können, heißen \emph{Nachfolger} von $S_0$.
Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
-gerichteten Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
+(gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
-Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $S_0$
-ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
+Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von
+$S_0$ ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
selbst erzeugen kann.
-Der Algorithmus {\sc SN-Markov} legt auf diesem Graph einen zufälligen Weg
-(englisch: \textit{random walk}) zurück. Er startet auf einem gegebenen
-Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu gelangen
-rekombiniert er das aktuelle Sortiernetzwerk mit sich selbst und erhält so
-einen zufälligen Nachfolger.
+Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben ist die Anzahl
+(unterschiedlicher) Schnittmuster und damit die Anzahl der Nachfolger sehr
+groß. Wenn $S_0$ ein Sortiernetzwerk mit $n$~Leitungen ist, so hat $S_0$ bis
+zu
+\begin{displaymath}
+ 2^n \cdot \left( \begin{array}{c} 2n \\ n \end{array} \right)
+\end{displaymath}
+Nachfolger.
+
+Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen
+zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem
+gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu
+gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich
+selbst und erhält so einen zufälligen Nachfolger.
\begin{itemize}
\item $n \leftarrow \mathrm{Input}$
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16.pdf}
+ \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf}
\end{center}
- \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden.}
- \label{fig:markov-comparators-16}
+ \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen),
+ die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
+ \emph{Gamma-Verteilung} $f(x - 40)$ mit $k = 8,267$ und $\theta = 0,962$.}
+ \label{fig:markov-comparators-12}
\end{figure}
-%\input{shmoo-aequivalenz.tex}
-
-\section{Optimierung der Schnitte}
-
-\todo{In den Abschnitt "`Leitungen entfernen"' einbauen.}
-
\begin{figure}
-\begin{center}
-\input{images/32-ec-1277190372.tex}
-\end{center}
-\caption{{\tt images/32-ec-1277190372.tex}: Sortiernetzwerk mit 32~Leitungen
- und 206~Komparatoren in 15~Schichten. Das Netzwerk wurde von dem Algorithmus
- \textsc{SN-Evolution-Cut} aus dem Bitonic-Mergesort-Netzwerk $BS(64)$ durch
- 32~Schnitte erzeugt.}
-\label{fig:32-ec-1277190372}
+ \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}
-Abbildung~\ref{fig:32-ec-1277190372} zeigt ein 32-Sortiernetzwerk, dass vom
-\textsc{SN-Evolution-Cut}-Algorithmus aus dem $BS(64)$-Netzwerk erzeugt wurde.
-Es besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als
-$BS(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler
-und Wankas Methode konstruiert wird. Die Anzahl der Schichten ist bei allen
-Netzwerken gleich.
-
-\textbf{TODO:} $BS(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten
-möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$
-Komparatoren; $BS(64)$: 672~Komparatoren.
-
-Schnitt-Sequenz:
-MIN( 92)
-MAX( 80)
-MIN(100)
-MAX( 54)
-MAX(102)
-MAX( 53)
-MAX(105)
-MAX( 6)
-MAX( 99)
-MAX( 79)
-MAX( 26)
-MIN(111)
-MAX( 12)
-MIN( 22)
-MAX( 61)
-MAX( 72)
-MAX( 68)
-MIN( 80)
-MAX( 80)
-MAX( 99)
-MAX(105)
-MAX( 0)
-MIN( 8)
-MAX( 40)
-MAX( 74)
-MAX( 40)
-MAX( 40)
-MIN( 56)
-MAX( 27)
-MAX( 13)
-MAX( 1)
-MAX( 81)
-MAX( 17)
-MAX( 4)
-MIN( 36)
-MIN( 22)
-MAX( 13)
-MIN( 72)
-MAX( 24)
-MAX( 5)
-MIN( 10)
-MAX( 59)
-MIN( 37)
-MAX( 65)
-MAX( 46)
-MAX( 73)
-MAX( 58)
-MAX( 29)
-MAX( 65)
-MIN( 23)
-MAX( 56)
-MAX( 11)
-MIN( 75)
-MIN( 51)
-MIN( 46)
-MIN( 34)
-MAX( 32)
-MAX( 6)
-MAX( 37)
-MIN( 4)
-MIN( 28)
-MIN( 20)
-MAX( 33)
-MAX( 34)
-
-% images/32-ec-1277190372.tex
+\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 $\ldots$
\end{itemize}
+\newpage
\section{Ausblick}
Das würde mir noch einfallen$\ldots$
-%\bibliography{references}
-%\bibliographystyle{plain}
+\newpage
+\section{Implementierung}
+
+So habe ich die ganzen Versuche durchgeführt.
+
+\newpage
+\bibliography{references}
+\bibliographystyle{plain}
%\listoffigures
projects / diplomarbeit.git / blobdiff