From: Florian Forster <octo@leeloo.lan.home.verplant.org>
Date: Tue, 24 Nov 2009 12:57:13 +0000 (+0100)
Subject: Die Shmoo-Gruppen beschrieben (so ein bisschen) und einige Netzwerke eingefügt.
X-Git-Url: https://git.octo.it/?p=diplomarbeit.git;a=commitdiff_plain;h=d9f8ab6653e8617e0d5fd6782816699f5f20796b

Die Shmoo-Gruppen beschrieben (so ein bisschen) und einige Netzwerke eingefügt.
---

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 8811a81..63c76d5 100644
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -644,6 +644,240 @@ acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
 \label{fig:10-e2-1239014566}
 \end{figure}
 
+% ============
+
+\section{Shmoo-Äquivalenz}
+
+Die folgenden 16-Eingang-Sortiernetzwerke wurden alle mit dem
+\emph{Algorithmus~1} gefunden. Sie haben alle 63~Komparatoren in 10~Schichten,
+jeweils die selbe Anzahl wie Odd-Even-Mergesort.
+
+Um wiederkehrende Muster in den hinteren Schichten der erzeugten
+Sortiernetzwerke besser untersuchen zu können, wurden die erzeugten Netzwerke
+in Gruppen aufgeteilt. Zwei Netzwerke befinden sich dann in der selben
+Gruppen, wenn die Nullen bzw. Einsen, die auf einer Leitung vorkommen können,
+nach der 5.~Schicht (Schicht~4, da bei Null mit dem Zählen begonnen wird)
+nicht mehr ändert. Das heißt, dass die Schichten 0--4 unterschiedlich
+aufgebaut sind, aber den selben Effekt erziehlen. Die Schichten 5--9 sind
+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
+\end{tabular}
+
+Die hinteren Schichten zwischen den Gruppen~1 und~3 schauen so aus, als wären
+sie nur gespiegelt. Warum kommt Gruppe~1 aber viel häufiger vor? Ggf. eine
+Konsequenz aus dem Normieren?
+
+Dito für die Gruppen~2 und~4. Warum ist die eine häufiger?
+
+Ist Gruppe~0 symmetrisch bzgl. der Leitungen?
+
+% Gruppe 0
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group0/16-e1-1258009316.tex}
+\end{center}
+\caption{{\tt images/16-e1/group0/16-e1-1258009316.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258009316}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group0/16-e1-1258010866.tex}
+\end{center}
+\caption{{\tt images/16-e1/group0/16-e1-1258010866.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258010866}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group0/16-e1-1258011861.tex}
+\end{center}
+\caption{{\tt images/16-e1/group0/16-e1-1258011861.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258011861}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group0/16-e1-1259060992.tex}
+\end{center}
+\caption{{\tt images/16-e1/group0/16-e1-1259060992.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1259060992}
+\end{figure}
+
+%\begin{figure}
+%\begin{center}
+%\input{images/16-e1/group0/16-e1-1259061148.tex}
+%\end{center}
+%\caption{{\tt images/16-e1/group0/16-e1-1259061148.tex}: 63~Komparatoren in
+%10~Schichten.}
+%\label{fig:16-e1-1259061148}
+%\end{figure}
+
+% Gruppe 1
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group1/16-e1-1258009982.tex}
+\end{center}
+\caption{{\tt images/16-e1/group1/16-e1-1258009982.tex}: 63~Komparatoren in 10~Schichten.
+Schichten 4--9 identisch zu 16-e1-1258030047 (Gruppe~1).}
+\label{fig:16-e1-1258009982}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group1/16-e1-1258010023.tex}
+\end{center}
+\caption{{\tt images/16-e1/group1/16-e1-1258010023.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258010023}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group1/16-e1-1258029734.tex}
+\end{center}
+\caption{{\tt images/16-e1/group1/16-e1-1258029734.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258029734}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group1/16-e1-1258030047.tex}
+\end{center}
+\caption{{\tt images/16-e1/group1/16-e1-1258030047.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258030047}
+\end{figure}
+
+%\begin{figure}
+%\begin{center}
+%\input{images/16-e1/group1/16-e1-1258034768.tex}
+%\end{center}
+%\caption{{\tt images/16-e1/group1/16-e1-1258034768.tex}: 63~Komparatoren in
+%10~Schichten.}
+%\label{fig:16-e1-1258034768}
+%\end{figure}
+
+% Gruppe 2
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group2/16-e1-1258029063.tex}
+\end{center}
+\caption{{\tt images/16-e1/group2/16-e1-1258029063.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258029063}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group2/16-e1-1258034821.tex}
+\end{center}
+\caption{{\tt images/16-e1/group2/16-e1-1258034821.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258034821}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group2/16-e1-1259054993.tex}
+\end{center}
+\caption{{\tt images/16-e1/group2/16-e1-1259054993.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1259054993}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group2/16-e1-1259058588.tex}
+\end{center}
+\caption{{\tt images/16-e1/group2/16-e1-1259058588.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1259058588}
+\end{figure}
+
+%\begin{figure}
+%\begin{center}
+%\input{images/16-e1/group2/16-e1-1259063485.tex}
+%\end{center}
+%\caption{{\tt images/16-e1/group2/16-e1-1259063485.tex}: 63~Komparatoren in
+%10~Schichten.}
+%\label{fig:16-e1-1259063485}
+%\end{figure}
+
+%\begin{figure}
+%\begin{center}
+%\input{images/16-e1/group2/16-e1-1259063618.tex}
+%\end{center}
+%\caption{{\tt images/16-e1/group2/16-e1-1259063618.tex}: 63~Komparatoren in
+%10~Schichten.}
+%\label{fig:16-e1-1259063618}
+%\end{figure}
+
+% Gruppe 3
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group3/16-e1-1258012027.tex}
+\end{center}
+\caption{{\tt images/16-e1/group3/16-e1-1258012027.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258012027}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group3/16-e1-1258037039.tex}
+\end{center}
+\caption{{\tt images/16-e1/group3/16-e1-1258037039.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1258037039}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group3/16-e1-1259065042.tex}
+\end{center}
+\caption{{\tt images/16-e1/group3/16-e1-1259065042.tex}: 63~Komparatoren in
+10~Schichten.}
+\label{fig:16-e1-1259065042}
+\end{figure}
+
+% Gruppe 4
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group4/16-e1-1259060520.tex}
+\end{center}
+\caption{{\tt images/16-e1/group4/16-e1-1259060520.tex}: 63~Komparatoren in 10~Schichten.
+(Gruppe~4).}
+\label{fig:16-e1-1259060520}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\input{images/16-e1/group4/16-e1-1259067171.tex}
+\end{center}
+\caption{{\tt images/16-e1/group4/16-e1-1259067171.tex}: 63~Komparatoren in 10~Schichten.
+(Gruppe~4).}
+\label{fig:16-e1-1259067171}
+\end{figure}
+
 \subsection{Güte}
 
 \begin{itemize}