From 7982d5b11345284f15de802e45e94b5a1eb82322 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Thu, 20 Jan 2011 09:45:23 +0100 Subject: [PATCH] Kleine Korrekturen. --- diplomarbeit.tex | 55 ++++++++++++++++++++++++++++++------------------------- 1 file changed, 30 insertions(+), 25 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 21ff5e0..dfa31d9 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -849,10 +849,10 @@ Ausgabe und kann entfernt werden. Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$, -$n-3$,~\dots Eingängen zu erzeugen. Insbesondere können wir auf diese Art und -Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk -mit $n$~Eingängen reduzieren. Das Anwenden mehrerer Minimum- und -Maximum-Schnitte bezeichnen wir als \emph{Schnittmuster}. +$n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und +Weise einen Sortiernetzwerke mit $2n$~Eingängen wieder auf Sortiernetzwerke +mit $n$~Eingängen reduziert werden. Mehrere Minimum- und Maximum-Schnitte, die +gleichzeitig angewendet werden, bezeichnen wir als \emph{Schnittmuster}. Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die @@ -928,7 +928,7 @@ Um die Anzahl der \emph{unterschiedlichen} Schnittmuster abschätzen zu können, wurden je eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$ angewandt. Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der -\emph{unterschiedlichen} Sortiernetzwerke gegen die Anzahl der zufälligen +\emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen Schnittmuster auf. Klar zu sehen ist, dass sich die Anzahl der erzeugten Sortiernetzwerke nach $500.000$~Iterationen nur noch gering verändert und der Wert nach $1.000.000$~Iterationen allem Anschein nach dem Endwert schon sehr @@ -940,9 +940,9 @@ führen aber nur zu wenigen \emph{unterschiedlichen} Sortiernetzwerken: 3519 ($\approx 0,1\%$) im Fall des \emph{Odd-Even-Mergesort-Netzwerks}, 4973 ($\approx 0,15\%$) beim \emph{bitonen Mergesort-Netzwerk} und 18764 ($\approx 0,57\%$) beim \emph{Pairwise-Sorting-Netzwerk}. Zwar ist es möglich, dass mehr -Iterationen die Anzahl der unterschiedlichen Netzwerke noch wachsen lässt. Die -Graphen in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der -Annahme, dass Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster +Iterationen die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. +Die Graphen in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der +Annahme, dass die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster vernachlässigbar klein ist. Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses @@ -951,7 +951,7 @@ die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu können, kann man sich einer stochastischen Methode bedienen, der sogenannten \emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster -zufällig erzeugt, und überprüft, ob sie sich in der Menge~$S$ enthalten sind. +zufällig erzeugt und überprüft, ob sie sich in der Menge~$S$ enthalten sind. Unter der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$ enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der @@ -970,10 +970,10 @@ unterschiedlichen Schnittmuster abschätzen. In Abbildung~\ref{fig:collisions-10000-1000000-32} ist das Ergebnis des Monte-Carlo-Algorithmus für 16-Schnittmuster zu sehen, die auf $\operatorname{OES}(32)$ und $\operatorname{BS}(32)$ angewandt wurden: Von -jedem Sortiernetzwerk wurden zunächst eine Menge von 10.000 +jedem Sortiernetzwerk wurden zunächst eine Menge~$S$ von 10.000 \emph{unterschiedlichen} Schnittmustern erzeugt. Anschließend wurden 1.000.000 zufällige Schnittmuster erzeugt und der Anteil der zufälligen Schnittmuster, -die identisch zu einem in der Menge enthalten Schnittmuster sind, berechnet. +die \emph{äquivalent} zu einem in~$S$ enthalten Schnittmuster sind, berechnet. Für $\operatorname{OES}(32)$ war dieser Anteil etwa $0,19 \%$, für $\operatorname{BS}(32)$ etwa $0,29 \%$. Das ergibt eine Abschätzung von $5,2 \cdot 10^6$ unterschiedlichen Schnittmustern für $\operatorname{OES}(32)$ und @@ -1003,11 +1003,11 @@ man keine Details mehr erkennen können. Aufgrund der hohen Anzahl unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit $\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedilchen Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385 -Schnittmuster gefunden, die ein Sortiernetzwerk aus dieser Menge erzeugen. -Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$ unterschiedlichen -Schnittmustern -- zwei Zehnerpotenzen mehr als bei den vorherigen -Sortiernetzwerken, aber immernoch fünf Zehnerpotenzen kleiner als die Anzahl -der \emph{möglichen} Schnittmuster. +Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent +sind. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$ +unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den +vorherigen Sortiernetzwerken, aber immernoch fünf Zehnerpotenzen kleiner als +die Anzahl der \emph{möglichen} Schnittmuster. \newpage \section{Der \textsc{SN-Evolution}-Algorithmus} @@ -1365,14 +1365,14 @@ $S_0$ mit sich selbst und anschließendem Eliminieren der Hälfte der Leitungen hervorgehen können, heißen \emph{Nachfolger} von $S_0$. Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem -gerichteten Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei +(gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer -Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $S_0$ -ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich +Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von +$S_0$ ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich selbst erzeugen kann. Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben ist die Anzahl -(unterschiedlichen) Schnittmuster und damit die Anzahl der Nachfolger sehr +(unterschiedlicher) Schnittmuster und damit die Anzahl der Nachfolger sehr groß. Wenn $S_0$ ein Sortiernetzwerk mit $n$~Leitungen ist, so hat $S_0$ bis zu \begin{displaymath} @@ -1380,11 +1380,11 @@ zu \end{displaymath} Nachfolger. -Der Algorithmus {\sc SN-Markov} legt auf diesem Graph einen zufälligen Weg -(englisch: \textit{random walk}) zurück. Er startet auf einem gegebenen -Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu gelangen -rekombiniert er das aktuelle Sortiernetzwerk mit sich selbst und erhält so -einen zufälligen Nachfolger. +Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen +zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem +gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu +gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich +selbst und erhält so einen zufälligen Nachfolger. \begin{itemize} \item $n \leftarrow \mathrm{Input}$ @@ -1445,6 +1445,11 @@ einen zufälligen Nachfolger. Das würde mir noch einfallen$\ldots$ \newpage +\section{Implementierung} + +So habe ich die ganzen Versuche durchgeführt. + +\newpage \bibliography{references} \bibliographystyle{plain} -- 2.11.0