X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=c8684121c0adc5f798e515941191bf062f27c21f;hb=928ac147177a1f854369cebeadfc0dee611668f6;hp=eb0255234802ee87da18311994b3504262bbbb3c;hpb=3028e656c71a13d67a5114094f1a36ef0ba23c5a;p=diplomarbeit.git

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index eb02552..c868412 100644
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -1554,26 +1554,34 @@ 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} dargestellt.
+Abbildung~\ref{fig:16-e1-oem-fast} dargestellt.
 
 \begin{figure}
   \begin{center}
-    \input{images/16-e1-oddeven-1296543330.tex}
+    \input{images/16-e1-oem-fast.tex}
   \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
     erzeugt.}
-  \label{fig:16-e1-oddeven-1296543330}
+  \label{fig:16-e1-oem-fast}
 \end{figure}
 
 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~Schichten benötigen.
-\oes{11} und \oes{12} benötigen jeweils 10~Schichten.
+Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Beispielsweise
+benötigt das 19-Sortiernetzwerk, das in Abbildung~\ref{fig:19-e1-oem-fast}
+dargestellt ist, nur 13~Schichten, während \oes{19} 14~Schichten benötigt.
 
+\begin{figure}
+  \begin{center}
+    \input{images/19-e1-oem-fast.tex}
+  \end{center}
+  \caption{Sortiernetzwerk mit 19~Leitungen und 93~Komparatoren in
+    13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
+    unter Verwendung des \emph{Odd-Even}-Mischers erzeugt.}
+  \label{fig:19-e1-oem-fast}
+\end{figure}
 
 %\begin{figure}
 %\begin{center}
@@ -1618,15 +1626,9 @@ Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur
 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.
+\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.
 
 \begin{table}\label{tbl:sn-ev-rnd-fast}
 \begin{center}
@@ -1667,6 +1669,56 @@ Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}}
 \end{center}
 \end{table}
 
+Bei einigen Leitungszahlen kann der Algorithmus durch die Verfügbarkeit beider
+Mischer-Netzwerke Sortiernetzwerke zurückgeben, die effizienter als die
+vorherigen Ergebnisse sind. Beispielsweise ist das 19-Sortiernetzwerk in
+Abbildung~\ref{fig:19-e1-rnd-fast} mit 92~Komparatoren effizienter als die
+19-Sortiernetzwerke, die mit nur einem der beiden Mischer-Netzwerke erreicht
+wurden (Abbildungen~\ref{fig:19-e1-bm-fast} und~\ref{fig:19-e1-oem-fast}).
+
+\begin{figure}
+  \begin{center}
+    \input{images/19-e1-rnd-fast.tex}
+  \end{center}
+  \caption{Sortiernetzwerk mit 19~Leitungen und 92~Komparatoren in
+    13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
+    unter Verwendung des \emph{bitonen Mischers} und des
+    \emph{Odd-Even}-Mischers erzeugt.}
+  \label{fig:19-e1-rnd-fast}
+\end{figure}
+
+Die Ergebnisse anderer Leitungszahlen erreichen die Geschwindigkeit der
+Ergebnisse, die mit dem \emph{bitonen Mischer} erzielt wurden. Die Effizienz
+liegt zwischen den Ergebnissen, die mit dem \emph{bitonen Mischer} erzielt
+wurden, und den Ergebnissen, die mit dem \emph{Odd-Even}-Mischer erzielt
+wurden. Beispielsweise ist das 18-Sortiernetzwerk in
+Abbildung~\ref{fig:18-e1-rnd-fast} so schnell wie das Ergebnis, das mit dem
+\emph{bitonen Mischer} ausgegeben wurde. Mit 83~Komparatoren liegt die
+Effizienz des Sortiernetzwerks zwischen den Ergebnissen, die mit dem
+\emph{bitonen Mischer} (87~Komparatoren), beziehungsweise dem
+\emph{Odd-Even}-Mischer (82~Komparatoren) erreicht werden konnten.
+
+\begin{figure}
+  \begin{center}
+    \input{images/18-e1-rnd-fast.tex}
+  \end{center}
+  \caption{Sortiernetzwerk mit 18~Leitungen und 83~Komparatoren in
+    12~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
+    unter Verwendung des \emph{bitonen Mischers} und des
+    \emph{Odd-Even}-Mischers erzeugt.}
+  \label{fig:18-e1-rnd-fast}
+\end{figure}
+
+In einigen Fällen hat \textsc{SN-Evolution} in dieser Konfiguration
+Sortiernetzwerke ausgegeben, die weniger effizient und genauso schnell wie die
+bisherigen Ergebnisse unter Verwendung des \emph{Odd-Even}-Mischers sind.
+Prinzipiell könnte der Algorithmus in jeder Iteration zufällig den
+\emph{Odd-Even}-Mischers auswählen, um die selektierten Individuen zu
+rekombinieren. Das heißt, das die Ergebnisse auch bei einer zufälligen Wahl
+des Mischer-Netzwerks theoretisch erreicht werden können. Allerdings sind
+unter Umständen mehr Iterationen notwendig, bis die gleiche Effizienz erreicht
+wird.
+
 %\input{shmoo-aequivalenz.tex}
 
 \newpage