From: Florian Forster <octo@leeloo.octo.it>
Date: Thu, 27 Jan 2011 15:27:05 +0000 (+0100)
Subject: Schnittmuster: Kleine Verbesserungen.
X-Git-Url: https://git.octo.it/?p=diplomarbeit.git;a=commitdiff_plain;h=9303184e1ed24de5977b4f86c03d1d26c3345aa1

Schnittmuster: Kleine Verbesserungen.
---

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 25d6329..efdb438 100644
--- 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}
 
-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)$
-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.
 
-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
@@ -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
-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.
-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.