From: Florian Forster Date: Sat, 29 Jan 2011 11:29:53 +0000 (+0100) Subject: Schönheitskorrekturen. X-Git-Url: https://git.octo.it/?p=diplomarbeit.git;a=commitdiff_plain;h=728535ac0e3596f77674a1084891d6bea2da65e4 Schönheitskorrekturen. --- diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 7116840..a1145c4 100644 --- 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 -$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 -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 -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 -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 -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 -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}. @@ -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 -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)$, @@ -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 -\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) @@ -1070,7 +1071,7 @@ unterschiedlichen Schnittmuster abschätzen. \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