Tabelle "tbl:ec-bs-fast" eingefügt.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index f32ec1b..94f7f65 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -1825,6 +1825,18 @@ invertieren.
 \subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
 \label{sect:sn-evolution-cut:bs}
 
+\begin{figure}
+  \begin{center}
+    \input{images/16-ec-from-bs22.tex}
+  \end{center}
+  \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
+    10~Schichten. Das Netzwerk wurde von dem Algorithmus
+    \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk
+    $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4,
+    10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.}
+  \label{fig:16-ec-from-bs22}
+\end{figure}
+
 \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
 wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
 durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen
@@ -1979,8 +1991,44 @@ Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur
 haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere
 von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
 \emph{Odd-Even-Transpositionsort-Netzwerk} $\operatorname{OET}(n)$ und
-$m$~Schnitten gestartet, so ist das beste Ergebnis immer das
-$\operatorname{OET}(n-m)$-Netzwerk. 
+$k$~Schnitten gestartet, so ist das beste Ergebnis immer das
+$\operatorname{OET}(n-k)$-Netzwerk. 
+
+\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  & 21 &    &    &    &    &    &    &    &    &    &    &    &     &     &     &     \\
+    10 & 20 & 27 &    &    &    &    &    &    &    &    &    &    &     &     &     &     \\
+    11 & 20 & 27 & 32 &    &    &    &    &    &    &    &    &    &     &     &     &     \\
+    12 & 20 & 26 & 32 & 39 &    &    &    &    &    &    &    &    &     &     &     &     \\
+    13 & 20 & 26 & 32 & 39 & 45 &    &    &    &    &    &    &    &     &     &     &     \\
+    14 & 20 & 26 & 32 & 39 & 45 & 53 &    &    &    &    &    &    &     &     &     &     \\
+    15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 &    &    &    &    &    &     &     &     &     \\
+    16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 &    &    &    &    &     &     &     &     \\
+    17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 &    &    &    &     &     &     &     \\
+    18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 &    &    &     &     &     &     \\
+    19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 &    &     &     &     &     \\
+    20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 &     &     &     &     \\
+    21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 &     &     &     \\
+    22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 &     &     \\
+    23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 &     \\
+    24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\
+    \hline
+\bs{n} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\
+    \hline
+    \end{tabular}
+  \end{center}
+  \caption{Anzahl der Komparatoren der Ergebnisse des
+    \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
+    Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
+    die Ergebnisse für ein Eingabenetzwerk \bs{n} an, die Spalten
+    repräsentieren die Anzahl der Leitungen des Ausgabenetzwerks.}
+  \label{tbl:ec-bs-fast}
+\end{table}
 
 \subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
 \label{sect:sn-evolution-cut:oes}