Kleine Korrekturen.

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 21ff5e0..dfa31d9 100644 (file)
--- 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$,
 
 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
 
 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
 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
 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
 ($\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
 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
 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
 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
 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,
 \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
 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
 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}
 
 \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
 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
 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
 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}
 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.
 
 \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}$
 
 \begin{itemize}
   \item $n \leftarrow \mathrm{Input}$


@@ -1445,6 +1445,11 @@ einen zufälligen Nachfolger.
 Das würde mir noch einfallen$\ldots$
 
 \newpage
 Das würde mir noch einfallen$\ldots$
 
 \newpage

+\section{Implementierung}
+
+So habe ich die ganzen Versuche durchgeführt.
+
+\newpage

 \bibliography{references}
 \bibliographystyle{plain}
 
 \bibliography{references}
 \bibliographystyle{plain}