X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=a1145c4d08b69f5f07959b53c5281a83afaaa450;hb=728535ac0e3596f77674a1084891d6bea2da65e4;hp=05168178e6c54c8b33c38dcad23c547e96207461;hpb=ce19fffb90d1a91a224630831471c95c48f4577b;p=diplomarbeit.git

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 0516817..a1145c4 100644
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -103,15 +103,15 @@ das hinbekomme bzw. Recht behalte.}
 
 \subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke}
 
-{\em Komparatoren} sind die Bausteine, die {\em Sortiernetzwerken} zugrunde
-liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten können.
-Ausserdem besitzt ein {\em Komparator} zwei Ausgänge, die im Gegensatz zu den
-Eingängen unterscheidbar sind: Die grö"sere der beiden Zahlen wird immer auf
-dem einen, die kleinere der beiden Zahlen immer auf dem anderen Ausgang
-ausgegeben.
-
-Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die
-Ausgänge von Komparatoren mit dem Eingängen anderer Komparatoren verbindet,
+\emph{Komparatoren} sind die Bausteine, die \emph{Komparatornetzwerken}
+zugrunde liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten
+können und zwei Ausgänge, auf denen die Zahlen wieder ausgegeben werden. Dabei
+sind die Ausgänge im Gegensatz zu den Eingängen unterscheidbar, da die größere
+der beiden Zahlen wird immer auf dem einen, die kleinere der beiden Zahlen
+immer auf dem anderen Ausgang ausgegeben ausgegeben wird.
+
+Kombiniert man mehrere \emph{Komparatoren} miteinander, das heißt, dass die
+Ausgänge eines Komparators mit Eingängen weiterer Komparatoren verbunden sind,
 erhält man ein {\em Komparatornetzwerk}.
 
 \begin{figure}
@@ -124,99 +124,151 @@ aus 5~Komparatoren.}
 \end{figure}
 
 Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
-Komparatornetzwerk aus fünf Komparatoren in der üblichen Darstellungsweise:
-Die horizontalen Linien stellen Leitungen von den Eingängen auf der linken
-Seite zu den Ausgängen auf er rechten Seite dar. Die vertikalen Pfeile
-symbolisieren die Komparatoren, die die Werte "`auf den Leitungen"'
-vergleichen und ggf. vertauschen. Nach einem Komparator befindet sich die
+\emph{Komparatornetzwerk} aus fünf Komparatoren. Insgesamt gibt es vier
+verschiedene Eingänge und vier Ausgänge. Die Ein- und Ausgänge werden durch
+eine horizontale Linie dargestellt und als \emph{Leitung} bezeichnet. Die
+\emph{Komparatoren} sind durch vertikale Pfeile dargestellt und verbinden je
+zwei verschiedene \emph{Leitungen} miteinander. Die Verbindungsstellen von
+\emph{Leitungen} und \emph{Komparatoren} sind zur besseren Übersichlichkeit
+durch schwarze Punkte symbolisiert.
+
+Auf der linken Seite befinden sich die Eingänge. Hier wird eine Zahlenfolge in
+das Netzwerk hineingegeben. Jeder Komparator vergleicht die Zahlen „auf“ den
+beiden Leitungen, die er verbindet. Nach einem Komparator befindet sich die
 kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
-befindet sich auf der Leitung auf der der Pfeil seinen Ursprung hat.
+befindet sich auf der Leitung, auf der der Pfeil seinen Ursprung hat.
 
 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
 gleichzeitig angewandt werden. Das Beispiel in
 Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
-vergleicht in einem ersten Schritt die zwei oberen und die zwei unteren
-Leitungen gleichzeitig. Eine Gruppe von Komparatoren, die gleichzeitig
-angewendet werden können, nennt man eine \emph{Schicht} des
-Komparatornetwerks. Die \emph{Verzögerung} eines Komparatornetzwerks ist
-gleichbedeutend mit der Anzahl der Schichten, in die sich die Komparatoren
-mindestens gruppieren lassen, da sie die Anzahl der benötigten parallelen
-Schritte darstellt.
-
-Komparatornetzwerke, die für jede beliebige Eingabepermutation eine
-Ausgabe erzeugen, die der Sortierung der Eingabe entspricht, heißen 
-{\em Sortiernetzwerke}. Das in
+vergleicht die zwei oberen und die zwei unteren Leitungen gleichzeitig. Eine
+Gruppe von Komparatoren, die gleichzeitig angewendet werden können, nennt man
+eine \emph{Schicht} des Komparatornetwerks. Die \emph{Verzögerung} eines
+Komparatornetzwerks ist gleichbedeutend mit der Anzahl der Schichten, in die
+sich die Komparatoren mindestens gruppieren lassen, da sie die Anzahl der
+benötigten parallelen Schritte darstellt.
+
+\emph{Komparatornetzwerke}, die für \emph{jede} Eingabefolge eine Ausgabe
+erzeugen, die der Sortierung der Eingabe entspricht, heißen
+\emph{Sortiernetzwerke}. Das in
 Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
