Schnittmuster: Kleine Verbesserungen.

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 25d6329..efdb438 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -946,17 +946,26 @@ sich die Resultate auch in der ersten Schicht nicht unterscheiden.
   \label{fig:count-cuts-16}
 \end{figure}
 
   \label{fig:count-cuts-16}
 \end{figure}
 

-Um die Anzahl der \emph{unterschiedlichen} Schnittmuster abschätzen zu können,
-wurden je eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke
+Alleine durch Betrachten der ersten Schicht von Komparatoren konnte die Anzahl
+der \emph{unterschiedlichen} Schnittmuster auf höchstens $\frac{2}{3}$ der
+\emph{möglichen} Schnittmuster reduziert werden. Um die Anzahl der
+\emph{unterschiedlichen} Schnittmuster experimentell zu ermitteln, wurden je
+eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke

 $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$
 $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$

-angewandt. Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
+angewandt. Anschließend wurde mithilfe einer Hashtabelle überprüft, ob das
+resultierende Sortiernetzwerk schon von einem \emph{äquivalenten}
+Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk noch nicht in der
+Hashtabelle enthalten war, wurde der Zähler für unterschiedliche Schnittmuster
+erhöht und das Sortiernetzwerk eingefügt.
+
+Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der

 \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
 nahe ist.
 
 \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
 nahe ist.
 

-Die Anzahl der 8-Schnittmuster ist entsprechend der
+Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der

 Formel~\ref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen Schnittmuster
 führen aber nur zu wenigen \emph{unterschiedlichen} Sortiernetzwerken: 3519
 ($\approx 0,1\%$) im Fall des \emph{Odd-Even-Mergesort-Netzwerks}, 4973
 Formel~\ref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen Schnittmuster
 führen aber nur zu wenigen \emph{unterschiedlichen} Sortiernetzwerken: 3519
 ($\approx 0,1\%$) im Fall des \emph{Odd-Even-Mergesort-Netzwerks}, 4973


@@ -968,14 +977,18 @@ 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

-Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar. Um
-die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu können,
-kann man sich einer stochastischen Methode bedienen, der sogenannten
+Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar.
+Die Hashtabelle benötigt mehr Arbeitsspeicher als in derzeitigen Rechnern
+vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für
+„kleine“ x-Werte verlässt.
+
+Um 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.
 \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.

-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
+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
 unterschiedlichen Schnittmuster abschätzen.
 
 unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der
 unterschiedlichen Schnittmuster abschätzen.