From 73495b061c2fa75855a6a068178f93c1d9948fa4 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Sat, 26 Feb 2011 13:03:10 +0100 Subject: [PATCH] =?utf8?q?SN-Evolution-Cut:=20Tabelle=20f=C3=BCr=20die=20E?= =?utf8?q?ffizient=20mit=20PS(n)=20hinzugef=C3=BCgt.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- diplomarbeit.tex | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 94f7f65..03be0ac 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -2189,6 +2189,43 @@ Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich, wie und warum es jede beliebige Eingabe sortiert. +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} +\begin{tabular}{|r|rrrrrrrrrrrrrrrr|} +\hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ +\hline + 9 & 20 & & & & & & & & & & & & & & & \\ + 10 & 20 & 27 & & & & & & & & & & & & & & \\ + 11 & 20 & 28 & 32 & & & & & & & & & & & & & \\ + 12 & 20 & 28 & 32 & 38 & & & & & & & & & & & & \\ + 13 & 19 & 27 & 31 & 37 & 41 & & & & & & & & & & & \\ + 14 & 19 & 27 & 31 & 37 & 41 & 48 & & & & & & & & & & \\ + 15 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\ + 16 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\ + 17 & 21 & 29 & 32 & 39 & 43 & 51 & 57 & 64 & 68 & & & & & & & \\ + 18 & 22 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & & & & & & \\ + 19 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & & & & & \\ + 20 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & 97 & & & & \\ + 21 & 20 & 30 & 34 & 38 & 44 & 51 & 57 & 64 & 74 & 82 & 87 & 96 & 102 & & & \\ + 22 & 20 & 30 & 34 & 38 & 46 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & & \\ + 23 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 66 & 72 & 83 & 89 & 97 & 102 & 112 & 119 & \\ + 24 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & 119 & 127 \\ +\hline +\ps{m}&19 & 27 & 32 & 38 & 42 & 48 & 53 & 59 & 63 & 79 & 88 & 97 & 103 & 112 & 119 & 127 \\ +\hline +\end{tabular} + \end{center} + \caption{Anzahl der Komparatoren der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des + \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$. + Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede + Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des + Ausgabenetzwerks.} + \label{tbl:ec-bs-fast} +\end{table} + Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992} definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit -- 2.11.0