SN-Evolution-Cut: Tabelle für die Effizient mit PS(n) hinzugefügt.

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 94f7f65..03be0ac 100644 (file)
--- 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