Schönheitskorrekturen.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 39ad37d..a1145c4 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -228,34 +228,35 @@ beschäftigen.
 
 Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
 entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
 
 Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
 entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse

-$NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte
-sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$
-liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese
-Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese
-Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer
-Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit
-praktikablen Zeitkonstanten gefunden werden.
+\textit{NP}, das heißt das keine Verfahren bekannt sind, die das Problem
+effizient exakt lösbar. Sollte sich herausstellen, dass diese Probleme nicht
+in der Komplexitätsklasse~\textit{P} liegen, wäre eine Konsequenz, dass es
+effiziente exakte Algorithmen für diese Probleme nicht geben kann. Falls sich
+hingegen herausstellt, dass diese Probleme in der
+Komplexitätsklasse~\textit{P} liegen, wird es mit großer Wahrscheinlichkeit
+noch einige Zeit dauern, bis auch Algorithmen mit praktikablen Zeitkonstanten
+gefunden werden.

 
 Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
 
 Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt

-die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus
-zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser
-Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
-beispielsweise immitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
+die beziehungsweise eine der {\em optimalen} Lösungen als einzige Ausgabe des
+Algorithmus zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele
+dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
+beispielsweise imitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen

 auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
 
 Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
 auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
 
 Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee

-ist es, bestehende Lösungen zu neuen, unter Umständen besseren Lösungen zu
+ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu

 kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
 kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten

-Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem häufig
-als {\em Individuum} bezeichnet.
+Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem als {\em
+Individuen} bezeichnet.

 
 Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
 
 Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer

-bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen
+bestehenden Lösungsmenge, der {\em Population}, werden zufällig Lösungen

 ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
 Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
 verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
 ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
 Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
 verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge

-integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
-Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
+eingefügt wird. Die verwendeten Wahrscheinlichkeiten, beispielsweise bei der
+{\em Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise

 werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
 Gütefunktion}.
 
 werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
 Gütefunktion}.
 


@@ -686,7 +687,7 @@ benötigt werden.
 Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie
 das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
 sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die
 Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie
 das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
 sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die

-effizientesten Sortiernetzwerke in Bezuf auf Komparator- und Schichtzahl
+effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl

 entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
 $\operatorname{OES}(n)$ aus
 $\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$,
 entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
 $\operatorname{OES}(n)$ aus
 $\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$,


@@ -716,7 +717,7 @@ die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
 die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
 
 Im Allgemeinen ist die Anzahl der Komparatoren, die vom
 die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
 
 Im Allgemeinen ist die Anzahl der Komparatoren, die vom

-\emph{Odd-Even-Mergesort-Netzwerk} verwendet wird, $k(n)$, direkt aus der
+\emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der

 Definition beziehungsweise der Konstruktionsanleitung abzulesen:
 \begin{displaymath}
   k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
 Definition beziehungsweise der Konstruktionsanleitung abzulesen:
 \begin{displaymath}
   k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)


@@ -750,16 +751,24 @@ gilt.
 
 \subsection{Komprimieren}
 
 
 \subsection{Komprimieren}
 

-\todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}
-

 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
 gleichzeitig ausgewertet werden, wie bereits in
 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
 gleichzeitig ausgewertet werden, wie bereits in

-Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
-\emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
-von \emph{Schichten} verstanden.
+Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Durch manche
+Transformationen, insbesondere das Entfernen einer Leitung, das in
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben wird, kann es vorkommen,
+dass die Komparatoren eines Sortiernetzwerks nicht mehr in der
+kleinstmöglichen Anzahl von \emph{Schichten} angeordnet sind. Unter
+\emph{Komprimierung} wird eine (Neu-)Gruppierung der Komparatoren verstanden,
+die jeden Komparator so früh wie möglich ausführt. So entsteht die
+kleinstmögliche Anzahl von \emph{Schichten}, in die sich ein Sortiernetzwerk
+unterteilen lässt.

 
 Diese Anzahl ist insbesondere beim automatisierten Bewerten von
 
 Diese Anzahl ist insbesondere beim automatisierten Bewerten von

-Komparatornetzwerken interessant. \dots
+Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung}
+beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
+Komparatoren später angewandt werden. Deshalb sollte vor einer Bewertung, die
+die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
+Komprimierung durchgeführt werden.

 
 \subsection{Normalisieren}
 
 
 \subsection{Normalisieren}
 


@@ -776,8 +785,8 @@ Komparatornetzwerken interessant. \dots
 Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
 ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
 zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
 Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
 ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
 zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante

-transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis})
-einen Algorithmus an.
+transformiert werden. Dazu gibt beispielsweise \emph{Donald~E. Knuth}
+in~\cite{KNUTH} einen Algorithmus an.

 
 Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
 bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
 
 Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
 bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}


@@ -861,7 +870,8 @@ nur mit exponentiellem Aufwand möglich ist.
 %\item Nach dem Pairwise sorting-network Schema.
 %\end{itemize}
 
 %\item Nach dem Pairwise sorting-network Schema.
 %\end{itemize}
 

-\subsection{Leitungen entfernen}\label{sect:leitungen_entfernen}
+\subsection{Leitungen entfernen}
+\label{sect:leitungen_entfernen}

 
 Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von
 \emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
 
 Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von
 \emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen


@@ -1061,7 +1071,7 @@ unterschiedlichen Schnittmuster abschätzen.
 
 \begin{figure}
   \begin{center}
 
 \begin{figure}
   \begin{center}

-    \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
+    \includegraphics[viewport=0 0 360 216,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