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
+so schnell, dass ein Ausprobieren aller möglichen Permutationen schon bei
+16~Leitungen praktisch nicht mehr zu bewerkstelligen
ist.\footnote{1.307.674.368.000 Permutationen}
\label{sect:0-1-prinzip}
Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen
wurden, liegen jetzt entsprechend eine Null und eine Eins an, die genauso
vertauscht werden oder nicht, wie das bei der Permutation der Fall war. Liegen
-zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als $a_i$
-oder zwei Zahlen größer oder gleich $a_i$. Da im Fall der 0-1-Folge zwei
-gleiche Zahlen am Komparator anliegen, dürfen wir davon ausgehen, dass sich
-der Komparator so verhält, wie er sich bei der Permutation verhalten hat --
-ohne das Ergebnis zu beeinflussen. Entsprechend kommen an den Ausgängen $i-1$
-und $i$ eine Null und eine Eins in der falschen Reihenfolge an. Das steht im
-Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden.
-
-Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
-Komplexitätsklasse
-$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
-ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(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~Milliarden Tests notwendig, die einen Rechner durchaus mehrere Minuten
-beschäftigen.
+zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als
+$a_i$, beziehungsweise zwei Zahlen größer oder gleich $a_i$. Da im Fall der
+0-1-Folge zwei gleiche Zahlen am Komparator anliegen, dürfen wir davon
+ausgehen, dass sich der Komparator so verhält, wie er sich bei der Permutation
+verhalten hat -- ohne das Ergebnis zu beeinflussen. Entsprechend müssen an den
+Ausgängen $i-1$ und $i$ eine Null und eine Eins in der falschen Reihenfolge
+ankommen. Das steht im Widerspruch zu der Annahme, dass alle 0-1-Folgen
+sortiert werden.
+
+Im Gegensatz zum Überprüfen aller möglichen Permutationen, was mit dem Aufwand
+$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ verbunden ist, besitzt
+das Überprüfen aller 0-1-Folgen „nur“ den Aufwand $\Theta(2^n)$. 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~Milliarden Tests notwendig, die einen Rechner durchaus
+mehrere Minuten beschäftigen. Das ist deshalb problematisch, weil die im
+Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende
+Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines
+Zwischenergebnisses fünf Minuten in Anspruch nimmt, sind für eine Million
+Iterationen fast zehn Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
+auf 1000~Computern mit je 4~Prozessoren verteilt wird, werden über 20~Stunden
+für einen Lauf benötigt.
\subsubsection{Evolutionäre Algorithmen}
Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
-$\mathcal{NP}$. Das heißt, dass keine Verfahren bekannt sind, die diese
-Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese Probleme
-außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine Konsequenz,
-dass es effiziente exakte Algorithmen für diese Probleme nicht gibt. Falls
-sich hingegen herausstellt, dass diese Probleme neben $\mathcal{NP}$ auch in
-der Komplexitätsklasse~\textit{P} liegen, gibt es effiziente Algorithmen. Es
-ist jedoch wahrscheinlich, dass die Zeitkonstanten solcher Algorithmen sehr
-groß sein würden, so dass der praktische Nutzen fraglich bleibt.
-
-Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
-die \emph{optimale Lösung}, beziehungsweise eine der \emph{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.
+$\mathcal{NP}$-vollständig. Das heißt, dass keine Verfahren bekannt sind, die
+diese Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese
+Probleme außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine
+Konsequenz, dass es für diese Probleme keine effizienten exakten Algorithmen
+gibt. Stellt sich hingegen heraus, dass diese Probleme neben
+$\mathcal{NP}$-vollständig auch in der Komplexitätsklasse~\textit{P} liegen,
+gibt es effiziente Algorithmen. Es ist jedoch wahrscheinlich, dass die
+Zeitkonstanten solcher Algorithmen sehr groß wären, so dass der praktische
+Nutzen fraglich bleibt.
+
+Aus diesem Grund besteht die Notwendigkeit, einen Kompromiss einzugehen: Statt
+die \emph{optimale Lösung}, beziehungsweise eine der \emph{optimalen Lösungen}
+als einzige Ausgabe des Algorithmus zuzulassen, wird eine "`möglichst gute"'
+Lösung ausgegeben. Dafür verringert sich die Laufzeit des Algorithmus. 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, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu
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.
projects / diplomarbeit.git / blobdiff