-ist kein Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ würde zur Ausgabe
-${(2, 1, 3, 4)}$ führen -- die bestehenden Sortierung wird also sogar
+ist \emph{kein} Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur
+Ausgabe ${(2, 1, 3, 4)}$ -- die bestehenden Sortierung wird also sogar
 zerstört.
 
-Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
-{\em nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich.
-Dieses Gegenbeispiel zu finden ist allerdings aufwendig.
-
-\todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein
-Netzwerk sortiert, ist doch NP-vollständig, also müsste doch das Finden eines
-Gegenbeispiels im Allgemeinen auch exponentialle Laufzeit haben..?}
-\todo{Wenn die {\em Entscheidung}, ob ein Netzwerk sortiert, NP-vollständig
-ist, müsse man dann nicht einen Zeugen für die Sortiereigenschaft angeben
-können?}
-
-\todo{$0-1$-Prinzip}
-
-Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft
-besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen
-ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle
-$2^n$~0-1-Folgen sortiert.
-
-Sortiernetzwerke:
-\begin{itemize}
-\item Ein Komparator-Netzwerk ist $\ldots$
-\item Ein Komparator-Netzwerk ist ein Sortiernetzwerk, wenn $\ldots$
-\item Die Frage nach der Sortiereigenschaft ist NP-vollständig.
-\end{itemize}
+\begin{figure}
+  \begin{center}
+    \input{images/09-e2-c24-allbut1.tex}
+  \end{center}
+  \caption{Ein \emph{Komparatornetzwerk} mit neun Eingängen und
+  24~Komparatoren, die in 8~Schichten angeordnet sind. Das Netzwerk sortiert
+  alle Eingaben, bei denen das Minimum nicht auf dem mittleren Eingang liegt.}
+  \label{fig:09-e2-c24-allbut1}
+\end{figure}
+Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft {\em
+nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich. Das
+Komparatornetzwerk wird auf das Gegenbeispiel angewendet und anschließend wird
+überprüft, ob die Ausgabe sortiert ist. Ist sie es nicht heißt das, dass es
+mindestens eine Eingabefolge gibt, die nicht sortiert wird. Entsprechend der
+Definition handelt es sich bei dem \emph{Komparatornetzwerk} folglich
+\emph{nicht} um ein \emph{Sortiernetzwerk}. Ein solches Gegenbeispiel für ein
+gegebenes Komparatornetzwerk zu finden ist nach heutigem Kenntnisstand jedoch
+nicht \emph{effizient} möglich.
+
+Beispielsweise sortiert das Komparatornetzwerk in
+Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880 möglichen
+Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4, 8, 6)$
+lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die
+Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge
+$(1, 0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt.
+
+Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein
+Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese
+Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$
+über-exponentiell schnell, so dass ein Ausprobieren aller möglichen
+Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen
+ist.\footnote{1.307.674.368.000 Permutationen}
+
+Glücklicherweise reicht es aus, alle möglichen 0-1-Folgen zu überprüfen, wie
+\textit{Donald~E. Knuth} in \cite{KNUTH} zeigt. Die Beweisidee ist folgende:
+Angenommen ein Komparatornetzwerk sortiert alle 0-1-Folgen und es gibt eine
+Permutation $E = (e_0, \dots, e_{n-1})$ beliebiger Zahlen, die nicht sortiert
+wird. Die Ausgabefolge sei $A = (a_0, \dots, a_{n-1})$. Sei $i$ eine Position
+in der Ausgabe, die die Sortierbedingung verletzt:
+\begin{displaymath}
+  a_0 \leqq a_1 \leqq \dots \leqq a_{i-1} > a_i \dots
+\end{displaymath}
+Die Eingabe kann mittels
+\begin{displaymath}
+  \hat{e}_j = \left\{
+    \begin{array}{cl}
+      0 & e_j \leqq a_i \\
+      1 & e_j > a_i
+    \end{array} \right.
+\end{displaymath}
+auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme von
+Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das
+Verhalten jedes einzelnen Komparators nicht, so dass die Annahme auf einen
+Widerspruch geführt wird.
+
+Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
+Komplexitätsklasse
+$\mathcal{O}\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
+ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\mathcal{O}(2^n)$
+verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
+schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
+ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,
+sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für
+aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung
+eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa
+4,3~Millarden Tests notwendig, die einen Rechner durchaus mehrere Minuten
+beschäftigen.
 
 \subsubsection{Evolutionäre Algorithmen}
 
 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}.
 
 Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
 sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
 aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
-es oft einfach ist {\em irgendeine} Lösung anzugeben. Zum anderen muss eine
-Methode für die Rekombination existieren. Das insbesondere dann problematisch
-wenn {\em Nebenbedingungen} eingehalten werden müssen.
+es oft einfach ist {\em irgendeine} Lösung anzugeben. Die angegebenen
+Algorithmen verwenden als einfache, initiale Lösung häufig das
+\emph{Odd-Even-Transpositionsort}-Netzwerk, das in
+Abschnitt~\ref{sect:odd_even_transpositionsort} beschrieben wird. Zum anderen
+muss eine Methode für die Rekombination existieren. Das ist insbesondere dann
+problematisch, wenn {\em Nebenbedingungen} eingehalten werden müssen.
 
 Beim Aussuchen von zufälligen Lösungen aus der Population, der
 \emph{Selektion}, werden gute Lösungen bevorzugt. Wie sehr diese Lösungen
@@ -238,11 +290,26 @@ eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
 beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
 zwischen verschiedenen Leitungszahlen stark unterscheiden.
 
-\begin{itemize}
-\item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$
-\item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die
-Mutation \textit{(vermutlich)} nicht (effizient) möglich.
-\end{itemize}
+Die \textit{Exploration} kann von einem weiteren Mechanismus unterstützt
+werden, der ebenfalls der Evolutionslehre entliehen ist, der \emph{Mutation}.
+Dabei werden Lösungen zufällig verändert, so dass auch andere Lösungen „in der
+Nähe“ von direkten Nachfolgern erreicht werden können. Das hilft insbesondere
+bei der intensiven Suche in der Nähe eines lokalen Optimums aber auch beim
+„Ausbrechen“ und finden noch besserer Lösungen.
+
+Bei \emph{Sortiernetzwerken} ist eine \emph{Mutation} leider immer damit
+verbunden, dass anschließend die Sortiereigenschaft des resultierenden
+\emph{Komparatornetzwerks} wieder überprüft werden muss, da selbst das
+Hinzufügen eines zufälligen Komparators diese Eigenschaft zerstören kann. Beim
+Suchen möglichst effizienter Netzwerke ist natürlich das zufällige Entfernen
+von Komparatoren interessanter, was die Sortiereigenschaft sehr oft aufhebt.
+
+Die im Folgenden beschriebenen Algorithmen mutieren (verändern) daher nicht
+die \emph{Sortiernetzwerke} selbst, sondern verzichten auf Mutation oder
+mutieren lediglich Transformationen von Sortiernetzwerken, die die
+Sortiereigenschaft erhält. Transformationen von Sortiernetzwerken werden in
+Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der Mutation
+einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
 
 \newpage
 \section{Bekannte konstruktive Sortiernetzwerke}
@@ -620,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)$,
@@ -650,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)
@@ -680,19 +747,28 @@ gilt.
 
 \newpage
 \section{Transformation von Sortiernetzwerken}
