From d8398b82efd25687be807b29a3c78315d3e31882 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Thu, 24 Feb 2011 20:00:36 +0100 Subject: [PATCH] Fehler--; Stil++; --- diplomarbeit.tex | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index be7e364..65c583e 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -491,10 +491,10 @@ Es ist jedoch möglich, das Sortiernetzwerk für beliebige~$n$ zu erzeugen. Das \emph{bitone Mergesort}-Netzwerk basiert auf dem sogenannten \emph{bitonen Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine -beliebige \emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine -\emph{bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton -absteigenden Folge, oder ein zyklischer Shift davon. -Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinzipiellen Möglichkeiten +beliebige \emph{bitone Folge} in eine sortierte Liste umordnen kann. Eine +\emph{bitone Folge} ist eine monoton steigende Folge, gefolgt von einer +monoton absteigenden Folge, oder ein zyklischer Shift davon. +Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinzipiellen Möglichkeiten, die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für das \emph{bitone Mergesort}-Netzwerk zeigen die Abbildungen~\ref{fig:beispiel-biton-0} und~\ref{fig:beispiel-biton-1}. Sie @@ -545,9 +545,9 @@ Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$ gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1} > v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$ vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der -"`linken"' Folge, $u_{m-1}$, kleiner ist als das kleinste Element der -"`rechten"' Folge, $v_{m-1}$. Daraus folgt, dass das Resultat in zwei bitone -Folgen aufteilen lässt: Eine aufsteigende~/ absteigende Folge und eine +"`linken"' Folge $u_{m-1}$ kleiner ist als das kleinste Element der +"`rechten"' Folge $v_{m-1}$. Daraus folgt, dass sich das Resultat in zwei +bitone Folgen aufteilen lässt: Eine aufsteigende~/ absteigende Folge und eine absteigende~/ aufsteigende Folge. Abbildung~\ref{fig:bitonic-merge-normal} zeigt die Situationen vor und nach diesem Schritt des Mischers schematisch. @@ -577,10 +577,10 @@ besteht, die in $\log(n)$~Schichten angeordnet werden können. Ebenso wie der bitone Mischer $\operatorname{BM}(n)$ ist auch das \emph{bitone Mergesort-Netzwerk} $\operatorname{BS}(n)$ rekursiv definiert. Es setzt sich -zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe, -\bs{\frac{n}{2}}, für je die Hälfte der Eingänge, sowie dem bitonen Mischer -für $n$~Leitungen, $\operatorname{BM}(n)$. Das Rekursionsende ist das bitone -Mergesort-Netzwerk mit nur einer Leitung, $\operatorname{BS}(1)$, welches als +zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe +$\bs{\frac{n}{2}}$ für je die Hälfte der Eingänge, sowie dem bitonen Mischer +für $n$~Leitungen $\operatorname{BM}(n)$. Das Rekursionsende ist das bitone +Mergesort-Netzwerk mit nur einer Leitung $\operatorname{BS}(1)$, welches als leeres Komparatornetzwerk definiert ist. Entsprechend sind die Komparatornetzwerke $\operatorname{BM}(2)$ und $\operatorname{BS}(2)$ identisch. @@ -601,7 +601,7 @@ alle Komparatoren in die gleiche Richtung zeigen. \label{fig:bitonic-08} \end{figure} -Das konkrete Netzwerk~$\operatorname{BS}(8)$ ist in +Das Sortiernetzwerk~$\operatorname{BS}(8)$ ist in 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, -- 2.11.0