From 0d8a350659881f5539c35b49151e6578620dc719 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Thu, 17 Mar 2011 23:52:32 +0100 Subject: [PATCH] =?utf8?q?Tabelle=20tbl:ec-ps-32=20eingef=C3=BCgt.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- diplomarbeit.tex | 63 ++++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 48 insertions(+), 15 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 2a8eff5..e9203fb 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -426,9 +426,7 @@ zusammenfügen). Da der Begriff des "`mischens"' beziehungsweise der "`Mischer"' in der Literatur sehr weit verbreitet ist, werden diese Begriffe in dieser Arbeit trotzdem verwendet.}, bilden die Grundlage für die beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale -Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt. - -\todo{Drei oder vier Verfahren? Sprich: Mit oder ohne Pairwise Sorting.} +Eingabe. Im Folgenden werden daher drei Konstruktionsverfahren vorgestellt. \subsection{Das Odd-Even-Transpositionsort-Netzwerk} \label{sect:odd_even_transpositionsort} @@ -2722,7 +2720,39 @@ besonders effizient und schnell. Um der Vermutung nachzugehen, dass der \textsc{SN-Evolution-Cut}-Algorithmus für $\ps{n = 2^d}$ besonders effiziente Schnittmuster findet, wurde \textsc{SN-Evolution-Cut} mit \ps{32} und $k = 1 \dots 16$ gestartet. Die Ergebnisse sind in Tabelle~\ref{tbl:ec-ps-32} -zusammengefasst. \todo{Tabelle einfügen.} +zusammengefasst. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|r|r|} + \hline + $m$ & Komp. & Schichten \\ + \hline + 16 & 69 & 11 \\ + 17 & 77 & 13 \\ + 18 & 89 & 13 \\ + 19 & 91 & 14 \\ + 20 & 97 & 14 \\ + 21 & 107 & 15 \\ + 22 & 114 & 15 \\ + 23 & 122 & 15 \\ + 24 & 127 & 15 \\ + 25 & 138 & 15 \\ + 26 & 146 & 15 \\ + 27 & 155 & 15 \\ + 28 & 161 & 15 \\ + 29 & 171 & 15 \\ + 30 & 178 & 15 \\ + 31 & 186 & 15 \\ + \hline + \end{tabular} + \end{center} + \caption{Anzahl der Komparatoren und Schichten von $m$-Sortiernetzwerken, + die von \textsc{SN-Evolution-Cut} nach 5.000.000 Iterationen aus \ps{32} + erzeugt wurden.} + \label{tbl:ec-ps-32} +\end{table} % Geschwindigkeit @@ -2796,10 +2826,12 @@ wie und warum es jede beliebige Eingabe sortiert. Bei dem \emph{Pairwise-Sorting}-Netzwerk $\ps{n=2^d}$ ist das anders. Startet man \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe, -16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, das die gleiche -Anzahl Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und -$\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in -Abbildung~\ref{fig:16-ec-from-ps32} dargestellt. +16~Leitungen zu entfernen, kann der Algorithmus ein Sortiernetzwerk +zurückgeben, das die gleiche Anzahl Komparatoren und Schichten wie +$\operatorname{PS}(16)$ und $\operatorname{OES}(16)$ hat. Eines dieser +Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt. +Dieses Ergebnis demonstriert, dass sich die Ergebnisse in den gezeigten +Tabellen oft durch zusätzliche Iterationen verbessern lassen. \begin{figure} \begin{center} @@ -2862,13 +2894,14 @@ Netzwerk in schwarz gut zu erkennen. \label{fig:16-pairwise} \end{figure} -Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf -$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein -8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für -größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise -kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16} -konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n} -untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}. +Ein Spezialfall ergibt sich, wenn \textsc{SN-Evolution-Cut} auf +$\operatorname{PS}(16)$ angewendet wird: In diesem Fall kann ein +8-Schnittmuster ausgegeben werden, das \emph{Odd-Even-Mergesort}-Netzwerk +\oes{8} aus \ps{16} erzeugt.. Für größere Sortiernetzwerke ist dies hingegen +nicht mehr möglich, beispielsweise kann $\operatorname{PS}(32)$ nicht durch +ein 16-Schnittmuster in \oes{16} konvertiert werden. Die Verwandtschaft von +$\operatorname{PS}(n)$ und \oes{n} untersucht \textit{Moritz Mühlenthaler} +ausführlich in~\cite{M2009}. \newpage \section{Fazit und Ausblick} -- 2.11.0