Abschnitt "Normalisieren".

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index a861992..49905bd 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -472,10 +472,49 @@ Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
 
 \section{Transformation von Sortiernetzwerken}
 
-\begin{itemize}
-\item Komprimieren (Alle Komparatoren so früh wie möglich anwenden).
-\item Normalisieren (Transformation zu Standard-Sortiernetzwerken).
-\end{itemize}
+\subsection{Komprimieren}
+
+\todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}
+
+Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
+gleichzeitig ausgewertet werden, wie bereits in
+Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
+\emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
+von \emph{Schichten} verstanden.
+
+Diese Anzahl ist insbesondere beim automatisierten Bewerten von
+Komparatornetzwerken interessant. \dots
+
+\subsection{Normalisieren}
+
+\begin{figure}
+  \centering
+  \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
+  \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
+  \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
+  transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
+  intuitiven Konstruktion und die normalisierte Variante.}
+  \label{fig:beispiel_normalisieren}
+\end{figure}
+
+Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
+ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
+zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
+transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis})
+einen Algorithmus an.
+
+Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
+bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
+zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
+Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
+die unter und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei
+Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist. 
+In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven
+Definition.
+
+In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
+Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche
+Richtung.
 
 \subsection{Zwei Netzwerke kombinieren}
 
@@ -679,11 +718,11 @@ hingegen innerhalb einer Gruppe austauschbar und oft (immer?) identisch.
 Die Anzahl der Netzwerke in den jeweiligen Gruppen ist unterschiedlich. Zur
 Zeit sind in den Gruppen so viele Netzwerke:\\
 \begin{tabular}{|l|r|r|} \hline
-Gruppe~0 & 18 & $48,7\%$ \\
-Gruppe~1 & 9  & $24,3\%$ \\
-Gruppe~2 & 6  & $16,2\%$ \\
-Gruppe~3 & 3  & $8,1\%$ \\
-Gruppe~4 & 1  & $2,7\%$ \\ \hline
+Gruppe~0 & 21 & $50,0\%$ \\
+Gruppe~1 & 10  & $23,8\%$ \\
+Gruppe~2 & 6  & $14,3\%$ \\
+Gruppe~3 & 3  & $7,1\%$ \\
+Gruppe~4 & 2  & $4,8\%$ \\ \hline
 \end{tabular}
 
 Die hinteren Schichten zwischen den Gruppen~1 und~3 schauen so aus, als wären