Beste 16-SN: Umformuliert.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 98dd41e..eda81d2 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -1252,10 +1252,20 @@ die bei Sortiernetzwerken verfolgt werden können:
   \item Möglichst wenige Schichten („schnell“)
 \end{itemize}
 
-Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
-effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus
-60~Komparatoren in 10~Schichten. Das schnellste bekannte 16-Sortiernetzwerk
-besteht aus 61~Komparatoren in nur 9~Schichten.
+\begin{figure}
+  \centering
+  \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
+  \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
+  \caption{Das effizienteste und das schnellste Sortiernetzwerk für
+  16~Leitungen, das derzeit bekannt ist.}
+  \label{fig:16-best-known}
+\end{figure}
+Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken.
+Beispielsweise besteht das \emph{effizienteste} bekannte Sortiernetzwerk für
+16~Eingänge aus 60~Komparatoren in 10~Schichten. Es ist in
+Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte
+16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in
+Abbildung~\ref{fig:16-voorhis} zu sehen.
 
 Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
 berücksichtigen kann, hat die folgende allgemeine Form:
@@ -1544,6 +1554,19 @@ Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l
 \end{center}
 \end{table}
 
+\subsection{Zufälliger Mischer}
+
+Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige
+Leitungszahlen der \emph{bitone Mischer} und für andere Leitungszahlen der
+\emph{Odd-Even}-Mischer bessere Ergebnisse liefert. Beispielsweise hat das
+Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur
+12~Schichten, bei Verwendung des \emph{Odd-Even}-Mischers hingegen nur
+82~Komparatoren. Daher liegt die Idee nahe, beide Mischer-Netzwerke zu nutzen,
+um das beste Ergebnis beider Konstruktionen zu erreichen.
+\textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier
+Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem
+\emph{Odd-Even}-Mischer wählen. \todo{Daten noch in eine Tabelle einfügen.}
+
 %\input{shmoo-aequivalenz.tex}
 
 \newpage