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}
 
 \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
   \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}
 
 \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
   \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}
 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)
 
 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
   }
 }
 
   mit Wahrscheinlichkeit P
   {
     Auswahl := Individuum
   }
 }

-gebe Auswahl zurueck
+gib Auswahl zurück

 \end{verbatim}
 
 \subsection{Rekombination}
 \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.
 
 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}).
 
 \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}
 
 \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
   \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}
 
 \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
   \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}
 
 \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
   \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}
 
   \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}
 
 \newpage
 \section{Empirische Beobachtungen}