beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt.
-% \todo{Drei oder vier Verfahren?}
+\todo{Drei oder vier Verfahren? Sprich: Mit oder ohne Pairwise Sorting.}
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
verleiht dem Sortiernetzwerk seinen Namen.
Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
-Instanzen des Netzwerks, deren Leitungszahl $n = 2^t$ eine Zweierpotenz ist.
+Instanzen des Netzwerks, deren Leitungszahl $n = 2^d$ eine Zweierpotenz ist.
Es ist jedoch möglich, das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
\subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
dass $K(n,m)$ in $\Theta(N \log (N))$ enthalten ist.
-Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die
+Für den wichtigen Spezialfall, dass $n = m = 2^{d-1}$ beträgt, lässt sich die
Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
erste Rekursionsschritt der OEM-Konstruktion fügt
$\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$
\end{displaymath}
Komparatoren eingespart. Damit ergibt sich
\begin{displaymath}
- K\left(n = 2^{t-1}, n = 2^{t-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
+ K\left(n = 2^{d-1}, n = 2^{d-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
\end{displaymath}
-für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^t)$
+für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^d)$
benötigt werden.
\subsubsection{Das Odd-Even-Mergesort-Netzwerk}
ist allerdings bekannt, dass $k(n)$ in $\Theta\left(n \left(\log
(n)\right)^2\right)$ enthalten ist.
-Für den wichtigen Spezialfall, dass $n = 2^t$ eine Zweierpotenz ist, kann die
+Für den wichtigen Spezialfall, dass $n = 2^d$ eine Zweierpotenz ist, kann die
Anzahl der Komparatoren wieder explizit angegeben werden. \textit{Kenneth
Batcher} zeigt in~\cite{B1968}, dass in diesem Fall
\begin{displaymath}
- k(n = 2^t) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
+ k(n = 2^d) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
\end{displaymath}
gilt.
\emph{Schichten}, in die sich ein Sortiernetzwerk unterteilen lässt.
Diese Anzahl ist insbesondere beim automatisierten Bewerten von
-Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung}
+Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:sn-evolution:bewertung}
beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
Komparatoren später angewendet werden. Deshalb sollte vor einer Bewertung, die
die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
(Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
(Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
-in Abschnitt~\ref{sect:bewertung} behandelt.
+in Abschnitt~\ref{sect:sn-evolution:bewertung} behandelt. Informationen zur Implementierung
+von \textsc{SN-Evolution} befinden sich in
+Abschnitt~\ref{sect:implementierung}.
-\subsection{Bewertungsfunktion}\label{sect:bewertung}
+\subsection{Bewertungsfunktion}\label{sect:sn-evolution:bewertung}
Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
{\em Güte} eines Netzwerks definiert werden. Prinzipiell gibt es zwei Ziele,
Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
-von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}.
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:sn-evolution:bewertung}.
Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
projects / diplomarbeit.git / blobdiff