+\label{sect:tranformation}
 
 \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
-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
-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}
 
@@ -709,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
-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}
@@ -794,7 +870,8 @@ nur mit exponentiellem Aufwand möglich ist.
 %\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
@@ -994,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
@@ -1060,16 +1137,16 @@ Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
 {\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
 die bei Sortiernetzwerken verfolgt werden können:
 \begin{itemize}
-  \item Möglichst wenige Komparatoren („billig“)
+  \item Möglichst wenige Komparatoren („effizient“)
   \item Möglichst wenige Schichten („schnell“)
 \end{itemize}
 
 Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
-billigste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
-in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
-9~Schichten.
+effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus
+60~Komparatoren in 10~Schichten. Das schnellste Netzwerk besteht aus
+61~Komparatoren in nur 9~Schichten.
 
-Eine Gütefunktion, die die beiden Ziele "`billig"' und "`schnell"'
+Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
 berücksichtigen kann, hat die folgende allgemeine Form:
 \begin{equation}
   \operatorname{Guete}(S) = w_{\mathrm{Basis}}
@@ -1084,10 +1161,10 @@ jegliche Ergebnisse sind dann rein zufälliger Natur.\footnote{Dass dies nicht
 so schlecht ist wie man intuitiv vermuten könnte, zeigt der
 \textsc{SN-Markov}-Algorithmus in Abschnitt~\ref{sect:markov}.}
 
-Da möglichst billige und schnelle Sortiernetzwerke gefunden werden sollen, ist
-ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert. Das
-heißt, dass das Ziel von \textsc{SN-Evolution} ist, $\operatorname{Guete}(S)$
-zu \emph{minimieren}.
+Da möglichst effiziente und schnelle Sortiernetzwerke gefunden werden sollen,
+ist ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert.
+Das heißt, dass das Ziel von \textsc{SN-Evolution} ist,
+$\operatorname{Guete}(S)$ zu \emph{minimieren}.
 
 Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
 genommen werden. Ist er groß, wird der relative Unterschied der Güten