From cdb40e0aa0bad35e71093d34a55b31cfed7397d2 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Sun, 27 Feb 2011 09:28:08 +0100 Subject: [PATCH] Ausgeschriebene Zahlen teilweise ersetzt. Immer dann, wenn sie mit anderen Zahlen verglichen werden sollen, die nicht ausgeschrieben sind. --- diplomarbeit.tex | 38 +++++++++++++++++++------------------- 1 file changed, 19 insertions(+), 19 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index d910dbb..6a77ae3 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -155,12 +155,12 @@ Ausgänge eines Komparators mit Eingängen weiterer Komparatoren verbunden sind, erhält man ein {\em Komparatornetzwerk}. \begin{figure} -\begin{center} -\input{images/einfaches_komparatornetzwerk.tex} -\end{center} -\caption{Einfaches Komparatornetzwerk mit vier Ein- beziehungsweise Ausgängen, bestehend -aus 5~Komparatoren.} -\label{fig:einfaches_komparatornetzwerk} + \begin{center} + \input{images/einfaches_komparatornetzwerk.tex} + \end{center} + \caption{Einfaches Komparatornetzwerk mit 4~Ein- beziehungsweise Ausgängen, + bestehend aus 5~Komparatoren.} + \label{fig:einfaches_komparatornetzwerk} \end{figure} Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches @@ -205,9 +205,9 @@ zerstört. \begin{center} \input{images/09-e2-c24-allbut1.tex} \end{center} - \caption{Ein \emph{Komparatornetzwerk} mit neun Eingängen und - 24~Komparatoren, die in 8~Schichten angeordnet sind. Das Netzwerk sortiert - alle Eingaben, bei denen das Minimum nicht auf dem mittleren Eingang liegt.} + \caption{Ein \emph{Komparatornetzwerk} mit 9~Eingängen und 24~Komparatoren, + die in 8~Schichten angeordnet sind. Das Netzwerk sortiert alle Eingaben, bei + denen das Minimum nicht auf dem mittleren Eingang liegt.} \label{fig:09-e2-c24-allbut1} \end{figure} Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft {\em @@ -947,16 +947,16 @@ 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. Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(9)$ benötigt -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. -$\operatorname{OES}(18)$ benötigt 82~Komparatoren in 13~Schichten. Damit ist -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. +beispielsweise 26~Komparatoren, die in 9~Schichten angeordnet sind. Es sind +allerdings Sortiernetzwerke mit 9~Eingängen bekannt, die lediglich +25~Komparatoren in 7~Schichten benötigen. Wenn zwei dieser Netzwerke mit dem +\emph{Odd-Even}-Mischer kombiniert werden, entsteht ein 18-Sortiernetzwerk, +das aus 80~Komparatoren in 11~Schichten besteht. Damit ist 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. $\operatorname{OES}(18)$ benötigt +82~Komparatoren in 13~Schichten. Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits -- 2.11.0