Durch die ausführliche Tabelle ist dieser Teil jetzt doppelt.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 9434d11..6809fff 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -1661,16 +1661,16 @@ Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}}
 \hline
 \end{tabular}
 \caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
-  unter Verwendung der verschiedenen Mischer. Der Algorithmus wurde mit dem
+  unter Verwendung der beiden Mischer-Netzwerke. Der Algorithmus wurde mit dem
   \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet und nach
   2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die Konstanten
-  $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
+  $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$ und
   $w_{\mathrm{Schichten}} = n$.}
 \end{center}
 \end{table}
 
 Bei einigen Leitungszahlen kann der Algorithmus durch die Verfügbarkeit beider
-Mischer-Netzwerke Sortiernetzwerke zurückgeben, die effizienter als die
+Mi\-scher-Netzwerke Sortiernetzwerke zurückgeben, die effizienter als die
 vorherigen Ergebnisse sind. Beispielsweise ist das 19-Sortiernetzwerk in
 Abbildung~\ref{fig:19-e1-rnd-fast} mit 92~Komparatoren effizienter als die
 19-Sortiernetzwerke, die mit nur einem der beiden Mischer-Netzwerke erreicht
@@ -2174,10 +2174,12 @@ dargestellt.
   \begin{center}
     \input{images/16-ec-from-bs32.tex}
   \end{center}
-  \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
-    10~Schichten. Das Netzwerk wurde von dem Algorithmus
-    \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort-Netzwerk}
-    $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
+  \caption{Visualisierung eines 16-Schnittmusters, das von
+    \textsc{SN-Evolution-Cut} für das \emph{bitone Mergesort}-Netzwerk \bs{32}
+    berechnet wurde. Das resultierende Sortiernetzwerk besteht aus
+    68~Komparatoren in 10~Schichten und ist in
+    Abbildung~\ref{fig:16-ec-from-bs32-normalized} als
+    Standard-Sortiernetzwerk dargestellt.}
   \label{fig:16-ec-from-bs32}
 \end{figure}
 
@@ -2186,9 +2188,10 @@ dargestellt.
     \input{images/16-ec-from-bs32-normalized.tex}
   \end{center}
   \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
-    10~Schichten. Das Netzwerk wurde von dem Algorithmus
-    \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
-    $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
+    10~Schichten. Das Netzwerk wurde mit einem 16-Schnittmuster, das von
+    \textsc{SN-Evolution-Cut} berechnet wurde, aus dem \emph{bitone
+    Mergesort}-Netzwerk \bs{32} erzeugt. Das Schnittmuster ist in
+    Abbildung~\ref{fig:16-ec-from-bs32} dargestellt.}
   \label{fig:16-ec-from-bs32-normalized}
 \end{figure}
 
@@ -2406,14 +2409,23 @@ $k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des
       27  &  91 & 14 \\
       28  &  91 & 14 \\
       29  &  95 & 13 \\
+      \rowcolor{green!10}
       30  &  93 & 13 \\
+      \rowcolor{green!10!white!95!black}
       31  &  93 & 13 \\
+      \rowcolor{green!10}
       32  &  93 & 13 \\
+      \rowcolor{green!10!white!95!black}
       33  &  93 & 13 \\
+      \rowcolor{green!10}
       34  &  93 & 13 \\
+      \rowcolor{green!10!white!95!black}
       35  &  93 & 13 \\
+      \rowcolor{green!10}
       36  &  93 & 13 \\
+      \rowcolor{green!10!white!95!black}
       37  &  93 & 13 \\
+      \rowcolor{green!10}
       38  &  93 & 13 \\
       \hline
  \bs{19}  &  98 & 14 \\
@@ -2536,48 +2548,6 @@ angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie
   \label{fig:12-ec-from-oes24}
 \end{figure}
 
-Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut}
-findet Sortiernetzwerke, die schneller sind als das entsprechende
-\emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das Sortiernetzwerke mit
-22, 24, 38, 40, 42, 44 und 46 Leitungen. In der folgenden Tabelle sind einige
-schnelle Netzwerke, die von \textsc{SN-Evolution-Cut} generiert werden können,
-charakterisiert. Die Eingabe für \textsc{SN-Evolution-Cut} war jeweils das
-\emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl.
-\begin{center}
-\begin{tabular}{|r|r|r|r|r|}
-\hline
-Leitungen  & Komparatoren   & Schichten      & Komparatoren & Schichten \\
-           & \textsc{SN-EC} & \textsc{SN-EC} &      \oes{n} &   \oes{n} \\
-\hline
-11 &  38 &  9 &  37 & 10 \\
-12 &  43 &  9 &  41 & 10 \\
-19 &  93 & 13 &  91 & 14 \\
-20 & 101 & 13 &  97 & 14 \\
-21 & 108 & 14 & 107 & 15 \\
-22 & 116 & 14 & 114 & 15 \\
-23 & 125 & 14 & 122 & 15 \\
-\hline
-\end{tabular}
-\end{center}
-Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
-23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem
-Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der
-Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In
-beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu
-\bs{23} beziehungsweise \oes{23} eine Schicht einspart.
-
-\begin{figure}
-  \begin{center}
-    \input{images/23-ec-from-oes46-fast.tex}
-  \end{center}
-  \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten. 
-    Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem
-    Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38,
-    44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$
-    erzeugt.}
-  \label{fig:23-ec-from-oes46}
-\end{figure}
-
 \subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
 
 Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene