SN-Evolution-Cut: PS: Tabelle und Beispiel-SN hinzugefügt.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 7f9cb23..70a7c42 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -2572,11 +2572,7 @@ effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
 
 \subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
 
-Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene
-Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war
-(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise
-ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
-wie und warum es jede beliebige Eingabe sortiert.
+% Effizienz
 
 \begin{table}
   \begin{center}
@@ -2612,9 +2608,87 @@ wie und warum es jede beliebige Eingabe sortiert.
     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-ps-efficiency}
+\end{table}
+
+% Beispiel Effizienz
+
+\begin{figure}
+  \centering
+  \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 10~Schichten. Das
+    Netzwerk wurde von \textsc{SN-Evolution-Cut} aus dem
+    \emph{Pairwise-Sorting}-Netzwerk \ps{13}
+    erzeugt.]{\input{images/11-ec-from-ps13.tex}}
+  \subfigure[12-Sortiernetzwerk aus 41~Komparatoren in 10~Schichten. Das
+    Netzwerk wurde von \textsc{SN-Evolution-Cut} aus dem
+    \emph{Pairwise-Sorting}-Netzwerk \ps{16}
+    erzeugt.]{\input{images/12-ec-from-ps16.tex}}
+  \caption{Zwei effiziente Sortiernetzwerke, die durch Schnittmuster, die von
+    \emph{SN-Evolution-Cut} berechnet wurden, aus dem
+    \emph{Pairwise-Sorting}-Netzwerk \ps{n} erzeugt wurden.}
+  \label{fig:ec-ps-efficient_networks}
+\end{figure}
+
+% Geschwindigkeit
+
+\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 &   6 &     &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+     10 &   6 &  10 &     &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+     11 &   6 &   9 &  10 &     &     &     &     &     &     &     &     &     &     &     &     &     \\
+     12 &   6 &   8 &   9 &  10 &     &     &     &     &     &     &     &     &     &     &     &     \\
+     13 &   6 &   8 &   9 &  10 &  10 &     &     &     &     &     &     &     &     &     &     &     \\
+     14 &   6 &   8 &   9 &  10 &  10 &  10 &     &     &     &     &     &     &     &     &     &     \\
+     15 &   6 &   8 &   9 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     &     &     \\
+     16 &   6 &   8 &   9 &  10 &  10 &  10 &  10 &  10 &     &     &     &     &     &     &     &     \\
+     17 &   7 &   8 &   9 &  10 &  10 &  11 &  11 &  11 &  11 &     &     &     &     &     &     &     \\
+     18 &   7 &   8 &   9 &  10 &  10 &  11 &  11 &  11 &  11 &  15 &     &     &     &     &     &     \\
+     19 &   7 &   8 &   9 &  10 &  10 &  11 &  11 &  11 &  11 &  15 &  15 &     &     &     &     &     \\
+     20 &   7 &   8 &   9 &  10 &  10 &  11 &  11 &  11 &  11 &  15 &  15 &  15 &     &     &     &     \\
+     21 &   6 &   8 &   9 &  10 &  10 &  11 &  11 &  11 &  12 &  14 &  15 &  15 &  15 &     &     &     \\
+     22 &   6 &   8 &   9 &  10 &  10 &  11 &  11 &  11 &  12 &  14 &  14 &  15 &  15 &  15 &     &     \\
+     23 &   6 &   9 &   9 &  10 &  10 &  10 &  11 &  11 &  11 &  13 &  14 &  14 &  15 &  15 &  15 &     \\
+     24 &   6 &   9 &   9 &  10 &  10 &  10 &  11 &  11 &  11 &  13 &  13 &  14 &  14 &  15 &  15 &  15 \\
+     \hline
+ \ps{m} &   6 &  10 &  10 &  10 &  10 &  10 &  10 &  10 &  10 &  15 &  15 &  15 &  15 &  15 &  15 &  15 \\
+    \hline
+    \end{tabular}
+  \end{center}
+  \caption{Anzahl der Schichten 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-ps-speed}
 \end{table}
 
+% Beispiel Geschwindigkeit
+
+\begin{figure}
+  \begin{center}
+    \input{images/18-ec-from-ps24.tex}
+  \end{center}
+  \caption{Sortiernetzwerk mit 18~Leitungen und 89~Komparatoren in
+    13~Schichten. Das Netzwerk wurde von dem Algorithmus
+    \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk
+    $\operatorname{PS}(24)$ erzeugt.}
+  \label{fig:18-ec-from-ps24}
+\end{figure}
+
+% 2-er Potenz
+
+Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene
+Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war
+(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise
+ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
+wie und warum es jede beliebige Eingabe sortiert.
+
 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