X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=c59c289fd8665e32beca703d66cf44ea574e04a6;hb=14d742c85fc0b88d2b87d2dc9c0c8b5b824dc7e7;hp=76b941a46f490313a96b6449314848debbab3a20;hpb=d775999718250435b96c1368a3b68b5d2e2cce4a;p=diplomarbeit.git

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 76b941a..c59c289 100644
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -261,10 +261,11 @@ 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-Transporitionsort-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
@@ -275,11 +276,6 @@ 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!}
-
 \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
 
 Das \emph{bitone Mergesort-Netzwerk} basiert auf dem sogenannten \emph{bitonen
@@ -387,15 +383,16 @@ alle Komparatoren in die gleiche Richtung zeigen.
   \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
@@ -931,13 +928,6 @@ 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}
-
 \begin{figure}
   \begin{center}
     \input{images/16-ec-from-ps32.tex}
@@ -946,9 +936,49 @@ Abbildung~\ref{fig:16-ec-1277186619} zu sehen.
     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}
+  \label{fig:16-ec-from-ps32}
 \end{figure}
 
+Betrachtet man das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619}, so
+ist keine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$
+erkennbar -- insbesondere die ersten Schichten des Netzwerks scheinen rein
+zufällig zu sein. Dies ist jedoch kein Eigenschaft des Algorithmus, sondern
+hängt insbesondere von der Eingaben. 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. 
+
+Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
+$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
+Pairwise Sorting Network“ 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)$. Der Algorithmus gibt
+auch nach zahlreichen Versuchen nur eines von zwei Sortiernetzwerken zurück,
+die beide sehr symmetrisch sind und eine saubere Struktur aufweisen. Eines der
+beiden Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32}
+dargestellt, das andere Sortiernetzwerk unterscheidet sich lediglich dadurch,
+dass die zweite und dritte Schicht vertauscht sind.
+
+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 -- die Schichten~1 und~2
+sowie 4~und~5 sind vertauscht, was jeweils zum selben Ergebnis nach dem
+Schichtenpaar führt.
+
+Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann
+man $\operatorname{OES}(8)$ erhalten.
+
+\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}
+
 \section{Der \textsc{SN-Evolution}-Algorithmus}
 
 Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
@@ -1241,8 +1271,8 @@ MAX( 34)
 
 Das würde mir noch einfallen$\ldots$
 
-%\bibliography{references}
-%\bibliographystyle{plain}
+\bibliography{references}
+\bibliographystyle{plain}
 
 %\listoffigures