Fehlende Dateien (Bilder) eingecheckt.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index fa09f30..c5d64e5 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -98,6 +98,7 @@ das hinbekomme bzw. Recht behalte.}
 
 \subsection{Motivation}\label{sect:motivation}
 
+\todo{Schreibe noch etwas zu …}
 \begin{itemize}
 \item Sortiernetzwerke sind toll, weil $\ldots$
 \item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
@@ -566,15 +567,6 @@ $\frac{1}{4} n \log(n) \log(n+1) = \mathcal{O}\left(n (log (n))^2\right)$
 Komparatoren, die in $\frac{1}{2} \log(n) \log(n+1) = \mathcal{O}(\log(n))$
 Schichten angeordnet sind.
 
-%\begin{figure}
-%\begin{center}
-%\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
-%\end{center}
-%\caption{Rekursiver Aufbau von $S(n)$: Es besteht aus zwei Instanzen von
-%$S(n/2)$ und dem Mischer $M(n)$.}
-%\label{fig:bms_rekursiver_aufbau}
-%\end{figure}
-
 \subsection{Das Odd-Even-Mergesort-Netzwerk}
 
 Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk}
@@ -902,18 +894,6 @@ Al-Haj Baddar} und \textit{Kenneth~E. Batcher} in ihrer Arbeit „An 11-Step
 Sorting Network for 18~Elements“~\cite{BB2009} vorstellen, benötigt aber
 6~Komparatoren weniger.
 
-% 9   9
-% 9  18
-% 9  27
-% 9  36
-% 9  45
-% 8  53
-% 8  61
-% 7  68
-% 7  75
-% 6  81
-% 5  86
-
 Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
 ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
 sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
@@ -923,12 +903,6 @@ die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden
 Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
 nur mit exponentiellem Aufwand möglich ist.
 
-%\begin{itemize}
-%\item Mit dem Bitonic-Merge
-%\item Mit dem Odd-Even-Merge
-%\item Nach dem Pairwise sorting-network Schema.
-%\end{itemize}
-
 \subsection{Leitungen entfernen}
 \label{sect:leitungen_entfernen}
 
@@ -1182,6 +1156,7 @@ die Anzahl der \emph{möglichen} Schnittmuster.
 
 \newpage
 \section{Der \textsc{SN-Evolution}-Algorithmus}
+\label{sect:sn-evolution}
 
 Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
 Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
@@ -1369,12 +1344,7 @@ Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Ein Netzwerk, das
 $\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch
 nicht beobachtet werden.
 
-
-
-\begin{itemize}
-\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
-\item Möglicherweise: Verwende den rekursiven Aufbau des \emph{Pairwise-Sorting}-Netzwerks um Sortiernetzwerke zu mergen.
-\end{itemize}
+\todo{Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.}
 
 %\begin{figure}
 %\begin{center}
@@ -1681,7 +1651,7 @@ selbst erzeugen kann.
 Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl
 der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger
 sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der
-Nachfolger zwar noch unter 20000, bei den untersuchten 32-Sortiernetzwerken
+Nachfolger zwar noch unter 20.000, bei den untersuchten 32-Sortiernetzwerken
 wurden jedoch bereits bis zu $2,6 \cdot 10^8$ unterschiedliche Schnittmuster
 geschätzt.
 
@@ -1704,6 +1674,13 @@ für n Iterationen
 gib Netzwerk zurück
 \end{verbatim}
 
+Die Abbildungen~\ref{fig:markov-comparators-12},
+\ref{fig:markov-comparators-14}, \ref{fig:markov-comparators-12},
+\ref{fig:markov-comparators-16} und~\ref{fig:markov-comparators-18} zeigen die
+Anzahl der Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf
+seinem zufälligen Pfad durchläuft. Ausserdem eingezeichnet ist eine
+\emph{Gamma-Verteilung}.
+
 \begin{figure}
   \begin{center}
   \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
@@ -1716,7 +1693,7 @@ gib Netzwerk zurück
   \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.
@@ -1765,14 +1742,6 @@ gib Netzwerk zurück
 \end{figure}
 
 \newpage
-\section{Empirische Beobachtungen}
-
-\begin{itemize}
-\item So schnell konvergiert der Algorithmus.
-\item $\ldots$
-\end{itemize}
-
-\newpage
 \section{Ausblick}
 
 Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von