From 502386e80e6d483ad822488ee630e35f5b828827 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Sun, 20 Feb 2011 20:41:57 +0100 Subject: [PATCH] Diverses. --- diplomarbeit.tex | 214 ++++++++++++++++++++++++++++++++++--------------------- references.bib | 10 +++ 2 files changed, 141 insertions(+), 83 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index b5d8a09..c4ac165 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -578,17 +578,17 @@ vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist. -\subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer} +\subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer} -Der \emph{Odd-Even-Mischer} $\operatorname{OEM}(n,m)$ ist ein +Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein Komperatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$ Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer} -vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even-Mischer} unter +vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even}-Mischer unter Umständen mehr Schichten als der \emph{bitone Mischer}.~\cite{KNUTH} -Der \emph{Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die +Der \emph{Odd-Even}-Mischer selbst ist ebenfalls rekursiv aufgebaut: Die Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei @@ -622,7 +622,7 @@ geraden Indizes und je eine Liste der ungeraden Indizes. Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden -rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am +rekursiv von kleineren \emph{Odd-Even}-Mischern zusammengefügt, so dass sich am Ausgang der Mischer die Folgen \begin{eqnarray} W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\ @@ -635,8 +635,8 @@ hinzugefügt, \begin{equation} w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2} \end{equation} -die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em -Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}. +die die Folge~$W$ sortieren. Den schematischen Aufbau des +\emph{Odd-Even}-Mischers zeigt Abbildung~\ref{fig:oe-merge}. Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde -- @@ -686,7 +686,7 @@ in Abbildung~\ref{fig:oe-post-recursive} dargestellt. \qquad \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}} \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der - kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der + kleineren \emph{Odd-Even}-Mischer entstehen können. Ist die Differenz der Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis sortiert ist.} @@ -737,7 +737,7 @@ benötigt werden. Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von -sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die +sich selbst und einem abschließenden \emph{Odd-Even}-Mischer. Die effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht $\operatorname{OES}(n)$ aus @@ -754,7 +754,7 @@ Komparatornetzwerke definiert sind. \end{center} \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden - \emph{Odd-Even-Mischer} $\operatorname{OEM}(4)$ für gerade und ungerade + \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten Komparatoren zwischen benachbarten Leitungen (grün).} \label{fig:odd-even-mergesort-08} @@ -763,7 +763,7 @@ Komparatornetzwerke definiert sind. In Abbildung~\ref{fig:odd-even-mergesort-08} ist das konkrete Sortiernetzwerk $\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den -\emph{Odd-Even-Mischer} für acht Leitungen dar: Die beiden blauen Blöcke sind +\emph{Odd-Even}-Mischer für acht Leitungen dar: Die beiden blauen Blöcke sind die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden. @@ -887,7 +887,7 @@ $\operatorname{OES}(9)$ benötigt beispielsweise 26~Komparatoren, die in in neun Schichten angeordnet sind. Es sind allerdings Sortiernetzwerke mit neun Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten benötigen. Kombiniert man zwei dieser Netzwerke mit dem -\emph{Odd-Even-Mischer} erhält man ein Sortiernetzwerk mit 18~Eingängen, das +\emph{Odd-Even}-Mischer erhält man ein Sortiernetzwerk mit 18~Eingängen, das 80~Komparatoren in 11~Schichten benötigt -- $\operatorname{OES}(18)$ benötigt 82~Komparatoren in 13~Schichten. Damit ist das resultierende Netzwerk so schnell wie das Sortiernetzwerk mit 18~Eingängen, das \textit{Sherenaz~W. @@ -1016,12 +1016,13 @@ führen beide Reihenfolgen zum selben Ergebnis. \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum -vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, -die Menge der so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die -Anzahl der möglichen Schnittmuster setzt sich zusammen aus der Anzahl von -Möglichkeiten, $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen -Minimum-~/ Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl -der möglichen Schnittmuster: +vorzubelegen, ohne die Menge der erreichbaren Sortiernetzwerke einzuschränken. +Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, die Menge der +so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die Anzahl der +möglichen Schnittmuster setzt sich zusammen aus der Anzahl von Möglichkeiten, +$k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen Minimum-~/ +Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl der möglichen +Schnittmuster: \begin{displaymath} 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right) = 2^{k} \cdot \frac{n!}{k! (n-k)!} @@ -1061,8 +1062,8 @@ sich die Resultate auch in der ersten Schicht nicht unterscheiden. 8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das - \emph{Odd-Even-Mergesort-Netzwerk}, 4973 für das \emph{bitone - Mergesort-Netzwerk} und 18764 für das \emph{Pairwise-Sorting-Netzwerk}.} + \emph{Odd-Even-Mergesort}-Netzwerk, 4973 für das \emph{bitone + Mergesort}-Netzwerk und 18764 für das \emph{Pairwise-Sorting}-Netzwerk.} \label{fig:count-cuts-16} \end{figure} @@ -1088,9 +1089,9 @@ Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der Formel~\eqref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen Schnittmuster führen aber nur zu wenigen \emph{unterschiedlichen} Sortiernetzwerken: 3519 ($\approx 0,1\%$) im Fall des -\emph{Odd-Even-Mergesort-Netzwerks}, 4973 ($\approx 0,15\%$) beim -\emph{bitonen Mergesort-Netzwerk} und 18764 ($\approx 0,57\%$) beim -\emph{Pairwise-Sorting-Netzwerk}. Zwar ist es möglich, dass mehr Iterationen +\emph{Odd-Even-Mergesort}-Netzwerks, 4973 ($\approx 0,15\%$) beim +\emph{bitonen Mergesort}-Netzwerk und 18764 ($\approx 0,57\%$) beim +\emph{Pairwise-Sorting}-Netzwerk. Zwar ist es möglich, dass mehr Iterationen die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. Die Graphen in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der Annahme, dass die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster @@ -1104,7 +1105,8 @@ 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 -\emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von +\emph{Monte-Carlo-Methode}, die \textit{Rolf Wanka} in~\cite{W2006} für +schwierige Zählprobleme vorstellt. Zunächst generiert man eine Menge~$S$ von $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$ @@ -1238,21 +1240,21 @@ Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert. Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von Pseudocode wie folgt beschreiben: \begin{verbatim} -Gütesumme := 0 -Auswahl := (leer) - -für jedes Individuum in Population -{ - reziproke Güte := 1.0 / Guete(Individuum) - Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte) - Gütesumme := Gütesumme + reziproke Güte - - mit Wahrscheinlichkeit P + Gütesumme := 0 + Auswahl := (leer) + + für jedes Individuum in Population { - Auswahl := Individuum + reziproke Güte := 1.0 / Guete(Individuum) + Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte) + Gütesumme := Gütesumme + reziproke Güte + + mit Wahrscheinlichkeit P + { + Auswahl := Individuum + } } -} -gib Auswahl zurück + gib Auswahl zurück \end{verbatim} \subsection{Rekombination} @@ -1260,13 +1262,15 @@ gib Auswahl zurück 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 -{\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die +\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 entfernen wir zufällig $n$~Leitungen wie in -Abschnitt~\ref{sect:leitungen_entfernen} beschrieben. +Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in +Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt. Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft -erhält. +erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das +Komparatornetzwerk die Sortiereigenschaft besitzt. Der Nachteil ist, dass +nicht alle Sortiernetzwerke auf diese Art und Weise erzeugt werden können. \subsection{Mutation} @@ -1330,7 +1334,7 @@ als das bitone Mergesort-Netzwerk: $\operatorname{BS}(16)$ benötigt 80~Komparatoren, das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67. -\subsection{Versuche mit dem Odd-Even-Mischer} +\subsection{Versuche mit dem \emph{Odd-Even}-Mischer} \begin{figure} \begin{center} @@ -1338,7 +1342,7 @@ Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67. \end{center} \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even-Mischers} + \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers erzeugt.} \label{fig:16-e1-oddeven-1296543330} \end{figure} @@ -1346,9 +1350,9 @@ Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67. Leider lies sich das Ergebnis des bitonen Mischers -- das von \textsc{SN-Evolution} ausgegebene Netzwerk war effizienter als das rekursiv aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem -\emph{Odd-Even-Mischer} nicht wiederholen. Zwar erreichen die +\emph{Odd-Even}-Mischer nicht wiederholen. Zwar erreichen die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des -\emph{Odd-Even-Mischers} findet, das \emph{Odd-Even-Mergesort}-Netzwerk +\emph{Odd-Even}-Mischers findet, das \emph{Odd-Even-Mergesort}-Netzwerk bezüglich Schnelligkeit und Effizienz, ein Beispiel hierfür ist in Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Ein Netzwerk, das $\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch @@ -1484,7 +1488,7 @@ Netzwerks scheinen rein zufällig zu sein. \label{fig:32-ec-from-bs64} \end{figure} -Das Ergebnis von \textit{Mühlenthaler} von \textit{Wanka}, die den bitonen +Das Ergebnis von \textit{Mühlenthaler} und \textit{Wanka}, die den bitonen Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk konstruiert haben, kann demnach auch erreicht werden, wenn $\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen @@ -1541,7 +1545,7 @@ Anzahl an 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. -Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht +Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht einsetzt und auch nicht auf einem Mischer basiert, ist der $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In @@ -1673,15 +1677,15 @@ selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt dich de Algorithmus wie folgt beschreiben: \begin{verbatim} -Netzwerk := Eingabe - -für n Iterationen -{ - Nachfolger := kombiniere (Netzwerk, Netzwerk) - Netzwerk := Nachfolger -} - -gib Netzwerk zurück + Netzwerk := Eingabe + + für n Iterationen + { + Nachfolger := kombiniere (Netzwerk, Netzwerk) + Netzwerk := Nachfolger + } + + gib Netzwerk zurück \end{verbatim} Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der @@ -1706,26 +1710,6 @@ Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$ unter den Graphen angegeben. \begin{figure} - \begin{center} - \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf} - \end{center} - \caption{Zyklen, die beim \textit{Random Walk} des - \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die - Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der - y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale - Start-Sortiernetzwerk war $\operatorname{OET}(16)$.} - \label{fig:markov-cycles-16} -\end{figure} - -\todo{Schreibe noch etwas zu …} -\begin{itemize} - \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}). - \item Anzahl der erreichbaren Sortiernetzwerke. - \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen - Netzwerke. (Abbildung~\ref{fig:markov-comparators-16}) -\end{itemize} - -\begin{figure} \centering \subfigure[12 Leitungen, $k = 8,267$, $\theta = 0,962$, $\delta = 40$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-12-pct.pdf}} \subfigure[14 Leitungen, $k = 9,522$, $\theta = 0,867$, $\delta = 52$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-14-pct.pdf}} @@ -1744,10 +1728,43 @@ unter den Graphen angegeben. \end{center} \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem - \emph{Odd-Even-Mischer} und dem \emph{bitonen Mischer}) gesaßen.} + \emph{Odd-Even}-Mischer und dem \emph{bitonen Mischer}) besaßen.} \label{fig:comparison-comparators} \end{figure} +Dass der \textsc{SN-Markov}-Algorithmus nicht schlechter ist als der +\textsc{SN-Evolution}-Algo\-rithmus, ist aus dem Graphen in +Abbildung~\ref{fig:comparison-comparators} ersichtlich. Analog zu dem Versuch +mit \textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die +Anzahl der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als +Startnetzwerk diente bei beiden Algorithmen das +\emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der +x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der +ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt +wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden außerdem nach +dem verwendeten Mischer-Netzwerk -- \oem{32} beziehungsweise \bm{32}. + +Sowohl der \textsc{SN-Markov}-Algorithmus, der das +\emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit +\oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die +bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind. +Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger: +Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit +63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335 +\%$ rund 20~mal höher. + +Erwartunggemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem +\emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist +jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die +mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort} -- \oet{16} +ist aus 120~Komparatoren aufgebaut, bei dem Lauf, der die Daten für +Abbildung~\ref{fig:comparison-comparators} lieferte, traten auch jeweils ein +Sortiernetzwerk mit 121 und 124~Komparatoren auf. Da Sortiernetzwerke mit so +vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen +Iterationen nicht noch einmal erzeugt wurden, handelt es sich vermutlich um +ein Phänomen, das mit der Initialisierung mit dem +\emph{Odd-Even-Transpositionsort}-Netzwerk zusammenhängt. + %\begin{figure} % \begin{center} % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf} @@ -1778,8 +1795,40 @@ unter den Graphen angegeben. % \label{fig:markov-comparators-18} %\end{figure} +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf} +% \end{center} +% \caption{Zyklen, die beim \textit{Random Walk} des +% \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die +% Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der +% y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale +% Start-Sortiernetzwerk war $\operatorname{OET}(16)$.} +% \label{fig:markov-cycles-16} +%\end{figure} + + +\todo{Schreibe noch etwas zu …} +\begin{itemize} + \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}). + \item Anzahl der erreichbaren Sortiernetzwerke. + \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen + Netzwerke. (Abbildung~\ref{fig:markov-comparators-16}) + \item \textsc{SN-Count-Markov} (ggf) +\end{itemize} + \newpage -\section{Ausblick} +\section{Fazit und Ausblick} + +\todo{Ausformulieren} +\begin{itemize} +\item Mit \textsc{SN-Evolution} und \oem{n} kann man nicht besser werden als + \oes{n}. +\item Mit \textsc{SN-Evolution} und \bm{n} kann man besser werden als \bs{n}. +\item Vermutlich kann man mit \textsc{SN-Evolution} und \bm{n} so gut werden +wie \textsc{SN-Evolution-Cut}, wenn er mit \bs{2n} gestartet wird. +\item Leider sind keine konstruktiven Methoden erkannt worden. +\end{itemize} Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von Sortiernetzwerken bieten, sind durch die in dieser Arbeit vorgestellten @@ -1788,11 +1837,11 @@ Herangehensweisen bei weitem nicht erschöpft. Im Folgenden werden Ansätze umrissen, mit denen an die Untersuchungen in dieser Arbeit nahtlos angeknöpft werden könnte. -\subsection{Verwendung des Pairwise-Sorting-Netzwerk in \textsc{SN-Evolution}} +\subsection{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \textsc{SN-Evolution}} Die aktuelle Implementierung von \textsc{SN-Evolution} (Abschnitt~\ref{sect:sn-evolution}) kann sowohl den \emph{bitonen Mischer} als -auch den \emph{Odd-Even-Mischer} verwenden, um zwei Individuen zu +auch den \emph{Odd-Even}-Mischer verwenden, um zwei Individuen zu rekombinieren. Das \emph{Pairwise-Sorting}-Netzwerk verwendet zwar keinen Mischer, es ist aber ebenfalls rekursiv über kleinere Versionen von sich selbst definiert. Das heißt, dass \ps{n} aus zwei Instanzen von @@ -1810,8 +1859,7 @@ wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine $n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren $n$-Sortiernetzwerken als \ps{n} führen. -\subsection{Kooperation von \textsc{SN-Evolution} und -\textsc{SN-Evolution-Cut}} +\subsection{Ausblick: Kooperation von \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut}} Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis} in~\cite{H1992} beschreibt, könnte man die Algorithmen \textsc{SN-Evolution} @@ -1863,7 +1911,7 @@ Beispielsweise eine \emph{normalisierte} Variante des \emph{bitonen Mergesort}-Netzwerks \bs{18} zu erzeugen, kann folgendes Kommando verwendet werden: \begin{verbatim} -$ sn-bitonicsort 18 | sn-normalize >sn-18 + $ sn-bitonicsort 18 | sn-normalize >sn-18 \end{verbatim} Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und es einfach zu ermöglichen, Programme zu verketten, ist eines der diff --git a/references.bib b/references.bib index 7bb306a..95d4959 100644 --- a/references.bib +++ b/references.bib @@ -86,3 +86,13 @@ Publisher = {Addison-Wesley}, Year = 1992 } + +@inbook{W2006, + Author = {Rolf Wanka}, + Title = {Approximationsalgorithmen}, + Chapter = {8 Approximate Counting und die Monte-Carlo-Methode}, + Pages = {151--186}, + Year = 2006, + Publisher = {Teubner Verlag}, + Address = {Wiesbaden} +} -- 2.11.0