Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
Komplexitätsklasse
-$\mathcal{O}\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
-ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\mathcal{O}(2^n)$
+$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
+ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(2^n)$
verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,
Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die
Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen
sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n
-(n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind.
+(n-1)} = \Theta(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind.
Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren,
($\Theta(n \log (n)^2)$), die in weniger Schichten,
($\Theta(\log (n)^2)$), angeordnet sind.
Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
$\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus
-$\frac{1}{2} n \log(n) = \mathcal{O}\left(n \log(n)\right)$~Komparatoren
+$\frac{1}{2} n \log(n) = \Theta\left(n \log(n)\right)$~Komparatoren
besteht, die in $\log(n)$~Schichten angeordnet werden können.
\subsubsection{Das bitone Mergesort-Netzwerk}
\end{figure}
Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,
-bricht die Rekursion nach $\mathcal{O}\left(\log (n) + \log (m)\right)$
+bricht die Rekursion nach $\Theta\left(\log (n) + \log (m)\right)$
Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
Schichten im Mischer-Netzwerk), hängt von der längeren der beiden
Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.
\end{displaymath}
Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
-dass $K(n,m)$ in $\mathcal{O}(N \log (N))$ enthalten ist.
+dass $K(n,m)$ in $\Theta(N \log (N))$ enthalten ist.
Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die
Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
\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:
Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
\emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind.
Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht
-wiederholen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung
-des \emph{Odd-Even}-Mischers findet, erreichen das
+erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
+\emph{Odd-Even-Merge}-Netzwerks findet, erreichen das
\emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
-Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Wenn $n$ keine
-Zweierpotenz ist, kann \textsc{SN-Evolution} unter Umständen Sortiernetzwerke
-ausgeben, die schneller als \oes{n} sind.
+Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen.
+
+Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch
+mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution}
+Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht
+beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt
+\textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen.
+\oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der
+Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet
+sich in Tabelle~\ref{tbl:sn-ev-oem-fast}.
%\begin{figure}
%\begin{center}
%\label{fig:10-e2-1239014566}
%\end{figure}
+\begin{table}\label{tbl:sn-ev-oem-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\
+\cline{2-5}
+ & Komp. & Schichten & Komp. & Schichten \\
+\hline
+ 8 & 19 & 6 & 19 & 6 \\
+ 9 & 26 & 8 & 26 & 8 \\
+ 10 & 31 & 9 & 31 & 9 \\
+ 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\
+ 12 & 43 & \gcell 9 & \gcell 41 & 10 \\
+ 13 & 48 & 10 & 48 & 10 \\
+ 14 & 53 & 10 & 53 & 10 \\
+ 15 & 59 & 10 & 59 & 10 \\
+ 16 & 63 & 10 & 63 & 10 \\
+ 17 & 74 & 12 & 74 & 12 \\
+ 18 & 82 & 13 & 82 & 13 \\
+ 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\
+ 20 & 97 & 14 & 97 & 14 \\
+ 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\
+ 22 & 117 & \gcell 14 & \gcell 114 & 15 \\
+ 23 & 129 & \Gcell 14 & \Gcell 122 & 15 \\
+ 24 & 128 & 15 & \gcell 127 & 15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+ unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. 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{Schichten}} = n$.}
+\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.
+
+Die Ergebnisse von \textsc{SN-Evolution} bei einer zufälligen Wahl des
+Mischers in der Rekombinationsphase sind in Tabelle~\ref{tbl:sn-ev-rnd-fast}
+zusammengefasst. Bei den Leitungszahlen 12, 19, 21, 22 und 23 hat der
+Algorithmus Netzwerke mit einer Effizienz erzeugt, die mit nur einem
+Mischertyp nicht erreicht wurde. Die Ergebnisse mit den Leitungszahlen 18 und
+20 erreichen die Geschwindigkeit der Netzwerke, die mit dem \emph{bitonen
+Mischer} generiert wurden, und verbessern gleichzeitig die Effizienz.
+
+\begin{table}\label{tbl:sn-ev-rnd-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}}
+ & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}}
+ & \multicolumn{2}{l|}{\textsc{SN-EV} mit Zufall} \\
+\cline{2-7}
+ ($n$) & Komp. & Schichten & Komp. & Schichten & Komp. & Schichten \\
+\hline
+ 8 & 20 & 6 & \gcell 19 & 6 & \gcell 19 & 6 \\
+ 9 & 26 & 8 & 26 & 8 & 26 & 8 \\
+ 10 & 31 & \gcell 8 & 31 & 9 & 31 & \gcell 8 \\
+ 11 & \Gcell 37 & 9 & 38 & 9 & \Gcell 37 & 9 \\
+ 12 & 42 & 9 & 43 & 9 & \gcell 41 & 9 \\
+ 13 & 48 & 10 & 48 & 10 & 48 & 10 \\
+ 14 & 54 & 10 & \gcell 53 & 10 & \gcell 53 & 10 \\
+ 15 & 61 & 10 & \Gcell 59 & 10 & \Gcell 59 & 10 \\
+ 16 & 67 & 10 & \gcell 63 & 10 & 64 & 10 \\
+ 17 & 76 & 12 & \Gcell 74 & 12 & \Gcell 74 & 12 \\
+ 18 & 87 & \gcell 12 & \gcell 82 & 13 & 83 & \gcell 12 \\
+ 19 & 93 & 13 & 93 & 13 & \Gcell 92 & 13 \\
+ 20 & 104 & \gcell 13 & \gcell 97 & 14 & 101 & \gcell 13 \\
+ 21 & 109 & 14 & 108 & 14 & \Gcell 107 & 14 \\
+ 22 & 118 & 14 & 117 & 14 & \gcell 116 & 14 \\
+ 23 & 134 & 14 & 129 & 14 & \Gcell 128 & 14 \\
+ 24 & 133 & 15 & \gcell 128 & 15 & 130 & 15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+ unter Verwendung der verschiedenen Mischer. 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{Schichten}} = n$.}
+\end{center}
+\end{table}
+
%\input{shmoo-aequivalenz.tex}
\newpage
projects / diplomarbeit.git / blobdiff