ausgegeben.
Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die
-Ausgänge von {\em Komparatoren} mit dem Eingängen anderer {\em Komparatoren}
-verbindet, erhält man ein {\em Komparatornetzwerk}.
+Ausgänge von Komparatoren mit dem Eingängen anderer Komparatoren verbindet,
+erhält man ein {\em Komparatornetzwerk}.
\begin{figure}
\begin{center}
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.
+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
zerstört.
Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
-{\em nicht} hat, ist mit einem gegebenen Gegenbeispiel also einfach möglich.
+{\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
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.
+$2^n$~0-1-Folgen sortiert.
Sortiernetzwerke:
\begin{itemize}
\begin{center}
\input{images/oe-transposition-8.tex}
\end{center}
-\caption{Das {\em Odd-Even-Transpositionsort} Netzwerk für acht Eingänge.}
+\caption{Das {\em Odd-Even-Transpositionsort-Netzwerk} für acht Eingänge.}
\label{fig:odd_even_transposition_08}
\end{figure}
Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte
Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit
weniger Vergleichen aus als der {\em bitone Mischer}, der im
-Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde.
+Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde, aus.
Der {\em Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
\begin{center}
\input{images/oe-mergesort-8.tex}
\end{center}
-\caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge.}
+\caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
+sind die Instanzen von $S(4)$ (rot), die beiden \emph{Odd-Even-Mischer}
+$\mathit{OEM}(4)$ für gerade und ungerade Leitungen (blau) und die im letzten
+Rekursionsschritt hinzugefügten Komparatoren zwischen benachbarten Leitungen
+(grün).}
\label{fig:odd_even_mergesort_08}
\end{figure}
In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche
-Richtung.
+Richtung. Statt dem typischen "`Treppenmuster"' sind abwechselnd das Treppen-
+und das Trichtermuster zu sehen.
\subsection{Zwei Netzwerke kombinieren}
projects / diplomarbeit.git / commitdiff