From 8e1104c3736e37c8471a3da2dd57a286cbc58e90 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Thu, 24 Feb 2011 21:45:19 +0100 Subject: [PATCH] Korrekturen. --- diplomarbeit.tex | 138 +++++++++++++++++++++++++++---------------------------- 1 file changed, 69 insertions(+), 69 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 65c583e..d23a996 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -154,7 +154,7 @@ erhält man ein {\em Komparatornetzwerk}. \begin{center} \input{images/einfaches_komparatornetzwerk.tex} \end{center} -\caption{Einfaches Komparatornetzwerk mit vier Ein- bzw. Ausgängen, bestehend +\caption{Einfaches Komparatornetzwerk mit vier Ein- beziehungsweise Ausgängen, bestehend aus 5~Komparatoren.} \label{fig:einfaches_komparatornetzwerk} \end{figure} @@ -456,8 +456,8 @@ Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n (n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind. Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren, -($\mathcal{\Theta}(n \log (n)^2)$), die in weniger Schichten, -($\mathcal{\Theta}(\log (n)^2)$), angeordnet sind. +($\Theta(n \log (n)^2)$), die in weniger Schichten, +($\Theta(\log (n)^2)$), angeordnet sind. Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der folgenden Algorithmen benötigen ein möglichst einfaches Sortiernetzwerk als @@ -500,7 +500,7 @@ die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für das Abbildungen~\ref{fig:beispiel-biton-0} und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und eine absteigend sortierte Liste aneinanderhängt. Bei den anderen beiden Formen ist wichtig zu beachten, dass -das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) bzw. +das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) beziehungsweise kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein darf. @@ -610,8 +610,8 @@ grün hinterlegt. Das \emph{bitone Mergesort}-Netzwerk mit einer Leitungszahl $n = 2^d$, die eine Zweierpotenz ist, besteht aus $\frac{1}{4} n \log(n) \log(n+1) = -\mathcal{\Theta}\left(n (log (n))^2\right)$ Komparatoren, die in $\frac{1}{2} -\log(n) \log(n+1) = \mathcal{\Theta}(\log(n)^2)$ Schichten angeordnet sind. +\Theta\left(n (log (n))^2\right)$ Komparatoren, die in $\frac{1}{2} +\log(n) \log(n+1) = \Theta(\log(n)^2)$ Schichten angeordnet sind. \subsection{Das Odd-Even-Mergesort-Netzwerk} @@ -627,7 +627,7 @@ darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist. \subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer} Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein -Komparatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$ +Komparatornetzwerk, das zwei sortierte Folgen mit $n$ beziehungsweise $m$ Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer} @@ -668,7 +668,7 @@ geraden Indizes und je eine Liste der ungeraden Indizes. V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right) \end{eqnarray} -Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ +Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$, beziehungsweise die ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden rekursiv von kleineren \emph{Odd-Even}-Mischern zusammengefügt, so dass sich am Ausgang der Mischer die Folgen @@ -697,14 +697,14 @@ Aufbau lauten: einzelnen Komparator. \end{itemize} -Dass die resultierende Folge sortiert ist, lässt sich mit dem -{\em 0-1-Prinzip} 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: +Mit dem {\em 0-1-Prinzip} lässt sich zeigen, sass die resultierende Folge +sortiert ist. Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den +geraden Teilfolgen $U_{\textrm{gerade}}$, beziehungsweise +$V_{\textrm{gerade}}$ größer oder gleich der Anzahl der Nullen in den +ungeraden Teilfolgen $U_{\textrm{ungerade}}$ beziehungsweise +$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 @@ -722,8 +722,8 @@ 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}}$ zwei Nullen mehr enthält als $W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die -Ausgabe zu sortieren. Diese wird von den Komparatoren, die benachbarte -Leitungen miteinander vergleichen, ausgeführt. Die jeweiligen Situationen sind +Ausgabe zu sortieren. Diese wird von den Komparatoren ausgeführt, die +benachbarte Leitungen miteinander vergleichen. Die jeweiligen Situationen sind in Abbildung~\ref{fig:oe-post-recursive} dargestellt. \begin{figure} @@ -744,12 +744,12 @@ in Abbildung~\ref{fig:oe-post-recursive} dargestellt. Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden, bricht die Rekursion nach $\mathcal{O}\left(\log (n) + \log (m)\right)$ Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit -Schichten im Mischer-Netzwerk), hängt von der Längeren der beiden +Schichten im Mischer-Netzwerk), hängt von der längeren der beiden Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$. Die Anzahl der Komparatoren $K(n,m)$, die $\operatorname{OEM}(n,m)$ im -allgemeinen Fall verwendet, ist Gemäß der rekursiven Definition in -Abhängigkeit der Länge der Eingabefolgen, $n$ und $m$: +allgemeinen Fall verwendet, hängt gemäß der rekursiven Definition von der +Länge der Eingabefolgen, $n$ und $m$ ab: \begin{displaymath} K(n,m) = \left\{ \begin{array}{ll} nm, & \mathrm{falls} \quad nm \leqq 1 \\ @@ -762,12 +762,12 @@ Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar, dass $K(n,m)$ in $\mathcal{O}(N \log (N))$ enthalten ist. -Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$, lässt sich die Anzahl -der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der erste -Rekursionsschritt der OEM-Konstruktion fügt +Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die +Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der +erste Rekursionsschritt der OEM-Konstruktion fügt $\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$ Komparatoren ein -- einen Komparator weniger als der \emph{bitone Mischer} in -diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer, +diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer $\operatorname{OEM}(\frac{n}{2}, \frac{n}{2})$ und so weiter bis einschließlich $\operatorname{OEM}(2, 2)$, von denen es $2, 4, \dots, \frac{N}{4} = 2^{\log(N)-2}$ Instanzen gibt. Insgesamt werden @@ -783,8 +783,8 @@ benötigt werden. \subsubsection{Das Odd-Even-Mergesort-Netzwerk} -Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ besteht --~wie -das \emph{bitone 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 Bezug auf Komparator- und Schichtzahl entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht @@ -806,24 +806,25 @@ die als leere Komparatornetzwerke definiert sind. \label{fig:odd-even-mergesort-08} \end{figure} -In Abbildung~\ref{fig:odd-even-mergesort-08} ist das konkrete Sortiernetzwerk -$\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven -Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den -\emph{Odd-Even}-Mischer für acht Leitungen dar: Die beiden blauen Blöcke sind +In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk +zu sehen. Rot markiert sind die beiden rekursiven Instanzen +$\operatorname{OES}(4)$. Die anderen Blöcke stellen den +\emph{Odd-Even}-Mischer für acht Leitungen dar: die beiden blauen Blöcke sind die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden. Im Allgemeinen ist die Anzahl der Komparatoren, die vom \emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der -Definition beziehungsweise der Konstruktionsanleitung abzulesen: +Definition, beziehungsweise der Konstruktionsanleitung abzulesen: \begin{displaymath} k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right) + k\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + K\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor\right) \end{displaymath} -Eine geschlossene Form dieser Formel ist schon alleine deshalb schwierig, weil -sie für $K(n,m)$ schwierig anzugeben ist. Es ist allerdings bekannt, dass -$k(n)$ in $\mathcal{O}\left(n \left(\log (n)\right)^2\right)$ enthalten ist. +Da es schwierig ist für $K(n,m)$ eine geschlossene Form anzugeben, ist eine +geschlossene Darstellung von $k(n)$ ebenfalls nicht ohne weiteres möglich. Es +ist allerdings bekannt, dass $k(n)$ in $\Theta\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{Kenneth @@ -860,14 +861,13 @@ das \emph{Odd-Even-Mergesort}-Netzwerk. Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können gleichzeitig ausgewertet werden, wie bereits in Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Durch manche -Transformationen, insbesondere das Entfernen einer Leitung, das in -Abschnitt~\ref{sect:leitungen_entfernen} beschrieben wird, kann es vorkommen, -dass die Komparatoren eines Sortiernetzwerks nicht mehr in der -kleinstmöglichen Anzahl von \emph{Schichten} angeordnet sind. Unter -\emph{Komprimierung} wird eine (Neu-)Gruppierung der Komparatoren verstanden, -die jeden Komparator so früh wie möglich ausführt. So entsteht die -kleinstmögliche Anzahl von \emph{Schichten}, in die sich ein Sortiernetzwerk -unterteilen lässt. +Transformationen, insbesondere das Entfernen einer Leitung wie in +Abschnitt~\ref{sect:leitungen_entfernen} beschrieben, kann es vorkommen, dass +die Komparatoren eines Sortiernetzwerks nicht mehr in der kleinstmöglichen +Anzahl von \emph{Schichten} angeordnet sind. Unter \emph{Komprimierung} wird +eine (Neu-)Gruppierung der Komparatoren verstanden, die jeden Komparator so +früh wie möglich ausführt. So entsteht die kleinstmögliche Anzahl von +\emph{Schichten}, in die sich ein Sortiernetzwerk unterteilen lässt. Diese Anzahl ist insbesondere beim automatisierten Bewerten von Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung} @@ -897,17 +897,17 @@ der obersten Leitung ausgegeben.} Jedes Sortiernetzwerk kann in eine normaliesierte Variante transformiert werden. Dazu gibt beispielsweise \emph{Donald~E. Knuth} in~\cite{KNUTH} einen Algorithmus an. -Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das \emph{bitone -Mergesort}-Netzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd} +Abbildung~\ref{fig:beispiel_normalisieren} stellt das \emph{bitone +Mergesort}-Netzwerk in zwei Varianten dar. Abbildung~\ref{fig:bitonic-nonstd} zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden -die untere und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei -Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist. -In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven -Definition. +die untere und die obere Hälfte gegenläufig sortiert. Das heißt, dass nach +drei Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert +ist. In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der +rekursiven Definition. In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen -Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche +Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die selbe Richtung. Statt dem typischen „Treppenmuster“ sind abwechselnd das Treppen- und das Trichtermuster zu sehen. @@ -917,7 +917,7 @@ Um Sortiernetzwerke als \emph{Individuen} evolutionärer Algorithmen verwenden zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen Sortiernetzwerk zusammenzufassen. -Wir haben diese Technik in den vorangegangen Abschnitten bereits verwendet, +Diese Technik wurde in den vorangegangen Abschnitten bereits verwendet, beispielsweise um zwei \emph{bitone Mergesort}-Netzwerke mit jeweils der halben Leitungszahl, $\operatorname{BS}\left(\frac{n}{2}\right)$, zu einem einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das @@ -925,29 +925,29 @@ einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das und Weise rekursiv aufgebaut. Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte -Folgen. \emph{Wie} diese Folgen sortiert wurden, ist unerheblich. Entsprechend +Folgen. \emph{Wie} diese Folgen sortiert wurden ist unerheblich. Entsprechend können wir beliebige Sortiernetzwerke einsetzen, um die beiden Eingabefolgen -zu sortieren, und die Ausgaben mit einem der beschriebenen Mischer +zu sortieren und die Ausgaben mit einem der beschriebenen Mischer zusammenfügen. -Beispielsweise kann man die Ausgabe von zwei \emph{bitonen -Mergesort-Netzwerken} $\operatorname{BS}(8)$ mit je acht Leitungen mit dem +Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken} +$\operatorname{BS}(8)$ mit je acht Leitungen mit dem \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten -Gesamtfolge zusammenfügen. Das resultierende Sortiernetzwerk besitzt +Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt 80~Komparatoren, $\operatorname{OES}(16)$ nur 63). -Verbesserungen der Effizienz (die Anzahl der benötigten Komparatoren) +Verbesserungen der Effizienz (die Anzahl der benötigten Komparatoren), beziehungsweise der Geschwindigkeit (die Anzahl der Schichten) eines „kleinen“ -Sortiernetzwerks übertragen sich direkt auf das resultierende Gesamtnetzwerk. +Sortiernetzwerks, übertragen sich direkt auf das resultierende Gesamtnetzwerk. Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(9)$ benötigt -beispielsweise 26~Komparatoren, die in in neun Schichten angeordnet sind. Es -sind allerdings Sortiernetzwerke mit neun Eingängen bekannt, die lediglich +beispielsweise 26~Komparatoren, die in neun Schichten angeordnet sind. Es sind +allerdings Sortiernetzwerke mit neun Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten benötigen. Kombiniert man zwei dieser Netzwerke mit dem \emph{Odd-Even}-Mischer erhält man ein Sortiernetzwerk mit -18~Eingängen, das 80~Komparatoren in 11~Schichten benötigt -- +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 +das resultierende Netzwerk genauso 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. @@ -964,22 +964,22 @@ nur mit exponentiellem Aufwand möglich ist. \subsection{Leitungen entfernen} \label{sect:leitungen_entfernen} -Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von -\emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen +Im vorherigen Abschnitt wurde gezeigt, dass es mithilfe von \emph{Mischern} +möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass -sich die Anzahl der Eingänge nicht verändert. Das heißt, dass wir wieder ein -Sortiernetzwerk mit $n$~Eingängen erhalten müssen. +sich die Anzahl der Eingänge nicht verändert. Es soll wieder ein +Sortiernetzwerk mit $n$~Eingängen entstehen. Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung -„eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem +„eliminiert“. Dazu wird angenommen, dass das Minimum oder das Maximum an einem bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maximum durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an einem der „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten Index. Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und -welche dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum -jeden Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die +welche dafür sorgen, dass der Wert die Leitung wechselt, da das Minimum jeden +Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch das \emph{Odd-Even-Transpositionsort}-Netzwerk. -- 2.11.0