1 \documentclass[a4paper,10pt]{article}
2 \usepackage[utf8]{inputenc}
6 \usepackage{amsmath, bbm}
12 %\usepackage{longtable}
13 \usepackage{subfigure}
17 \usetikzlibrary{arrows,shapes}
20 \usepackage{mathtools}
22 \geometry{paper=a4paper,margin=30mm}
26 %\fancyhead[LO,LE]{"Ubung zu Computational Intelligence}
27 %\fancyhead[CO,CE]{2006-05-15}
28 %\fancyhead[RO,RE]{Florian Forster (2099894)}
30 \title{Evolutionäre Optimierung von Sortiernetzwerken}
31 \author{Florian Forster}
34 \newcommand{\false}{\textsc{False}}
35 \newcommand{\true}{\textsc{True}}
36 \newcommand{\todo}[1]{{\bf TODO:} #1}
37 \newcommand{\qed}{\hfill $\Box$ \par \bigskip}
39 \newtheorem{definition}{Definition}
40 \newtheorem{satz}{Satz}
42 % Zeige Nummern nur bei referenzierten Gleichungen an.
43 \mathtoolsset{showonlyrefs=true}
47 \tikzstyle{vertex} = [circle,draw,thick,fill=black,minimum size=5,inner sep=0pt]
48 \tikzstyle{comp} = [draw,thick,-]
49 \tikzstyle{compup} = [draw,thick,->]
50 \tikzstyle{compdown} = [draw,thick,<-]
51 \tikzstyle{edge} = [draw,thick,-]
52 \tikzstyle{diredge} = [draw,thick,->]
53 \tikzstyle{prob} = [font=\tiny]
55 \tikzstyle{edge minimum} = [edge,color=blue!20]
56 \tikzstyle{edge maximum} = [edge,color=red!20]
57 \tikzstyle{vertex active minimum} = [vertex,color=blue!50, fill=blue!50]
58 \tikzstyle{vertex active maximum} = [vertex,color=red!50, fill=red!50]
59 \tikzstyle{vertex inactive minimum} = [vertex,color=blue!20, fill=blue!20]
60 \tikzstyle{vertex inactive maximum} = [vertex,color=red!20, fill=red!20]
61 \tikzstyle{vertex inactive minimum maximum} = [vertex,color=black!20, fill=black!20]
62 \tikzstyle{comp active minimum} = [comp]
63 \tikzstyle{comp active maximum} = [comp]
64 \tikzstyle{comp inactive minimum} = [comp,color=blue!20]
65 \tikzstyle{comp inactive maximum} = [comp,color=red!20]
66 \tikzstyle{comp inactive minimum maximum} = [comp,color=black!20]
68 \tikzstyle{red box} = [draw,-,color=red, top color=red!2,bottom color=red!10]
69 \tikzstyle{blue box} = [draw,-,color=blue,top color=blue!2,bottom color=blue!10]
70 \tikzstyle{green box} = [draw,-,color=teal,top color=teal!2,bottom color=teal!10]
71 \tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10]
75 Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
76 vorgestellt (Off-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
77 Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
78 Evolutionäre Algorithmen werden beschrieben und ein evolutionärer
79 Algorithmus für die Optimierung von Sortiernetzwerken wird angegeben.
80 Die mindestens von diesem Algorithmus erreichte Güte wird angegeben und die
81 Transformation zu einer Markov-Kette wird gezeigt. {\em Natürlich: So fern ich
82 das hinbekomme bzw. Recht behalte.}
89 \section{Motivation und Einleitung}
91 \subsection{Motivation}\label{sect:motivation}
94 \item Sortiernetzwerke sind toll, weil $\ldots$
95 \item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
96 \item Bisher noch kein evolutionärer Algorithmus zur automatischen
97 Optimierung von Sortiernetzwerken bekannt. \textit{(Glaube ich zumindest.)}
100 \subsection{Einleitung}\label{sect:einleitung}
102 \subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke}
104 {\em Komparatoren} sind die Bausteine, die {\em Sortiernetzwerken} zugrunde
105 liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten können.
106 Ausserdem besitzt ein {\em Komparator} zwei Ausgänge, die im Gegensatz zu den
107 Eingängen unterscheidbar sind: Die grö"sere der beiden Zahlen wird immer auf
108 dem einen, die kleinere der beiden Zahlen immer auf dem anderen Ausgang
111 Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die
112 Ausgänge von Komparatoren mit dem Eingängen anderer Komparatoren verbindet,
113 erhält man ein {\em Komparatornetzwerk}.
117 \input{images/einfaches_komparatornetzwerk.tex}
119 \caption{Einfaches Komparatornetzwerk mit vier Ein- bzw. Ausgängen, bestehend
121 \label{fig:einfaches_komparatornetzwerk}
124 Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
125 Komparatornetzwerk aus fünf Komparatoren in der üblichen Darstellungsweise:
126 Die horizontalen Linien stellen Leitungen von den Eingängen auf der linken
127 Seite zu den Ausgängen auf er rechten Seite dar. Die vertikalen Pfeile
128 symbolisieren die Komparatoren, die die Werte "`auf den Leitungen"'
129 vergleichen und ggf. vertauschen. Nach einem Komparator befindet sich die
130 kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
131 befindet sich auf der Leitung auf der der Pfeil seinen Ursprung hat.
133 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
134 gleichzeitig angewandt werden. Das Beispiel in
135 Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
136 vergleicht in einem ersten Schritt die zwei oberen und die zwei unteren
137 Leitungen gleichzeitig. Eine Gruppe von Komparatoren, die gleichzeitig
138 angewendet werden können, nennt man eine \emph{Schicht} des
139 Komparatornetwerks. Die \emph{Verzögerung} eines Komparatornetzwerks ist
140 gleichbedeutend mit der Anzahl der Schichten, in die sich die Komparatoren
141 mindestens gruppieren lassen, da sie die Anzahl der benötigten parallelen
144 Komparatornetzwerke, die für jede beliebige Eingabepermutation eine
145 Ausgabe erzeugen, die der Sortierung der Eingabe entspricht, heißen
146 {\em Sortiernetzwerke}. Das in
147 Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
148 ist kein Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ würde zur Ausgabe
149 ${(2, 1, 3, 4)}$ führen -- die bestehenden Sortierung wird also sogar
152 Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
153 {\em nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich.
154 Dieses Gegenbeispiel zu finden ist allerdings aufwendig.
156 \todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein
157 Netzwerk sortiert, ist doch NP-vollständig, also müsste doch das Finden eines
158 Gegenbeispiels im Allgemeinen auch exponentialle Laufzeit haben..?}
159 \todo{Wenn die {\em Entscheidung}, ob ein Netzwerk sortiert, NP-vollständig
160 ist, müsse man dann nicht einen Zeugen für die Sortiereigenschaft angeben
165 Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft
166 besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen
167 ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle
168 $2^n$~0-1-Folgen sortiert.
172 \item Ein Komparator-Netzwerk ist $\ldots$
173 \item Ein Komparator-Netzwerk ist ein Sortiernetzwerk, wenn $\ldots$
174 \item Die Frage nach der Sortiereigenschaft ist NP-vollständig.
177 \subsubsection{Evolutionäre Algorithmen}
179 Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
180 entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
181 $NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte
182 sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$
183 liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese
184 Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese
185 Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer
186 Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit
187 praktikablen Zeitkonstanten gefunden werden.
189 Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
190 die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus
191 zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser
192 Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
193 beispielsweise immitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
194 auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
196 Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
197 ist es, bestehende Lösungen zu neuen, unter Umständen besseren Lösungen zu
198 kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
199 Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem häufig
200 als {\em Individuum} bezeichnet.
202 Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
203 bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen
204 ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
205 Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
206 verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
207 integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
208 Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
209 werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em
212 Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
213 sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
214 aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
215 es oft einfach ist {\em irgendeine} Lösung anzugeben. Zum anderen muss eine
216 Methode für die Rekombination existieren. Das insbesondere dann problematisch
217 wenn {\em Nebenbedingungen} eingehalten werden müssen.
220 \item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$
221 \item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die
222 Mutation \textit{(vermutlich)} nicht (effizient) möglich.
225 \section{Bekannte konstruktive Sortiernetzwerke}
227 Übersicht über bekannte konstruktive Sortiernetzwerke.
229 \subsection{Das Odd-Even-Transpositionsort-Netzwerk}
230 \label{sect:odd_even_transpositionsort}
232 Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der
233 einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
234 "`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
235 Abbildung~\ref{fig:odd-even-transposition-08} zeigt das OET-Netzwerk für
240 \input{images/oe-transposition-8.tex}
242 \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.}
243 \label{fig:odd-even-transposition-08}
246 Dass das Odd-Even-Transporitionsort-Netzwerk tatsächlich jede beliegibe
247 Eingabe sortiert ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass
248 sowohl das Minimum als auch das Maximum durch das im Netzwerk enthaltene
249 Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt. Beim
250 Odd-Even-Transporitionsort-Netzwerk mit drei Eingängen,
251 $\operatorname{OET}(3)$, ist die Ausgabe folglich sortiert.
253 Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen,
254 indem man $\operatorname{OET}(n)$ auf $\operatorname{OET}(n-1)$ durch
255 Herausschneiden einer Leitung reduziert. In
256 Abschnitt~\ref{sect:leitungen_entfernen} wird das Vorgehen im Detail
257 beschrieben, Abbildung~\ref{fig:oe-transposition-cut} zeigt das
258 Herausschneiden einer Leitung aus $\operatorname{OET}(8)$.
260 Das Odd-Even-Transporitionsort-Netzwerk ist weder in Bezug auf die Anzahl der
261 Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen sich die
262 Komparatoren anordnen lassen, effizient. Es benötigt
263 ${\frac12 n (n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten
264 angeordnet sind. Andere Sortiernetzwerke benötigen deutlich weniger
265 Komparatoren, beispielsweise $\mathcal{O}(n (\log n)^2)$, die in weniger
266 Schichten, zum Beispiel $\mathcal{O}(\log n)$, angeordnet sind.
268 Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
269 folgenden Algorithmen benötigen ein (einfaches) Sortiernetzwerk als
270 Starteingabe, auf dessen Basis sie versuchen optimierte Sortiernetzwerke zu
271 finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
274 \subsection{Das bitone Mergesort-Netzwerk}
276 Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
277 Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968}
278 veröffentlicht wurde. Es ist deutlich effizienter als das
279 Odd-Even-Transporitionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
280 Komparatoren als auch bezüglich der benötigten Zeit, also der Anzahl der
283 Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei
284 sortierte Listen zusammenfügen (englisch: \textit{to~merge}) kann. Dieser
285 \emph{„bitoner Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein
286 verleiht dem Sortiernetzwerk seinen Namen.
288 Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
289 Instanzen des Netzwerks, deren Leitungszahl eine Zweierpotenz ist,
290 $\operatorname{BS}(n = 2^t)$.
292 \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
294 Das \emph{bitone Mergesort-Netzwerk} basiert auf dem sogenannten \emph{bitonen
295 Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine beliebige
296 \emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine \emph{bitone
297 Folge} ist eine monoton steigende Folge gefolgt von einer monoton absteigenden
298 Folge, oder ein zyklischer Shift davon. Abbildung~\ref{fig:beispiel-biton}
299 zeigt die vier prinzipiellen Möglichkeiten die durch zyklische Shifts
300 entstehen können. Die wichtigsten Varianten für das \emph{bitone
301 Mergesort-Netzwerk} zeigen die Abbildungen~\ref{fig:beispiel-biton-0}
302 und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und
303 eine absteigend sortierte Liste aneinanderhängt. Bei den anderen beiden Formen
304 ist wichtig zu beachten, dass das letzte Element nicht größer
305 (Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner
306 (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein
311 \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}}
312 \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}}
313 \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}}
314 \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}}
315 \caption{Beispiele bitoner Folgen.}
316 \label{fig:beispiel-biton}
321 \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
323 \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
324 \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
325 aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
326 der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
327 resultierenden Teilfolgen sind wiederum biton.}
328 \label{fig:bitonic-merge-schema}
331 Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
332 ${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und
333 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend
334 sortiert, die Folge $V$ sei absteigend sortiert:
336 u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
337 v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
339 Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen
340 Positionen verglichen und ggf. vertauscht:
342 u_i \longleftrightarrow v_i, \quad 0 \leqq i < m
344 Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die
345 durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass
346 Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$
347 gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1}
348 > v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
349 vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
350 "`linken"' Folge, $u_{m-1}$, kleiner ist als das kleinste Element der
351 "`rechten"' Folge, $v_{m-1}$. Daraus folgt, dass das Resultat in zwei bitone
352 Folgen aufteilen lässt: Eine aufsteigende~/ absteigende Folge und eine
353 absteigende~/ aufsteigende Folge. Abbildung~\ref{fig:bitonic-merge-normal}
354 zeigt die Situationen vor und nach diesem Schritt des Mischers.
356 Um die Folge vollständig zu sortieren, müssen anschließend die beiden
357 resultierenden bitonen Folgen sortiert werden. Die geschieht ebenfalls
358 mithilfe des bitonen Mischers, mit zwei Instanzen von
359 $\operatorname{BM}(\frac{n}{2})$. Diese rekursive Definition endet mit dem
360 bitonen Mischer mit zwei Leitungen, $\operatorname{BM}(2)$, der als
361 Komparator-Netzwerk mit einem Komparator zwischen den beiden Leitungen
364 Der bitonen Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist
365 lediglich eine etwas modifizierte Vergleichs-Kaskade im ersten Schritt
366 notwendig. Die folgenden, kleineren Mischer erhalten als Eingabe wieder eine
367 „echte“ bitone Folge. Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das
368 Schema des bitonen Mischers für zwei aufsteigend sortierte Foglen. Durch das
369 Umdrehen einer Folge verändert sich das Muster der Komparatoren ein wenig:
370 Statt an eine Treppe erinnert das Muster nun an einen Trichter.
372 Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
373 die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
374 $\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus
375 $\frac{1}{2} n \log(n) = \mathcal{O}\left(n \log(n)\right)$~Komparatoren
376 besteht, die in $\log(n)$~Schichten angeordnet werden können.
378 \subsubsection{Das bitone Mergesort-Netzwerk}
380 Ebenso wie der bitone Mischer $\operatorname{BM}(n)$ ist auch das \emph{bitone
381 Mergesort-Netzwerk} $\operatorname{BS}(n)$ rekursiv definiert. Es setzt sich
382 zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe,
383 $\operatorname{BS}(\frac{n}{2})$, für je die Hälfte der Eingänge, sowie dem
384 bitonen Mischer für $n$~Leitungen, $\operatorname{BM}(n)$. Das Rekursionsende
385 ist das bitone Mergesort-Netzwerk mit nur einer Leitung,
386 $\operatorname{BS}(1)$, welches als leeres Komparatornetzwerk definiert ist.
387 Entsprechend sind die Komparatornetzwerke $\operatorname{BM}(2)$ und
388 $\operatorname{BS}(2)$ identisch.
390 Bei der Konstruktion kommt die trichterförmige Anordnung der Komparatoren
391 (Abbildung~\ref{fig:bitonic-merge-tricheter}) gelegen, weil so die beiden
392 rekursiven Sortiernetzwerke in die gleiche Richtung sortieren können und so
393 alle Komparatoren in die gleiche Richtung zeigen.
397 \input{images/batcher-8.tex}
399 \caption{$\operatorname{BS}(8)$, Batchers {\em bitones Mergesort-Netzwerk}
400 für acht Eingänge. Markiert sind die beiden Instanzen von
401 $\operatorname{BS}(4)$ (rot), die beiden bitonen
402 Mischer~$\operatorname{BM}(4)$ (blau) und die Komparatoren, die im letzten
403 rekursiven Schritt hinzugefügt wurden (grün).}
404 \label{fig:bitonic-08}
407 Das konkrete Netzwerk~$\operatorname{BS}(8)$ ist in
408 Abbildung~\ref{fig:bitonic-08} zu sehen. Eingezeichnet sind ebenfalls die
409 beiden Instanzen des Netzwerks~$\operatorname{BS}(4)$ (rot) sowie der bitone
410 Mischer~$\operatorname{BM}(8)$ (blau). Die trichterförmige Komparator-Kaskade,
411 die die bitone Eingabefolge in zwei bitone Ausgabefolgen transformiert, ist
414 Das \emph{bitone Mergesort-Netzwerk} $\operatorname{BS}(8)$ besteht aus
415 $\frac{1}{4} n \log(n) \log(n+1) = \mathcal{O}\left(n (log (n))^2\right)$
416 Komparatoren, die in $\frac{1}{2} \log(n) \log(n+1) = \mathcal{O}(\log(n))$
417 Schichten angeordnet sind.
421 %\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
423 %\caption{Rekursiver Aufbau von $S(n)$: Es besteht aus zwei Instanzen von
424 %$S(n/2)$ und dem Mischer $M(n)$.}
425 %\label{fig:bms_rekursiver_aufbau}
428 \subsection{Das Odd-Even-Mergesort-Netzwerk}
430 Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk}
431 (OES) und das \emph{Odd-Even-Transpositionsort-Netzwerk} (siehe
432 Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Vielmehr ist
433 OES dem \emph{bitonen Mergesort-Netzwerk}, das im vorherigen Abschnitt
434 vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von
435 \textit{Kenneth~E. Batcher} gefunden worden und ist ebenfalls in~\cite{B1968}
436 beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht
437 darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist.
439 \subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer}
441 Der \emph{Odd-Even-Mischer} $\operatorname{OEM}(n,m)$ ist ein
442 Komperatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$
443 Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
444 zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
445 \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}
446 vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even-Mischer} unter
447 Umständen mehr Schichten als der \emph{bitone Mischer}.\footnote{Knuth,
448 “Bitonic Sorting”, Seite~230}
450 Der \emph{Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
451 Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
452 sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
453 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
454 $W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
456 w_i = \left\{ \begin{array}{ll}
465 \input{images/oe-merge.tex}
467 \caption{Schematischer Aufbau des {\em Odd-Even} Mischers. Im Vergleich zum
468 bitonen Mischer für Acht kommt dieses Schema mit einem Komparator weniger
469 aus. Der Effekt wird duch den rekursiven Aufbau noch verstärkt.}
473 Diese werden in insgesamt vier sortierte Folgen aufgeteilt, je eine Liste der
474 geraden Indizes und je eine Liste der ungeraden Indizes.
476 U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\
477 U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
478 V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\
479 V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
482 Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die
483 ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden
484 rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am
485 Ausgang der Mischer die Folgen
487 W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
488 W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
492 Anschließend werden die Komparatoren zwischen benachbarten Leitungen
495 w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
497 die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em
498 Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}.
500 Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
501 Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
502 entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
503 offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
506 \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
507 \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
508 einzelnen Komparator.
511 Dass die resultierende Folge sortiert ist, lässt sich mit dem
512 {\em 0-1-Prinzip} zeigen:
513 Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden
514 Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder
515 gleich der Anzahl der Nullen in den ungeraden Teilfolgen
516 $U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ --~die Einsen verhalten
517 sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen
518 $W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu:
520 \left|W_{\textrm{gerade}}\right|_0
521 &=& \left|U_{\textrm{gerade}}\right|_0
522 + \left|V_{\textrm{gerade}}\right|_0
523 = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
524 + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
525 \left|W_{\textrm{ungerade}}\right|_0
526 &=& \left|U_{\textrm{ungerade}}\right|_0
527 + \left|V_{\textrm{ungerade}}\right|_0
528 = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
529 + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
531 Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
532 als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
533 Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
534 wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthählt als
535 $W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die
536 Ausgabe zu sortieren. Diese wird von den Komparatoren, die benachbarte
537 Leitungen miteinander vergleichen, ausgeführt. Die jeweiligen Situationen sind
538 in Abbildung~\ref{fig:oe-post-recursive} dargestellt.
542 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
544 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
546 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
547 \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
548 kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der
549 Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
550 letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
552 \label{fig:oe-post-recursive}
555 Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,
556 bricht die Rekursion nach $\mathcal{O}\left(\log (n) + \log (m)\right)$
557 Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
558 Schichten im Mischer-Netzwerk), hängt von der Längeren der beiden
559 Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.
561 Die Anzahl der Komparatoren $K(n,m)$, die $\operatorname{OEM}(n,m)$ im
562 allgemeinen Fall verwendet, ist Gemäß der rekursiven Definition in
563 Abhängigkeit der Länge der Eingabefolgen, $n$ und $m$:
565 K(n,m) = \left\{ \begin{array}{ll}
566 nm, & \mathrm{falls} \quad nm \leqq 1 \\
567 K\left(\left\lceil \frac{n}{2} \right\rceil, \left\lceil \frac{m}{2} \right\rceil\right)
568 + K\left(\left\lfloor \frac{n}{2} \right\rfloor, \left\lfloor \frac{m}{2} \right\rfloor\right)
569 + \left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor & \mathrm{falls} \quad nm > 1
572 Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
573 anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
574 dass $K(n,m)$ in $\mathcal{O}(N \log (N))$ enthalten ist.
576 Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$, lässt sich die Anzahl
577 der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der erste
578 Rekursionsschritt der OEM-Konstruktion fügt
579 $\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$
580 Komparatoren ein -- einen Komparator weniger als der \emph{bitone Mischer} in
581 diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer,
582 $\operatorname{OEM}(\frac{n}{2}, \frac{n}{2})$ und so weiter bis
583 einschließlich $\operatorname{OEM}(2, 2)$, von denen es $2, 4, \dots,
584 \frac{N}{4} = 2^{\log(N)-2}$ Instanzen gibt. Insgesamt werden
586 \sum_{i=0}^{\log(N)-2} 2^i = 2^{\log(N) - 1} - 1 = \frac{N}{2} - 1 = n - 1
588 Komparatoren eingespart. Damit ergibt sich
590 K\left(n = 2^{t-1}, n = 2^{t-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
592 für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^t)$
595 \subsubsection{Das Odd-Even-Mergesort-Netzwerk}
597 Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht, --~wie
598 das \emph{bitonen Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
599 sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die
600 effizientesten Sortiernetzwerke in Bezuf auf Komparator- und Schichtzahl
601 entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
602 $\operatorname{OES}(n)$ aus
603 $\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$,
604 $\operatorname{OES}\left(\left\lfloor\frac{n}{2}\right\rfloor\right)$
605 und $\operatorname{OEM}\left(\left\lceil\frac{n}{2}\right\rceil,
606 \left\lfloor\frac{n}{2}\right\rfloor\right)$. Die Rekursion endet mit
607 $\operatorname{OES}(1)$ und $\operatorname{OES}(0)$, die als leere
608 Komparatornetzwerke definiert sind.
612 \input{images/oe-mergesort-8.tex}
614 \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
615 sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden
616 \emph{Odd-Even-Mischer} $\operatorname{OEM}(4)$ für gerade und ungerade
617 Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
618 Komparatoren zwischen benachbarten Leitungen (grün).}
619 \label{fig:odd-even-mergesort-08}
622 In Abbildung~\ref{fig:odd-even-mergesort-08} ist das konkrete Sortiernetzwerk
623 $\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven
624 Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den
625 \emph{Odd-Even-Mischer} für acht Leitungen dar: Die beiden blauen Blöcke sind
626 die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
627 die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
629 Im Allgemeinen ist die Anzahl der Komparatoren, die vom
630 \emph{Odd-Even-Mergesort-Netzwerk} verwendet wird, $k(n)$, direkt aus der
631 Definition beziehungsweise der Konstruktionsanleitung abzulesen:
633 k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
634 + k\left(\left\lfloor\frac{n}{2}\right\rfloor\right)
635 + K\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor\right)
637 Eine geschlossene Form dieser Formel ist schon alleine deshalb schwierig, weil
638 sie für $K(n,m)$ schwierig anzugeben ist. Es ist allerdings bekannt, dass
639 $k(n)$ in $\mathcal{O}\left(n \left(\log (n)\right)^2\right)$ enthalten ist.
641 Für den wichtigen Spezialfall, dass $n = 2^t$ eine Zweierpotenz ist, kann die
642 Anzahl der Komparatoren wieder explizit angegeben werden. \textit{K.~Batcher}
643 zeigt in seiner Arbeit\footnote{\todo{Referenz!}}, dass in diesem Fall
645 k(n = 2^t) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
650 % oem(n,m) = ((n*m) <= 1) ? (n*m) : oem(ceil(.5*n), ceil(.5*m)) + oem(floor(.5*n), floor(.5*m)) + floor(.5*(n+m-1.0))
651 % oem1(n) = oem(ceil(.5*n),floor(.5*n))
652 % oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)
655 %\item Pairwise sorting-network
658 \section{Transformation von Sortiernetzwerken}
660 \subsection{Komprimieren}
662 \todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}
664 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
665 gleichzeitig ausgewertet werden, wie bereits in
666 Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
667 \emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
668 von \emph{Schichten} verstanden.
670 Diese Anzahl ist insbesondere beim automatisierten Bewerten von
671 Komparatornetzwerken interessant. \dots
673 \subsection{Normalisieren}
677 \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
678 \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
679 \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
680 transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
681 intuitiven Konstruktion und die normalisierte Variante.}
682 \label{fig:beispiel_normalisieren}
685 Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
686 ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
687 zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
688 transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis})
689 einen Algorithmus an.
691 Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
692 bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
693 zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
694 Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
695 die unter und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei
696 Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist.
697 In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven
700 In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
701 Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche
702 Richtung. Statt dem typischen "`Treppenmuster"' sind abwechselnd das Treppen-
703 und das Trichtermuster zu sehen.
705 \subsection{Zwei Netzwerke kombinieren}
707 Um Sortiernetzwerke als \emph{Individuen} evolutionärer Algorithmen verwenden
708 zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen
709 Sortiernetzwerk zusammenzufassen.
711 Wir haben diese Technik in den vorangegangen Abschnitten bereits verwendet,
712 beispielsweise um zwei \emph{bitone Mergesort-Netzwerke} mit jeweils der
713 halben Leitungszahl, $\operatorname{BS}\left(\frac{n}{2}\right)$, zu einem
714 einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das
715 \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ wurde auf diese Art
716 und Weise rekursiv aufgebaut.
718 Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte
719 Folgen. \emph{Wie} diese Folgen sortiert wurden, ist unerheblich. Entsprechend
720 können wir beliebige Sortiernetzwerke einsetzen, um die beiden Eingabefolgen
721 zu sortieren, und die Ausgaben mit einem der beschriebenen Mischer
724 Beispielsweise kann man die Ausgabe von zwei \emph{bitonen
725 Mergesort-Netzwerken} $\operatorname{BS}(8)$ mit je acht Leitungen mit dem
726 \emph{Odd-Even-Merge} $\operatorname{OEM(8,8)}$ zu einer sortierten
727 Gesamtfolge zusammenfügen. Das resultierende Sortiernetzwerk besitzt
728 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
729 80~Komparatoren, $\operatorname{OES}(16)$ nur 63).
731 Verbesserungen in der Anzahl der benötigten Komparatoren beziehungsweise der
732 Schichten eines „kleinen“ Sortiernetzwerks übertragen sich direkt auf das
733 resultierende Gesamtnetzwerk. Das \emph{Odd-Even-Mergesort-Netzwerk}
734 $\operatorname{OES}(9)$ benötigt beispielsweise 26~Komparatoren, die in in
735 neun Schichten angeordnet sind. Es sind allerdings Sortiernetzwerke mit neun
736 Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten
737 benötigen. Kombiniert man zwei dieser Netzwerke mit dem
738 \emph{Odd-Even-Mischer} erhält man ein Sortiernetzwerk mit 18~Eingängen, das
739 80~Komparatoren in 11~Schichten benötigt -- $\operatorname{OES}(18)$ benötigt
740 82~Komparatoren in 13~Schichten. Damit ist das resultierende Netzwerk so
741 schnell wie das Sortiernetzwerk mit 18~Eingängen, das \textit{Baddar} und
742 \textit{Batcher} in ihrer Arbeit „An 11-Step Sorting Network for 18~Elements“
743 vorstellen, benötigt aber 6~Komparatoren weniger.
757 Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
758 ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
759 sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
760 Aneinanderreihung der Art „die ersten $x$~Schichten des einen, dann die
761 letzten $y$~Schichten des anderen Sortiernetzwerks“ zerstören im Allgemeinen
762 die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden
763 Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
764 nur mit exponentiellem Aufwand möglich ist.
767 %\item Mit dem Bitonic-Merge
768 %\item Mit dem Odd-Even-Merge
769 %\item Nach dem Pairwise sorting-network Schema.
772 \subsection{Leitungen entfernen}\label{sect:leitungen_entfernen}
774 Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von
775 \emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
776 ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen
777 beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass
778 sich die Anzahl der Eingänge nicht verändert. Das heißt, dass wir wieder ein
779 Sortiernetzwerk mit $n$~Eingängen erhalten müssen.
781 Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
782 Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung
783 „eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem
784 bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maxim
785 durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an einem der
786 „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten Index.
787 Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und welche
788 dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum jeden
789 Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
790 Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
791 das {\em Odd-Even-Transpositionsort-Netzwerk}.
795 \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
796 \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
797 \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
798 \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
799 \caption{Eine Leitung wird aus dem
800 \emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(8)$ entfernt:
801 Auf der rot markierten Leitung wird $\infty$ angelegt. Da der Wert bei jedem
802 Komparator am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die
803 restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
804 Pfad herausgetrennt werden. In der letzten Abbildung ist
805 $\operatorname{OET}(7)$ markiert.}
806 \label{fig:oe-transposition-cut}
809 Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
810 ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt
811 haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
812 Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
813 zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
814 ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
815 das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
816 auf die keine Komparatoren mehr berührt
817 (Abbildung~\ref{fig:oe-transposition-cut1}).
819 Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
820 Komparatornetzwerk immernoch sortiert werden: Wir haben lediglich die Position
821 des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss die
822 Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum liegt.
823 Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme
824 auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage
825 getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
826 mit $(n-1)$~Elementen darstellen.
828 Wenn wir die Minimum- beziehungsweise Maximum-Leitung entfernen
829 (Abbildung~\ref{fig:oe-transposition-cut2}), bleibt das Sortiernetzwerk für
830 $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung ein Minimum oder ein
831 Maximum angenommen wird, bezeichnen wir das eliminieren einer Leitung als
832 \emph{Minimum-Schnitt} beziehungsweise \emph{Maximum-Schnitt}.
834 Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
835 Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
836 markierten Komparatoren wurden verschoben, so dass sich eine kompaktere
837 Darstellung ergibt. Ausserdem ist das
838 {\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der
839 zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
840 Ausgabe und kann entfernt werden.
842 \subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
843 \label{sect:anzahl_schnittmuster}
845 Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
846 Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
847 $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können wir auf diese Art und
848 Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
849 mit $n$~Eingängen reduzieren. Das Anwenden mehrerer Minimum- und
850 Maximum-Schnitte bezeichnen wir als \emph{Schnittmuster}.
852 Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
853 auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
854 Schnittmuster \emph{unterschiedlich} bezüglich~$S$.
856 Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
857 Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
858 auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
859 ein $n$-Sortiernetzwerk auf ein $m$-Sortiernetzwerk zu reduzieren, ergeben
862 \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
865 \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
866 unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung
867 und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks,
868 führen beide Reihenfolgen zum selben Ergebnis.
870 \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass
871 es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise
872 Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster
873 reduziert, die Menge der so erzeugbaren Sortiernetzwerke bleibt aber
874 unverändert. Die Anzahl der möglichen Schnittmuster setzt sich zusammen aus
875 der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
876 und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
877 Formel für die Anzahl der Schnittmuster:
879 2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
880 = 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
881 = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!}
885 Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden
886 Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
887 ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schmittmuster mit
888 16~Schnitten notwendig, für das es bereits etwa ${3,939 \cdot 10^{13}}$
889 Möglichkeiten gibt. Ein Ausprobieren aller Möglichkeiten ist für große
890 Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich.
892 Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
893 als die Anzahl der möglichen Schnittmuster. Für jeden Komparator auf der
894 ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
895 Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
896 unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
897 der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die
900 Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe
901 Ausgangmuster abgebildet, weil die Position des Minimums beziehungsweise des
902 Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun
903 unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster
904 erzeugen. In der zweiten und allen folgenden Schichten kann man diesen
905 Unterschied nicht mehr erkennen. In allen sechs Fällen, in denen sich die
906 Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass
907 sich die Resultate auch in der ersten Schicht nicht unterscheiden.
909 \subsubsection{Der \textsc{SN-Evolution-Cut}-Algorithmus}
910 \label{sect:sn-evolution-cut}
912 Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
913 Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
914 Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
915 möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
916 von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
917 Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
918 gute Schnittmuster gesucht.
920 Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster}
921 als Individuen. Um zwei Individuen zu rekombinieren werden die ersten
922 $r$~Schnitte des einen Schnittmusters verwendet und die letzten
923 ${c-r}$~Schnitte des zweiten Schmittmusters. $r$ ist eine Zufallsvariable mit
926 Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
927 auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
930 % bitones Mergesort-Netzwerk
932 In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka},
933 wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
934 durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen
935 Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer
936 sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert
937 werden, Komparatoren ein.
939 Beispeilsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
940 Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
941 konstruiert wurde. Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger
942 als das bitone Mergesort-Netzwerk nach Batchers Methode. Gegenüber Batchers
943 Methode sparen so konstruierte Sortiernetzwerke ${\frac{1}{4}n(\log n - 1)}$
948 \input{images/16-ec-1277186619.tex}
950 \caption{{\tt images/16-ec-1277186619.tex}: Sortiernetzwerk mit 16~Leitungen
951 und 68~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem
952 Algorithmus \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
953 $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
954 \label{fig:16-ec-1277186619}
957 Startet man {\sc SN-Evolution-Cut} mit dem bitonen Mergesort-Netzwerk
958 $\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
959 Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
960 16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in
961 Abbildung~\ref{fig:16-ec-1277186619} zu sehen.
963 % Odd-Even-Transpositionsort-Netzwerk
965 Betrachtet man das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619}, so
966 ist keine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$
967 erkennbar -- insbesondere die ersten Schichten des Netzwerks scheinen rein
968 zufällig zu sein. Dies ist jedoch kein Eigenschaft des Algorithmus, sondern
969 hängt insbesondere von der Eingabe ab. Wird \textsc{SN-Evolution-Cut}
970 beispielsweise mit dem \emph{Odd-Even-Transpositionsort-Netzwerk}
971 $\operatorname{OET}(n)$ und $m$~Schnitten gestartet, so ist das beste Ergebnis
972 immer das $\operatorname{OET}(n-m)$-Netzwerk.
976 \input{images/16-ec-from-ps32.tex}
978 \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
979 10~Schichten. Das Netzwerk wurde von dem Algorithmus
980 \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk}
981 $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.}
982 \label{fig:16-ec-from-ps32}
985 % Pairwise-Sorting-Netzwerk
987 Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
988 $\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
989 Pairwise Sorting Network“ \cite{P1992} definiert. Startet man
990 \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
991 16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, dass die gleiche
992 Anzahl an Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und
993 $\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
994 Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
996 Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht
997 einsetzt und auch nicht auf einem Mischer basiert, ist der
998 $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
999 Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
1000 den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzerke, die
1001 strukturell identisch zu $\operatorname{PS}(8)$ sind -- die Schichten~1 und~2
1002 sowie 4~und~5 sind vertauscht, was jeweils zum selben Ergebnis nach dem
1003 Schichtenpaar führt.
1006 \textit{Eingang}_i = \left\{ \begin{array}{rl}
1007 -\infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{0, 6\} \\
1008 \infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{2, 4\} \\
1009 ? & \quad \mathrm{sonst}
1015 \input{images/32-pairwise-cut-16-pairwise.tex}
1017 \caption{PS(32) mit 16 Schnitten zu PS(16).}
1018 \label{fig:ps16-from-ps32}
1023 \input{images/16-pairwise.tex}
1025 \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten
1026 ($\operatorname{MIN}(0,2,4,6), \operatorname{MAX}(9,11,13,15)$). Das
1027 resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.}
1028 \label{fig:16-pairwise}
1031 Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann
1032 man $\operatorname{OES}(8)$ erhalten.
1034 % Odd-Even-Mergesort-Netzwerk
1036 \todo{Schreibe noch etwas zum Odd-Even-Mergesort-Netzwerk.}
1039 \item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort.
1040 \item Wie gut kann man durch wegschneiden werden?
1041 \item Wieviele Schnitte ergeben das selbe Netzwerk? Oder andersrum: Wieviele
1042 unterschiedliche Netzwerke kann ich erhalten? Wieviele Nachfolger hat ein
1043 Netzwerk / Knoten in der Markov-Kette?
1044 \item Abschnitt „Optimierung der Schnitte“ hier einbauen.
1047 \section{Der \textsc{SN-Evolution}-Algorithmus}
1049 Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
1050 die vorgestellten Methoden kombiniert.
1052 \subsection{Bewertungsfunktion}\label{sect:bewertung}
1054 Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
1055 {\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
1056 die interessant sind:
1058 \item Möglichst wenige Komparatoren ("`klein"')
1059 \item Möglichst wenige Schichten ("`schnell"')
1062 Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
1063 kleinste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
1064 in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
1067 Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
1068 berücksichtigen kann, hat die folgende allgemeine Form:
1070 \operatorname{Guete}(S) = w_{\mathrm{Basis}}
1071 + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
1072 + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
1074 Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
1075 dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
1076 gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
1077 Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
1078 jegliche Ergebnisse sind dann rein zufälliger Natur.
1080 Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
1081 genommen werden. Ist er groß, wird der relative Unterschied der Güten
1082 verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
1083 gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
1084 klein, in Abhängigkeit von den anderen beiden Parametern sind auch negative
1085 Werte möglich, werden die relativen Unterschiede groß. Dadurch wird die {\em
1086 Exploitation}, das Finden lokaler Optima, bevorzugt.
1088 \subsection{Selektion}
1092 \subsection{Rekombination}
1094 Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
1095 einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
1096 den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
1097 {\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
1098 beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
1099 Anschließend entfernen wir zufällig $n$~Leitungen wie in
1100 Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
1102 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
1105 \subsection{Mutation}
1107 Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine Mutation
1108 --~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
1109 Sortiernetzwerk zufällig zu verändern aber trotzdem die Sortiereigenschaft zu
1110 erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
1111 Eigenschaft zerstören.
1113 Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
1114 Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
1115 Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
1116 Ausprobieren aller $2^n$~Bitmuster.
1118 Um das Potenzial einer Mutation abzuschätzen habe ich in den evolutionären
1119 Algorithmus eine Überprüfung eingebaut. Unmittelbar vor dem Einfügen in die
1120 Population überprüft das Programm die Notwendigkeit jedes einzelnen
1121 Komparators. Dazu wurde nacheinander jeder Komparator entfernt und überprüft,
1122 ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt.
1125 \item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
1126 Schichten, kobiniert)
1127 \item Rekombination: Merge Anhängen und Leitungen entfernen.
1130 Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt
1131 Abbildung~\ref{fig:evolutionary_08}.
1135 \input{images/evolutionary-08.tex}
1137 \caption{Ein mit dem evolutionären Algorithmus erzeugtes Sortiernetzwerk mit
1138 acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
1139 \label{fig:evolutionary_08}
1144 \input{images/08-e2-1237993371.tex}
1146 \caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
1147 \label{fig:08-e2-1237993371}
1152 \input{images/09-e2-1237997073.tex}
1154 \caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
1155 \label{fig:09-e2-1237997073}
1160 \input{images/09-e2-1237999719.tex}
1162 \caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten}
1163 \label{fig:09-e2-1237999719}
1168 \input{images/10-e2-1239014566.tex}
1170 \caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
1171 \label{fig:10-e2-1239014566}
1177 \item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}.
1178 \item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
1181 \section{Der \textsc{SN-Markov}-Algorithmus}
1183 Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
1184 Abschnitt verwendete immer zwei zufällige Sortiernetzwerke („Individuen“) aus
1185 einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander
1186 ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal
1187 verwendet und mit sich selbst kombiniert wird.
1189 Macht man diesen Spezialfall zum Regelfall, indem man \emph{immer} das
1190 aktuelle Netzwerk mit sich selbst kombiniert und anschließend die Hälfte aller
1191 Leitungen eliminiert, lassen sich einige interessante Beobachtungen anstellen.
1192 Netzwerke, die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von
1193 $S_0$ mit sich selbst und anschließendem Eliminieren der Hälfte der Leitungen
1194 hervorgehen können, heißen \emph{Nachfolger} von $S_0$.
1196 Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
1197 gerichteten Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
1198 Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
1199 Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $S_0$
1200 ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
1201 selbst erzeugen kann.
1203 Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben ist die Anzahl
1204 (unterschiedlichen) Schnittmuster und damit die Anzahl der Nachfolger sehr
1205 groß. Wenn $S_0$ ein Sortiernetzwerk mit $n$~Leitungen ist, so hat $S_0$ bis
1208 2^n \cdot \left( \begin{array}{c} 2n \\ n \end{array} \right)
1212 Der Algorithmus {\sc SN-Markov} legt auf diesem Graph einen zufälligen Weg
1213 (englisch: \textit{random walk}) zurück. Er startet auf einem gegebenen
1214 Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu gelangen
1215 rekombiniert er das aktuelle Sortiernetzwerk mit sich selbst und erhält so
1216 einen zufälligen Nachfolger.
1219 \item $n \leftarrow \mathrm{Input}$
1220 \item \texttt{while} \textit{true}
1222 \item $n \leftarrow \operatorname{recombine} (n, n)$
1227 \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
1228 \item Anzahl der erreichbaren Sortiernetzwerke.
1229 \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen
1230 Netzwerke. (Abbildung~\ref{fig:markov-comparators-16})
1235 \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16.pdf}
1237 \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden.}
1238 \label{fig:markov-comparators-16}
1241 %\input{shmoo-aequivalenz.tex}
1243 \section{Optimierung der Schnitte}
1245 \todo{In den Abschnitt "`Leitungen entfernen"' einbauen.}
1249 \input{images/32-ec-1277190372.tex}
1251 \caption{{\tt images/32-ec-1277190372.tex}: Sortiernetzwerk mit 32~Leitungen
1252 und 206~Komparatoren in 15~Schichten. Das Netzwerk wurde von dem Algorithmus
1253 \textsc{SN-Evolution-Cut} aus dem Bitonic-Mergesort-Netzwerk $BS(64)$ durch
1254 32~Schnitte erzeugt.}
1255 \label{fig:32-ec-1277190372}
1258 Abbildung~\ref{fig:32-ec-1277190372} zeigt ein 32-Sortiernetzwerk, dass vom
1259 \textsc{SN-Evolution-Cut}-Algorithmus aus dem $BS(64)$-Netzwerk erzeugt wurde.
1260 Es besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als
1261 $BS(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler
1262 und Wankas Methode konstruiert wird. Die Anzahl der Schichten ist bei allen
1265 \textbf{TODO:} $BS(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten
1266 möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$
1267 Komparatoren; $BS(64)$: 672~Komparatoren.
1335 % images/32-ec-1277190372.tex
1337 \section{Empirische Beobachtungen}
1340 \item So schnell konvergiert der Algorithmus.
1346 Das würde mir noch einfallen$\ldots$
1348 \bibliography{references}
1349 \bibliographystyle{plain}
1355 % vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 :