X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=8e7beca45b659efc04c39df648245f61b015ae43;hb=56c2c5c629b941ea34faf8ee70fe0c0a87a5ebf3;hp=d98d914d73f37a16a0890b632fd5e37a397694b8;hpb=d6d4f620236bc7b6ea9fdb368ae83d23b8692d7c;p=diplomarbeit.git

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index d98d914..8e7beca 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}
 
@@ -1380,15 +1384,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}