X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=d98d914d73f37a16a0890b632fd5e37a397694b8;hb=d6d4f620236bc7b6ea9fdb368ae83d23b8692d7c;hp=6cd40785ebfa38f7dd1031d40839d8cbc2222b37;hpb=8fc2876c1eb49652c1e1a897b4cd4617fae96094;p=diplomarbeit.git

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 6cd4078..d98d914 100644
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -1158,10 +1158,10 @@ die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
 vernachlässigbar klein ist.
 
 Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
-Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar.
-Die Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen
-Rechnern vorhanden ist, bevor ein entsprechender Graph den linearen Bereich
-für „kleine“ x-Werte verlässt.
+Experiment für größere Sortiernetzwerke nicht sinnvoll durchführbar. Die
+Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen Rechnern
+vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für
+„kleine“ x-Werte verlässt.
 
 Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
 können, kann man sich einer stochastischen Methode bedienen, der sogenannten
@@ -1283,8 +1283,8 @@ Exploitation}, das Finden (lokaler) Optima, bevorzugt.
 
 Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
 der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
-Lösungen findet oder sich in \emph{lokalen} Optima verrennt. Leider gibt es
-kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
+Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt
+es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
 Leitungszahlen und Mischer-Typen experimentiert werden muss.
 
 Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
@@ -1330,12 +1330,12 @@ Pseudocode wie folgt beschreiben:
 \label{sect:sn-evolution:rekombination}
 
 Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
-einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
-den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
-\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
-beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
-Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in
-Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
+einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu
+einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em
+bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der
+\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}),
+Anschließend werden $n$~Leitungen mit einem zufälligen $n$-Schnittmuster wie
+in Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
 
 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
 erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
@@ -1403,17 +1403,18 @@ leider mit keiner Leitungszahl erreicht.
   \label{fig:16-e1-oddeven-1296543330}
 \end{figure}
 
-Leider lies sich das Ergebnis des bitonen Mischers -- die von
-\textsc{SN-Evolution} ausgegebenen Netzwerke waren effizienter als das
-rekursiv aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem
-\emph{Odd-Even-Merge}-Netzwerk nicht wiederholen. Zwar erreichen die
-Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
-\emph{Odd-Even}-Mischers findet, das \emph{Odd-Even-Mergesort}-Netzwerk
-bezüglich Geschwindigkeit und Effizienz, ein Beispiel hierfür ist in
-Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Sortiernetzwerkde, die
-effizienter als $\operatorname{OES}(n)$ sind, konnten leider nicht beobachtet
-werden. Wenn $n$ keine Zweietpotenz ist, kann \textsc{SN-Evolution} unter
-Umständen Sortiernetzwerke ausgeben, die schneller als \oes{n} sind.
+Im vorherigen Abschnitt wurde gezeigt, dass der
+\textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
+Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
+\emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind.
+Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht
+wiederholen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung
+des \emph{Odd-Even}-Mischers findet, erreichen das
+\emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
+nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
+Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Wenn $n$ keine
+Zweierpotenz ist, kann \textsc{SN-Evolution} unter Umständen Sortiernetzwerke
+ausgeben, die schneller als \oes{n} sind.
 
 %\begin{figure}
 %\begin{center}
@@ -1573,9 +1574,9 @@ Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
 Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
 ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
 ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
-die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks
-leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und
-der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden.
+die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
+Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
+mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
 
 \begin{figure}
   \centering
@@ -1642,7 +1643,7 @@ Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
 $\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
 Pairwise Sorting Network“ \cite{P1992} definiert. Startet man
 \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
-16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, dass die gleiche
+16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, das die gleiche
 Anzahl Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und
 $\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
 Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
@@ -1677,7 +1678,7 @@ Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
 \end{figure}
 
 Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
-regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk einen kleineres
+regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres
 schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das
 einfache Schnittmuster
 \begin{displaymath}
@@ -1805,8 +1806,8 @@ werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
 16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
 dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
 sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten
-angeordnet sind. Das heißt, dass das resultierende Netzwerk zwar nicht so
-effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12} ist.
+angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie
+\oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
 
 \begin{figure}
   \centering