shmoo-aequivalenz.tex

   1 \section{Shmoo-Äquivalenz}
   2
   3 Die folgenden 16-Eingang-Sortiernetzwerke wurden alle mit dem
   4 \emph{Algorithmus~1} gefunden. Sie haben alle 63~Komparatoren in 10~Schichten,
   5 jeweils die selbe Anzahl wie Odd-Even-Mergesort.
   6
   7 Um wiederkehrende Muster in den hinteren Schichten der erzeugten
   8 Sortiernetzwerke besser untersuchen zu können, wurden die erzeugten Netzwerke
   9 in Gruppen aufgeteilt. Zwei Netzwerke befinden sich dann in der selben
  10 Gruppen, wenn die Nullen bzw. Einsen, die auf einer Leitung vorkommen können,
  11 nach der 5.~Schicht (Schicht~4, da bei Null mit dem Zählen begonnen wird)
  12 nicht mehr ändert. Das heißt, dass die Schichten 0--4 unterschiedlich
  13 aufgebaut sind, aber den selben Effekt erziehlen. Die Schichten 5--9 sind
  14 hingegen innerhalb einer Gruppe austauschbar und oft (immer?) identisch.
  15
  16 Die Anzahl der Netzwerke in den jeweiligen Gruppen ist unterschiedlich. Zur
  17 Zeit sind in den Gruppen so viele Netzwerke:\\
  18 \begin{tabular}{|l|r|r|} \hline
  19 Gruppe~0 & 21 & $50,0\%$ \\
  20 Gruppe~1 & 10  & $23,8\%$ \\
  21 Gruppe~2 & 6  & $14,3\%$ \\
  22 Gruppe~3 & 3  & $7,1\%$ \\
  23 Gruppe~4 & 2  & $4,8\%$ \\ \hline
  24 \end{tabular}
  25
  26 Die hinteren Schichten zwischen den Gruppen~1 und~3 schauen so aus, als wären
  27 sie nur gespiegelt. Warum kommt Gruppe~1 aber viel häufiger vor? Ggf. eine
  28 Konsequenz aus dem Normieren?
  29
  30 Dito für die Gruppen~2 und~4. Warum ist die eine häufiger?
  31
  32 Ist Gruppe~0 symmetrisch bzgl. der Leitungen?
  33
  34 % Gruppe 0
  35
  36 \begin{figure}
  37 \begin{center}
  38 \input{images/16-e1/group0/16-e1-1258009316.tex}
  39 \end{center}
  40 \caption{{\tt images/16-e1/group0/16-e1-1258009316.tex}: 63~Komparatoren in
  41 10~Schichten.}
  42 \label{fig:16-e1-1258009316}
  43 \end{figure}
  44
  45 \begin{figure}
  46 \begin{center}
  47 \input{images/16-e1/group0/16-e1-1258010866.tex}
  48 \end{center}
  49 \caption{{\tt images/16-e1/group0/16-e1-1258010866.tex}: 63~Komparatoren in
  50 10~Schichten.}
  51 \label{fig:16-e1-1258010866}
  52 \end{figure}
  53
  54 \begin{figure}
  55 \begin{center}
  56 \input{images/16-e1/group0/16-e1-1258011861.tex}
  57 \end{center}
  58 \caption{{\tt images/16-e1/group0/16-e1-1258011861.tex}: 63~Komparatoren in
  59 10~Schichten.}
  60 \label{fig:16-e1-1258011861}
  61 \end{figure}
  62
  63 \begin{figure}
  64 \begin{center}
  65 \input{images/16-e1/group0/16-e1-1259060992.tex}
  66 \end{center}
  67 \caption{{\tt images/16-e1/group0/16-e1-1259060992.tex}: 63~Komparatoren in
  68 10~Schichten.}
  69 \label{fig:16-e1-1259060992}
  70 \end{figure}
  71
  72 %\begin{figure}
  73 %\begin{center}
  74 %\input{images/16-e1/group0/16-e1-1259061148.tex}
  75 %\end{center}
  76 %\caption{{\tt images/16-e1/group0/16-e1-1259061148.tex}: 63~Komparatoren in
  77 %10~Schichten.}
  78 %\label{fig:16-e1-1259061148}
  79 %\end{figure}
  80
  81 % Gruppe 1
  82
  83 \begin{figure}
  84 \begin{center}
  85 \input{images/16-e1/group1/16-e1-1258009982.tex}
  86 \end{center}
  87 \caption{{\tt images/16-e1/group1/16-e1-1258009982.tex}: 63~Komparatoren in 10~Schichten.
  88 Schichten 4--9 identisch zu 16-e1-1258030047 (Gruppe~1).}
  89 \label{fig:16-e1-1258009982}
  90 \end{figure}
  91
  92 \begin{figure}
  93 \begin{center}
  94 \input{images/16-e1/group1/16-e1-1258010023.tex}
  95 \end{center}
  96 \caption{{\tt images/16-e1/group1/16-e1-1258010023.tex}: 63~Komparatoren in
  97 10~Schichten.}
  98 \label{fig:16-e1-1258010023}
  99 \end{figure}
 100
 101 \begin{figure}
 102 \begin{center}
 103 \input{images/16-e1/group1/16-e1-1258029734.tex}
 104 \end{center}
 105 \caption{{\tt images/16-e1/group1/16-e1-1258029734.tex}: 63~Komparatoren in
 106 10~Schichten.}
 107 \label{fig:16-e1-1258029734}
 108 \end{figure}
 109
 110 \begin{figure}
 111 \begin{center}
 112 \input{images/16-e1/group1/16-e1-1258030047.tex}
 113 \end{center}
 114 \caption{{\tt images/16-e1/group1/16-e1-1258030047.tex}: 63~Komparatoren in
 115 10~Schichten.}
 116 \label{fig:16-e1-1258030047}
 117 \end{figure}
 118
 119 %\begin{figure}
 120 %\begin{center}
 121 %\input{images/16-e1/group1/16-e1-1258034768.tex}
 122 %\end{center}
 123 %\caption{{\tt images/16-e1/group1/16-e1-1258034768.tex}: 63~Komparatoren in
 124 %10~Schichten.}
 125 %\label{fig:16-e1-1258034768}
 126 %\end{figure}
 127
 128 % Gruppe 2
 129
 130 \begin{figure}
 131 \begin{center}
 132 \input{images/16-e1/group2/16-e1-1258029063.tex}
 133 \end{center}
 134 \caption{{\tt images/16-e1/group2/16-e1-1258029063.tex}: 63~Komparatoren in
 135 10~Schichten.}
 136 \label{fig:16-e1-1258029063}
 137 \end{figure}
 138
 139 \begin{figure}
 140 \begin{center}
 141 \input{images/16-e1/group2/16-e1-1258034821.tex}
 142 \end{center}
 143 \caption{{\tt images/16-e1/group2/16-e1-1258034821.tex}: 63~Komparatoren in
 144 10~Schichten.}
 145 \label{fig:16-e1-1258034821}
 146 \end{figure}
 147
 148 \begin{figure}
 149 \begin{center}
 150 \input{images/16-e1/group2/16-e1-1259054993.tex}
 151 \end{center}
 152 \caption{{\tt images/16-e1/group2/16-e1-1259054993.tex}: 63~Komparatoren in
 153 10~Schichten.}
 154 \label{fig:16-e1-1259054993}
 155 \end{figure}
 156
 157 \begin{figure}
 158 \begin{center}
 159 \input{images/16-e1/group2/16-e1-1259058588.tex}
 160 \end{center}
 161 \caption{{\tt images/16-e1/group2/16-e1-1259058588.tex}: 63~Komparatoren in
 162 10~Schichten.}
 163 \label{fig:16-e1-1259058588}
 164 \end{figure}
 165
 166 %\begin{figure}
 167 %\begin{center}
 168 %\input{images/16-e1/group2/16-e1-1259063485.tex}
 169 %\end{center}
 170 %\caption{{\tt images/16-e1/group2/16-e1-1259063485.tex}: 63~Komparatoren in
 171 %10~Schichten.}
 172 %\label{fig:16-e1-1259063485}
 173 %\end{figure}
 174
 175 %\begin{figure}
 176 %\begin{center}
 177 %\input{images/16-e1/group2/16-e1-1259063618.tex}
 178 %\end{center}
 179 %\caption{{\tt images/16-e1/group2/16-e1-1259063618.tex}: 63~Komparatoren in
 180 %10~Schichten.}
 181 %\label{fig:16-e1-1259063618}
 182 %\end{figure}
 183
 184 % Gruppe 3
 185
 186 \begin{figure}
 187 \begin{center}
 188 \input{images/16-e1/group3/16-e1-1258012027.tex}
 189 \end{center}
 190 \caption{{\tt images/16-e1/group3/16-e1-1258012027.tex}: 63~Komparatoren in
 191 10~Schichten.}
 192 \label{fig:16-e1-1258012027}
 193 \end{figure}
 194
 195 \begin{figure}
 196 \begin{center}
 197 \input{images/16-e1/group3/16-e1-1258037039.tex}
 198 \end{center}
 199 \caption{{\tt images/16-e1/group3/16-e1-1258037039.tex}: 63~Komparatoren in
 200 10~Schichten.}
 201 \label{fig:16-e1-1258037039}
 202 \end{figure}
 203
 204 \begin{figure}
 205 \begin{center}
 206 \input{images/16-e1/group3/16-e1-1259065042.tex}
 207 \end{center}
 208 \caption{{\tt images/16-e1/group3/16-e1-1259065042.tex}: 63~Komparatoren in
 209 10~Schichten.}
 210 \label{fig:16-e1-1259065042}
 211 \end{figure}
 212
 213 % Gruppe 4
 214
 215 \begin{figure}
 216 \begin{center}
 217 \input{images/16-e1/group4/16-e1-1259060520.tex}
 218 \end{center}
 219 \caption{{\tt images/16-e1/group4/16-e1-1259060520.tex}: 63~Komparatoren in 10~Schichten.
 220 (Gruppe~4).}
 221 \label{fig:16-e1-1259060520}
 222 \end{figure}
 223
 224 \begin{figure}
 225 \begin{center}
 226 \input{images/16-e1/group4/16-e1-1259067171.tex}
 227 \end{center}
 228 \caption{{\tt images/16-e1/group4/16-e1-1259067171.tex}: 63~Komparatoren in 10~Schichten.
 229 (Gruppe~4).}
 230 \label{fig:16-e1-1259067171}
 231 \end{figure}
 232