\begin{document}
-\tikzstyle{vertex} = [circle,draw,thick,fill=black,minimum size=5pt,inner sep=0pt]
+\tikzstyle{vertex} = [circle,draw,thick,fill=black,minimum size=5,inner sep=0pt]
\tikzstyle{comp} = [draw,thick,-]
\tikzstyle{compup} = [draw,thick,->]
\tikzstyle{compdown} = [draw,thick,<-]
\tikzstyle{diredge} = [draw,thick,->]
\tikzstyle{prob} = [font=\tiny]
+\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]
+\tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10]
+
\maketitle
\begin{abstract}
Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
\todo{$0-1$-Prinzip}
+Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft
+besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen
+ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle
+$2^n$~${0-1}$-Folgen sortiert.
+
Sortiernetzwerke:
\begin{itemize}
\item Ein Komparator-Netzwerk ist $\ldots$
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
+ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
-verändert ({\em Mutation}), bevor sie in die bestehende Lösungsmenge
+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
einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
"`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
Abbildung~\ref{fig:odd_even_transposition_08} zeigt das OET-Netzwerk für
-${n = 8}$.
+${n = 8}$ Leitungen.
\begin{figure}
\begin{center}
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}
+\subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
Das Netzwerk basiert auf dem {\em bitonen Mischer}, einem Komparator-Netzwerk,
das eine beliebige bitone Folge in eine sortierte Listen umordnen kann. Eine
\begin{figure}
\centering
\subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
+ \qquad
\subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
\caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
- resultierenden Teilfolgen sind wiederum biton.
- }
+ resultierenden Teilfolgen sind wiederum biton.}
\label{fig:bitonic-merge-schema}
\end{figure}
%\end{figure}
\begin{figure}
-\begin{center}
-\input{images/batcher-8.tex}
-\end{center}
-\caption{$S(8)$, as {\em Batcher-Mergesort} Netzwerk für acht Eingänge.
-Markiert sind die beiden Instanzen von $S(4)$ (rot) und der bitone Mischer
-$M(8)$ (blau).}
-\label{fig:batcher_08}
+ \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}
\end{figure}
\subsection{Odd-Even-Mergesort}
Obwohl der Name ähnlich klingt, haben {\em Odd-Even-Mergesort} (OEM) und
-Odd-Even-Transporisionsort (OET, siehe
+{\em Odd-Even-Transpositionsort} (OET, siehe
Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Auch dieses
Netzwerk ist von K.~Batcher gefunden worden und wird rekursiv durch einen
-Mischer definiert.
+"`Mischer"' definiert.
+
+\subsubsection{Der Odd-Even-Mischer}
-Beispiel: Siehe Abbildung~\ref{fig:odd_even_mergesort_08}.
+Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte
+Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit
+weniger Vergleichen aus als der {\em bitone Mischer}, der im
+Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde.
+
+Der {\em Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
+Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
+sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
+$V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
+$W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
+\begin{equation}
+w_i = \left\{ \begin{array}{ll}
+ u_i, & i < n \\
+ v_{i-n}, & i \geqq n
+ \end{array} \right.,
+ \quad 0 \leqq i < N
+\end{equation}
+
+\begin{figure}
+ \begin{center}
+ \input{images/oe-merge.tex}
+ \end{center}
+ \caption{Schematischer Aufbau des {\em Odd-Even} Mischers. Im Vergleich zum
+ bitonen Mischer für Acht kommt dieses Schema mit einem Komparator weniger
+ aus. Der Effekt wird duch den rekursiven Aufbau noch verstärkt.}
+ \label{fig:oe-merge}
+\end{figure}
+
+Diese werden jetzt in insgesamt vier sortierte Folgen aufgeteilt, je eine
+Liste der geraden Indizes und je eine Liste der ungeraden Indizes.
+\begin{eqnarray}
+ U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\
+ U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
+ V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\
+ V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
+\end{eqnarray}
+
+Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die
+ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden
+rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am
+Ausgang der Mischer die Folgen
+\begin{eqnarray}
+ W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
+ W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
+\end{eqnarray}
+ergeben.
+
+Anschließend werden die Komparatoren zwischen benachbarten Leitungen
+hinzugefügt,
+\begin{equation}
+ w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
+\end{equation}
+die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em
+Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}.
+
+Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
+Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
+entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
+offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
+Aufbau lauten:
+\begin{itemize}
+ \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
+ \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
+ einzelnen Komparator.
+\end{itemize}
+
+Dass die resultierende Folge sortiert ist, lässt sich mit dem
+{\em 0-1-Prinzip} leicht 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:
+\begin{eqnarray}
+ \left|W_{\textrm{gerade}}\right|_0
+ &=& \left|U_{\textrm{gerade}}\right|_0
+ + \left|V_{\textrm{gerade}}\right|_0
+ = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
+ + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
+ \left|W_{\textrm{ungerade}}\right|_0
+ &=& \left|U_{\textrm{ungerade}}\right|_0
+ + \left|V_{\textrm{ungerade}}\right|_0
+ = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
+ + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
+\end{eqnarray}
+Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
+als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
+Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
+wenn $W_{\textrm{gerade}}$ $2$~Nullen mehr enthählt als
+$W_{\textrm{ungerade}}$, muss eine Vertauschung stattfinden, um die Ausgabe zu
+sortieren. Die jeweiligen Situationen sind in
+Abbildung~\ref{fig:oe-post-recursive} dargestellt.
+
+\begin{figure}
+ \centering
+ \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
+ \qquad
+ \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
+ \qquad
+ \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
+ \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
+ kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der
+ Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
+ letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
+ sortiert ist.}
+ \label{fig:oe-post-recursive}
+\end{figure}
+
+\subsubsection{Das Odd-Even-Mergesort-Netzwerk}
+
+Auch beim {\em Odd-Even-Mergesort-Netzwerk} -- wie beim {\em bitonen
+Mergesort-Netzwerk} -- entsteht das Sortiernetzwerk aus dem {\em
+Odd-Even-Mischer} durch resursives Anwenden auf einen Teil der Eingabe
+(üblicherweise die Hälfte der Leitungen) und anschließendes zusammenfügen.
+Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
\begin{figure}
\begin{center}
\subsection{Leitungen entfernen}
+\begin{figure}
+ \centering
+ \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
+ \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
+ \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
+ \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
+ \caption{Eine Leitung wird aus dem {\em Odd-Even-Transpositionsort} Netzwerk
+ $\textrm{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 herausgetrennt werden. In der
+ letzten Abbildung ist $\textrm{OET}(7)$ markiert.}
+\end{figure}
+
\begin{itemize}
\item Min-Richtung
\item Max-Richtung
projects / diplomarbeit.git / commitdiff