From 722308a3028582c1c3f88a17e3d21cb718f4084b Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Thu, 2 Apr 2009 22:57:54 +0200 Subject: [PATCH] diplomarbeit.tex: Todays work. --- diplomarbeit.tex | 177 +++++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 160 insertions(+), 17 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 38c4c56..7652e83 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -44,7 +44,7 @@ \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,<-] @@ -52,6 +52,11 @@ \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 @@ -133,6 +138,11 @@ können?} \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$ @@ -167,9 +177,9 @@ als {\em Individuum} bezeichnet. 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 @@ -199,7 +209,7 @@ Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der 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} @@ -214,8 +224,9 @@ ${n = 8}$. 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 @@ -244,12 +255,12 @@ darf. \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} @@ -305,24 +316,142 @@ sowie der bitone Mischer~$M(8)$ (blau). %\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} @@ -356,6 +485,20 @@ Beispiel: Siehe Abbildung~\ref{fig:odd_even_mergesort_08}. \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 -- 2.11.0