Schönheitskorrekturen.

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 7116840..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)


@@ -1070,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