From 23e4242936016962fe3be68c8f532022243fa9ef Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Tue, 24 Nov 2009 13:57:40 +0100 Subject: [PATCH] =?utf8?q?Gesch=C3=BCtzte=20Leerzeichen=20verwendet=20wo?= =?utf8?q?=20sinnvoll.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- diplomarbeit.tex | 16 +++++++++------- 1 file changed, 9 insertions(+), 7 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 63c76d5..980d052 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -299,13 +299,15 @@ Muster nun an einen Trichter. \subsubsection{Batcher's Bitonic-Mergesort-Netzwerk} Das Sortiernetzwerk $S(n)$ mit $n$~Eingängen besteht aus zwei Instanzen von -$S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen, und dem bitonen -Mischer $M(n)$. Die Rekursion bricht bei ${n = 1}$~ab -- eine einelementige +$S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen und dem bitonen +Mischer~$M(n)$. Die Rekursion bricht bei ${n = 1}$~ab --~eine einelementige Liste ist immer sortiert. Das konkrete Netzwerk~$S(8)$ ist in Abbildung~\ref{fig:batcher_08} zu sehen. Eingezeichnet sind ebenfalls die beiden Instanzen des Netzwerks~$S(4)$ (rot) sowie der bitone Mischer~$M(8)$ (blau). + + %\begin{figure} %\begin{center} %\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf} @@ -407,7 +409,7 @@ Dass die resultierende Folge sortiert ist, lässt sich mit dem 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 +$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} @@ -447,9 +449,9 @@ Abbildung~\ref{fig:oe-post-recursive} dargestellt. \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 +Auch beim \emph{Odd-Even-Mergesort-Netzwerk} --~wie beim \emph{bitonen +Mergesort-Netzwerk}~-- entsteht das Sortiernetzwerk aus dem {\em +Odd-Even-Mischer} durch rekursives 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. @@ -577,7 +579,7 @@ Exploitation}, das Finden lokaler Optima, bevorzugt. \subsection{Rekombination} -Bei der Rekombination werden zwei Individuen -- hier Sortiernetzwerke -- zu +Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den {\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die -- 2.11.0