\maketitle
\begin{abstract}
-\todo{Einleitung schreiben.}
-
-Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
-vorgestellt (Odd-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
-Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
-Evolutionäre Algorithmen werden beschrieben und ein evolutionärer
-Algorithmus für die Optimierung von Sortiernetzwerken wird angegeben.
-Die mindestens von diesem Algorithmus erreichte Güte wird angegeben und die
-Transformation zu einer Markov-Kette wird gezeigt. {\em Natürlich: So fern ich
-das hin bekomme bzw. Recht behalte.}
+Sortiernetzwerke erweisen sich als sehr schwieriges Optimierungsproblem. Zwar
+ist das Konzept leicht verständlich und schnell erklärt, effiziente und
+schnelle Sortiernetzwerke zu finden oder zu konstruieren bleibt aber eine
+Herausforderung.
+
+Diese Arbeit verwendet „Schnitte“ oder „Leitungselimination“ und
+Mischer-Netzwerke, um evolutionäre Algorithmen anzugeben, deren Individuen die
+Menge der gültigen Sortiernetzwerke nie verlassen. Bisherige Ansätze 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
+evolutionären Algorithmus \textsc{SN-Evolution} -- eine Markov-Kette für
+Sortiernetzwerke angegeben.
\end{abstract}
\newpage
Konstruktionsvorschrift genutzt werden kann um die Korrektheit für beliebige
Eingabegrößen zu beweisen. Im Abschnitt~\ref{sect:konstruktive_netzwerke}
geschieht dies beispielsweise für zwei von \emph{Kenneth~E. Batcher} 1968
-gefundenen Konstruktionsvorschriften.
+gefundene Konstruktionsvorschriften.
-Um effiziente und schnelle Sortiernetzwerke zu finden, wurden schon früh
+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
die Sortiereigenschaft besitzen und aus wenigen Komparatoren bestehen. Die
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}
Bekannten (Abbildung~\ref{fig:13-juille}).
\newpage
-\section{Bekannte konstruktive Sortiernetzwerke}
+\section[Konstruktionsverfahren]{Bekannte konstruktive Sortiernetzwerke}
\label{sect:konstruktive_netzwerke}
-Übersicht über bekannte konstruktive Sortiernetzwerke.
-
-\todo{Einleitungssatz}
+Die bekannten Konstruktionsverfahren für Sortiernetzwerke, insbesondere
+sogenannte \emph{Mischer}, bilden die Grundlage für die beschriebenen
+evolutionären Algorithmen beziehungsweise dienen als initiale Eingabe. Im
+Folgenden werden daher drei Konstruktionsverfahren vorgestellt.
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
Algorithmen.
+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.
+
\subsection{Das bitone Mergesort-Netzwerk}
Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
\end{eqnarray*}
-\subsection{Versuche mit dem bitonen Mischer}
+\subsection[Bitoner Mischer]{Versuche mit dem bitonen Mischer}
\begin{figure}
\begin{center}
das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt
lediglich~67.
-\subsection{Versuche mit dem \emph{Odd-Even}-Mischer}
+\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
\begin{figure}
\begin{center}
$\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch
nicht beobachtet werden.
-\todo{Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.}
-
%\begin{figure}
%\begin{center}
%\input{images/08-e2-1237993371.tex}
in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, 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$.
+Schnittmusters. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.
Die Mutation setzt entweder die Leitungsnummer eines Schnitts~$i$ zufällig auf
einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
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.
+Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{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
leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und
der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden.
+\begin{figure}
+ \centering
+ \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/11-ec-from-bs22-fast.tex}\label{fig:11-ec-from-bs22-fast}}
+ \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{24} erzeugt.]{\input{images/12-ec-from-bs24-fast.tex}\label{fig:12-ec-from-bs24-fast}}
+ \caption{Startet man \textsc{SN-Evolution-Cut} mit \bs{22} und \bs{24}, kann
+ der Algorithmus schnelle Sortiernetzwerke ausgeben.}
+ \label{fig:11-12-ec-from-bs22-bs24}
+\end{figure}
+
+Verwendet man als Eingabe für \textsc{SN-Evolution-Cut} Instanzen des
+\emph{bitonen Mergesort}-Netzwerks, deren Leitungszahl keine Zweierpotenz ist,
+können Sortiernetzwerke zurückgegeben werden, die sowohl schneller als auch
+effizienter als das entsprechende \emph{bitone Mergesort}-Netzwerk sind. Die
+folgende Tabelle listet einige interessante Fälle auf. Die Eingabe für
+\textsc{SN-Evolution-Cut} war jeweils das \emph{bitone Mergesort}-Netzwerk mit
+der doppelten Leitungszahl.
+Abbildung~\ref{fig:23-ec-from-bs46} zeigt beispielhaft ein
+23-Sortiernetzwerk, das aus \bs{46} generiert wurde.
+\begin{center}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
+ & \textsc{SN-EC} & \textsc{SN-EC} & \bs{n} &
+ \bs{n} \\
+\hline
+11 & 37 & 9 & 39 & 10 \\
+12 & 42 & 9 & 46 & 10 \\
+19 & 93 & 13 & 98 & 14 \\
+20 & 102 & 13 & 106 & 14 \\
+% 20: # sn-cut 2:MAX 3:MIN 4:MIN 9:MIN 10:MIN 13:MIN 14:MIN 15:MIN 19:MIN 20:MAX 24:MAX 26:MIN 27:MAX 29:MIN 31:MAX 33:MIN 34:MAX 35:MIN 37:MIN 39:MAX
+21 & 109 & 14 & 114 & 15 \\
+22 & 116 & 14 & 123 & 15 \\
+23 & 124 & 14 & 133 & 15 \\
+\hline
+\end{tabular}
+\end{center}
+
+\begin{figure}
+ \begin{center}
+ \input{images/23-ec-from-bs46-fast.tex}
+ \end{center}
+ \caption{23-Sortiernetzwerk mit 124~Komparatoren in 14~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{46} mit dem
+ Schnittmuster $\operatorname{MIN}(2, 4, 9, 12, 20, 22, 28, 30, 32, 33, 37,
+ 38, 41)$, $\operatorname{MAX}(1, 5, 16, 19, 21, 24, 25, 35, 36, 43)$
+ erzeugt.}
+ \label{fig:23-ec-from-bs46}
+\end{figure}
+
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
$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{OES}(16)$. Eines dieser Sortiernetzwerke ist in
Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
+\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}
+
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
untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.
\subsection{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:oes}
In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke
\emph{Odd-Even-Mergesort}-Netzwerk die wenigsten unterschiedlichen
16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. Entsprechend ist es
wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit
-$\operatorname{OES}(32)$ sehr schnell ein gutes 16-Schnittmuster findet.
-
-Eines der eher zufälligen Schnittmuster ist $\operatorname{MIN}(1, 6, 11, 14,
-17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, 8,$ $13, 18, 21, 27, 31)$. Das
-Schnittmuster ist in Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht,
-das resultierende Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
+$\operatorname{OES}(32)$ sehr schnell\footnote{Auf dem Computer, auf dem diese
+Arbeit geschrieben wurde, dauerte es in den meisten Fällen weniger als eine
+Sekunde bis ein entsprechendes Schnittmuster gefunden wurde.} ein gutes
+16-Schnittmuster findet.
+
+Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
+bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist
+$\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7,
+8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in
+Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende
+Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
\begin{figure}
\begin{center}
\label{fig:16-ec-from-oes32}
\end{figure}
+Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3,
+4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser
+Beobachtung kann man das regelmäßige Schnittmuster
+\begin{displaymath}
+\textit{Eingang}_i = \left\{ \begin{array}{rl}
+ \infty & \quad \textrm{falls } i \bmod 4 = 0 \\
+ -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\
+ ? & \quad \mathrm{sonst}
+ \end{array} \right.
+\end{displaymath}
+ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der
+Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente
+Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein
+32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde,
+ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.
+
+\begin{figure}
+ \begin{center}
+ \input{images/32-ec-from-oes64.tex}
+ \end{center}
+ \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten.
+ Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem
+ \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.}
+ \label{fig:32-ec-from-oes64}
+\end{figure}
+
+Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so
+erzeugten Sortiernetzwerke die Effizienz des
+\emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster
+beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit
+43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit
+beider Sortiernetzwerke ist mit 10~Schichten identisch.
+
+Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24}
+und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der
+verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der
+Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20,
+22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in
+Abbildung~\ref{12-ec-from-oes24-efficient} zu sehen ist. Das resultierende
+Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet
+werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit
+gleichauf mit \oes{12}. Werden hingegen schnelle Sortiernetzwerke bevorzugt,
+werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
+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} ist, dafür aber schneller als \oes{12} und \bs{12}.
+
+\begin{figure}
+ \centering
+ \subfigure[Schnelles 12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten,
+ das von \textsc{SN-Evolution-Cut} aus dem \emph{Odd-Even-Mergesort}-Netzwerk
+ generiert
+ wurde.]{\input{images/12-ec-from-oes24-fast.tex}\label{fig:12-ec-from-oes24-fast}}
+ \subfigure[Effizientes 12-Sortiernetzwerk aus 41~Komparatoren in
+ 10~Schichten, das von \textsc{SN-Evolution-Cut} aus dem
+ \emph{Odd-Even-Mergesort}-Netzwerk generiert
+ wurde.]{\input{images/12-ec-from-oes24-efficient.tex}\label{fig:12-ec-from-oes24-efficient}}
+ \caption{Startet man \textsc{SN-Evolution-Cut} mit \oes{24}, hängt das
+ Ergebnis von der Bewertungsfunktion ab.}
+ \label{fig:12-ec-from-oes24}
+\end{figure}
+
+Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut}
+findet Sortiernetzwerke, die schneller sind als das entsprechende
+\emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das
+\emph{Odd-Even-Mergesort}-Netzwerk mit 22, 24, 38, 40, 42, 44 und 46
+Eingängen. In der folgenden Tabelle sind einige schnelle Netzwerke, die von
+\textsc{SN-Evolution-Cut} generiert werden können, charakterisiert. Die
+Eingabe für \textsc{SN-Evolution-Cut} war jeweils das
+\emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl.
+\begin{center}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
+ & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\
+\hline
+11 & 38 & 9 & 37 & 10 \\
+12 & 43 & 9 & 41 & 10 \\
+19 & 93 & 13 & 91 & 14 \\
+20 & 101 & 13 & 97 & 14 \\
+21 & 108 & 14 & 107 & 15 \\
+22 & 116 & 14 & 114 & 15 \\
+23 & 125 & 14 & 122 & 15 \\
+\hline
+\end{tabular}
+\end{center}
+Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
+23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem
+Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der
+Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In
+beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu
+\bs{23} beziehungsweise \oes{23} eine Schicht einspart. Allerdings ist das
+Sortiernetzwerk auf Basis von \bs{46} (Abbildung~\ref{fig:23-ec-from-bs46})
+effizienter, da es nur 124~Komparatoren benötigt.
+
+\begin{figure}
+ \begin{center}
+ \input{images/23-ec-from-oes46-fast.tex}
+ \end{center}
+ \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten.
+ Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem
+ Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38,
+ 44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$
+ erzeugt.}
+ \label{fig:23-ec-from-oes46}
+\end{figure}
+
\newpage
\section{Der \textsc{SN-Markov}-Algorithmus}
\label{sect:markov}
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
-Abbildung~\ref{fig:comparison-comparators} lieferte, traten auch jeweils ein
+Abbildung~\ref{fig:comparison-comparators} lieferte, trat auch jeweils ein
Sortiernetzwerk mit 121 und 124~Komparatoren auf. Da 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
% \label{fig:markov-cycles-16}
%\end{figure}
-
-\todo{Schreibe noch etwas zu …}
-\begin{itemize}
- \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
- \item Anzahl der erreichbaren Sortiernetzwerke.
- \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen
- Netzwerke. (Abbildung~\ref{fig:markov-comparators-16})
- \item \textsc{SN-Count-Markov} (ggf)
-\end{itemize}
-
\newpage
\section{Fazit und Ausblick}
-\todo{Ausformulieren}
-\begin{itemize}
-\item Mit \textsc{SN-Evolution} und \oem{n} kann man nicht besser werden als
- \oes{n}.
-\item Mit \textsc{SN-Evolution} und \bm{n} kann man besser werden als \bs{n}.
-\item Vermutlich kann man mit \textsc{SN-Evolution} und \bm{n} so gut werden
-wie \textsc{SN-Evolution-Cut}, wenn er mit \bs{2n} gestartet wird.
-\item Leider sind keine konstruktiven Methoden erkannt worden.
-\end{itemize}
+Dass sich mithilfe dem Entfernen von Leitungen aus bekannten Sortiernetzwerke
+interessante Ergebnisse erzielen lassen, zeige \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.
+
+Das \emph{Odd-Even-Mergesort}-Netzwerk wird sowohl von \textsc{SN-Evolution},
+\textsc{SN-Evolution-Cut} und \textsc{SN-Markov} erreicht. Wenn die Anzahl der
+Leitungen keine Zweierpotenz ist, kann gegebenenfalls ein schnelleres
+Sortiernetzwerk erzeugt werden. Einige Beispiele hierfür wurden in
+Abschnitt~\ref{sect:sn-evolution-cut:oes} aufgezeigt.
+
+Das \emph{bitone Mergesort}-Netzwerk kann in Bezug auf Effizienz von den
+vorgestellten Algorithmen übertroffen werden. Der Algorithmus
+\textsc{SN-Evolution-Cut} kann das Ergebnis von \textit{Mühlenthaler} und
+\textit{Wanka} (\cite{MW2010}) für ein 16-Sortiernetzwerk reproduzieren und
+für ein 32-Sortiernetzwerk sogar noch übertreffen. Der
+\textsc{SN-Evolution}-Algorithmus fand ein 16-Sortiernetzwerk, das gegenüber
+dem Ergebnis von \textsc{SN-Evolution-Cut} beziehungsweise~\cite{MW2010} einen
+weiteren Komparator einspart.
+
+Leider weisen die Sortiernetzwerke, die von den angegebenen Algorithmen
+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
+schnell und effizient sind wie die vergleichbaren \oes{n} und \ps{n}
+Netzwerke.
+
+Die Anzahl der \emph{unterschiedlichen} Schnitte von verschiedenen
+Sortiernetzwerken wurde experimentell bestimmt und gezeigt, dass es deutlich
+weniger \emph{unterschiedliche} als \emph{mögliche} Schnittmuster gibt. Das
+bedeutet im Umkehrschluss, dass die gewonnenen Sortiernetzwerke mit mehreren
+unterschiedlichen 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
-Herangehensweisen bei weitem nicht erschöpft.
-
-Im Folgenden werden Ansätze umrissen, mit denen an die Untersuchungen in
-dieser Arbeit nahtlos angeknöpft werden könnte.
+Herangehensweisen bei weitem nicht erschöpft. Im Folgenden werden Ansätze
+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}}
erwiesen.
Funktionen, die von Kommandozeilen-Programmen zur Verfügung gestellt werden,
-sind unter anderem das Erzeugen von Odd-Even-Mergesort-, bitonic Mergesort-
-und Pairwise-Sorting-Netzwerken, das Normalisieren von Sortiernetzwerken,
-Anwendung von Schnittmustern auf Sortiernetzwerke und Anwendung eines
-Komparatornetzwerks auf eine Eingabe-Permutation.
+sind unter anderem das Erzeugen des \emph{Odd-Even-Mergesort}-, \emph{bitonen
+Mergesort}- und \emph{Pairwise-Sorting}-Netzwerks, das Normalisieren von
+Sortiernetzwerken, Anwendung von Schnittmustern auf Sortiernetzwerke und
+Anwendung eines Komparatornetzwerks auf eine Eingabepermutation. Das
+Darstellen von Sortiernetzwerken wird ebenfalls angeboten, beispielsweise
+wurden die Sortiernetzwerke in dieser Arbeit mit dem Kommando \texttt{sn-tex}
+visualisiert.
\textit{libsortnetwork} kann unter der Web-Adresse
\url{http://octo.it/libsortnetwork/} unentgeltlich heruntergeladen werden.
\end{document}
-% vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 :
+% vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 spelllang=de :
projects / diplomarbeit.git / blobdiff