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
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
\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
\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}
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
$\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.
\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}
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