SN-Markov-Graphen ausgebaut.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index a1145c4..2f8aed2 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -1012,7 +1012,7 @@ sich die Resultate auch in der ersten Schicht nicht unterscheiden.
 
 \begin{figure}
   \begin{center}
-    \includegraphics[viewport=0 0 360 216,width=15cm]{images/count-cuts-16.pdf}
+    \includegraphics[viewport=0 0 425 262,width=15cm]{images/count-cuts-16.pdf}
   \end{center}
   \caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch
   8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
@@ -1071,7 +1071,7 @@ unterschiedlichen Schnittmuster abschätzen.
 
 \begin{figure}
   \begin{center}
-    \includegraphics[viewport=0 0 360 216,width=15cm]{images/collisions-10000-1000000-32.pdf}
+    \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
   \end{center}
   \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der
   \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und
@@ -1194,21 +1194,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}
-Guetesumme := 0
+Gütesumme := 0
 Auswahl := (leer)
 
-fuer jedes Individuum in Population
+für jedes Individuum in Population
 {
-  reziproke Guete := 1.0 / Guete(Individuum)
-  Wahrscheinlichkeit P := reziproke Guete / (reziproke Guete + Guetesumme)
-  Guetesumme := Guetesumme + reziproke Guete
+  reziproke Güte := 1.0 / Guete(Individuum)
+  Wahrscheinlichkeit P := reziproke Güte / (reziproke Güte + Gütesumme)
+  Gütesumme := Gütesumme + reziproke Güte
 
   mit Wahrscheinlichkeit P
   {
     Auswahl := Individuum
   }
 }
-gebe Auswahl zurueck
+gib Auswahl zurück
 \end{verbatim}
 
 \subsection{Rekombination}
@@ -1543,13 +1543,17 @@ gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu
 gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich
 selbst und erhält so einen zufälligen Nachfolger.
 
-\begin{itemize}
-  \item $n \leftarrow \mathrm{Input}$
-  \item \texttt{while} \textit{true}
-  \begin{itemize}
-    \item $n \leftarrow \operatorname{recombine} (n, n)$
-  \end{itemize}
-\end{itemize}
+\begin{verbatim}
+  Netzwerk := Eingabe
+
+  für n Iterationen
+  {
+    Nachfolger := kombiniere (Netzwerk, Netzwerk)
+    Netzwerk   := Nachfolger
+  }
+
+  gib Netzwerk zurück
+\end{verbatim}
 
 \begin{itemize}
   \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
@@ -1560,7 +1564,7 @@ selbst und erhält so einen zufälligen Nachfolger.
 
 \begin{figure}
   \begin{center}
-  \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf}
+  \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-12-pct.pdf}
   \end{center}
   \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen),
   die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
@@ -1570,7 +1574,7 @@ selbst und erhält so einen zufälligen Nachfolger.
 
 \begin{figure}
   \begin{center}
-  \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-14-pct.pdf}
+  \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf}
   \end{center}
   \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen),
   die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
@@ -1580,7 +1584,7 @@ selbst und erhält so einen zufälligen Nachfolger.
 
 \begin{figure}
   \begin{center}
-  \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16-pct.pdf}
+  \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf}
   \end{center}
   \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen),
   die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
@@ -1588,6 +1592,16 @@ selbst und erhält so einen zufälligen Nachfolger.
   \label{fig:markov-comparators-16}
 \end{figure}
 
+\begin{figure}
+  \begin{center}
+  \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf}
+  \end{center}
+  \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen),
+  die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
+  \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.}
+  \label{fig:markov-comparators-18}
+\end{figure}
+
 \newpage
 \section{Empirische Beobachtungen}