X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=5b660971a1449cdbf84007d524b151c0b502a800;hb=be3bbadf49d9c924fb967e198f90d9f162e90571;hp=6cd40785ebfa38f7dd1031d40839d8cbc2222b37;hpb=8fc2876c1eb49652c1e1a897b4cd4617fae96094;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 6cd4078..5b66097 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -9,6 +9,7 @@ \usepackage{listings} \usepackage{graphicx} \usepackage{url} +\usepackage[table]{xcolor} %\usepackage{longtable} \usepackage{subfigure} \usepackage{icomma} @@ -43,6 +44,9 @@ \newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}} \newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}} +\newcommand{\gcell}{\cellcolor{green!10}} +\newcommand{\Gcell}{\cellcolor{green!10!white!95!black}} + \newtheorem{definition}{Definition} \newtheorem{satz}{Satz} @@ -266,8 +270,8 @@ Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden. 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, @@ -454,7 +458,7 @@ $\operatorname{OET}(3)$ sortiert. 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. @@ -570,7 +574,7 @@ Statt an eine Treppe erinnert das Muster nun an einen Trichter. 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} @@ -697,7 +701,7 @@ Aufbau lauten: einzelnen Komparator. \end{itemize} -Mit dem {\em 0-1-Prinzip} lässt sich zeigen, sass die resultierende Folge +Mit dem {\em 0-1-Prinzip} lässt sich zeigen, dass die resultierende Folge sortiert ist. Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden Teilfolgen $U_{\textrm{gerade}}$, beziehungsweise $V_{\textrm{gerade}}$ größer oder gleich der Anzahl der Nullen in den @@ -742,7 +746,7 @@ in Abbildung~\ref{fig:oe-post-recursive} dargestellt. \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$. @@ -760,7 +764,7 @@ Länge der Eingabefolgen, $n$ und $m$ ab: \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 @@ -1158,10 +1162,10 @@ die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster vernachlässigbar klein ist. Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses -Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar. -Die Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen -Rechnern vorhanden ist, bevor ein entsprechender Graph den linearen Bereich -für „kleine“ x-Werte verlässt. +Experiment für größere Sortiernetzwerke nicht sinnvoll durchführbar. Die +Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen Rechnern +vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für +„kleine“ x-Werte verlässt. Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu können, kann man sich einer stochastischen Methode bedienen, der sogenannten @@ -1248,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: @@ -1283,8 +1297,8 @@ Exploitation}, das Finden (lokaler) Optima, bevorzugt. Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute -Lösungen findet oder sich in \emph{lokalen} Optima verrennt. Leider gibt es -kein Patentrezept für die Wahl der Parameter, so dass für verschiedene +Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt +es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene Leitungszahlen und Mischer-Typen experimentiert werden muss. Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden @@ -1330,12 +1344,12 @@ Pseudocode wie folgt beschreiben: \label{sect:sn-evolution:rekombination} Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu -einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel -den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den -\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), um die -beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen. -Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in -Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt. +einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu +einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em +bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der +\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), +Anschließend werden $n$~Leitungen mit einem zufälligen $n$-Schnittmuster wie +in Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt. Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das @@ -1380,15 +1394,63 @@ wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet. \label{fig:16-e1-bitonic-1296542566} \end{figure} -Verwendet man den \emph{bitonen Mischer} in der Rekombinationsphase von -\textsc{SN-Evolution}, so erhält man Netzwerke wie das in -Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte: Der Algorithmus -wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als triviale -Initiallösung gestartet. Das Ergebnis ist ein Netzwerk, das effizienter ist -als das \emph{bitone Mergesort}-Netzwerk: \bs{16} benötigt 80~Komparatoren, -das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt -lediglich~67. Die Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks wurde -leider mit keiner Leitungszahl erreicht. +Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk +als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen +Mischer} verwendet, gibt der Algorithmus Sortiernetzwerke wie das in +Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte zurück. + +Viele der Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser +Konfiguration gefunden werden, sind effizienter als das \emph{bitone +Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen +Merge}-Netzwerk \bm{n} beruht. Das in +Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk +benötigt 67~Komparatoren, 13~Komparatoren weniger als \bs{n}. + +Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke +bevorzugt, können Netzwerke zurückgegeben werden, die schneller als \bs{n} +sind. Viele der schnellen Sortiernetzwerke sind außerdem effizienter als +\bs{n}. Das Sortiernetzwerk mit $n = 23$ Leitungen benötigt mit +134~Komparatoren jedoch einen Komparator mehr als \bs{23}. Die Daten von +schnellen Sortiernetzwerken, die \textsc{SN-Evolution} mit dem \emph{bitonen +Merge}-Netzwerk erzeugt hat, sind in Tabelle~\ref{tbl:sn-ev-bm-fast} +aufgelistet. + +\begin{table}\label{tbl:sn-ev-bm-fast} +\begin{center} +\rowcolors{4}{black!5}{} +\begin{tabular}{|r|r|r|r|r|} +\hline +Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l|}{\bs{n}} \\ +\cline{2-5} + ($n$) & Komp. & Schichten & Komp. & Schichten \\ +\hline + 8 & \gcell 20 & 6 & 24 & 6 \\ + 9 & \Gcell 26 & 8 & 28 & 8 \\ + 10 & \gcell 31 & \gcell 8 & 33 & 9 \\ + 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\ + 12 & \gcell 42 & \gcell 9 & 46 & 10 \\ + 13 & \Gcell 48 & 10 & 53 & 10 \\ + 14 & \gcell 54 & 10 & 61 & 10 \\ + 15 & \Gcell 61 & 10 & 70 & 10 \\ + 16 & \gcell 67 & 10 & 80 & 10 \\ + 17 & \Gcell 76 & 12 & 85 & 12 \\ + 18 & \gcell 87 & \gcell 12 & 91 & 13 \\ + 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\ + 20 & \gcell 104 & \gcell 13 & 106 & 14 \\ + 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\ + 22 & \gcell 118 & \gcell 14 & 123 & 15 \\ + 23 & 134 & \Gcell 14 & \Gcell 133 & 15 \\ + 24 & \gcell 133 & 15 & 144 & 15 \\ +\hline +\end{tabular} +\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus + unter Verwendung des \emph{bitonen Merge}-Netzwerks \bm{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[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer} @@ -1403,17 +1465,25 @@ leider mit keiner Leitungszahl erreicht. \label{fig:16-e1-oddeven-1296543330} \end{figure} -Leider lies sich das Ergebnis des bitonen Mischers -- die von -\textsc{SN-Evolution} ausgegebenen Netzwerke waren effizienter als das -rekursiv aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem -\emph{Odd-Even-Merge}-Netzwerk nicht wiederholen. Zwar erreichen die -Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des -\emph{Odd-Even}-Mischers findet, das \emph{Odd-Even-Mergesort}-Netzwerk -bezüglich Geschwindigkeit und Effizienz, ein Beispiel hierfür ist in -Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Sortiernetzwerkde, die -effizienter als $\operatorname{OES}(n)$ sind, konnten leider nicht beobachtet -werden. Wenn $n$ keine Zweietpotenz ist, kann \textsc{SN-Evolution} unter -Umständen Sortiernetzwerke ausgeben, die schneller als \oes{n} sind. +Im vorherigen Abschnitt wurde gezeigt, dass der +\textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers} +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 +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. + +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} @@ -1447,6 +1517,103 @@ Umständen Sortiernetzwerke ausgeben, die schneller als \oes{n} sind. %\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 @@ -1573,9 +1740,9 @@ Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73 ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich -die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks -leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und -der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden. +die Schnittmuster aufgrund der Symmetrie des \emph{bitonen +Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung -- +mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig. \begin{figure} \centering @@ -1642,7 +1809,7 @@ Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992} definiert. Startet man \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe, -16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, dass die gleiche +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. @@ -1677,7 +1844,7 @@ Schichten~1 und~2 sowie 4~und~5 sind vertauscht. \end{figure} Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach -regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk einen kleineres +regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das einfache Schnittmuster \begin{displaymath} @@ -1805,8 +1972,8 @@ werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15, 16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten -angeordnet sind. Das heißt, dass das resultierende Netzwerk zwar nicht so -effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12} ist. +angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie +\oes{12}, dafür aber schneller als \oes{12} und \bs{12}. \begin{figure} \centering