Diverses.

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index a7f0bf9..b0fa6ac 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -979,7 +979,7 @@ auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
 ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
 ergeben sich insgesamt
 \begin{equation}\label{eqn:anzahl_schnittmuster}
 ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
 ergeben sich insgesamt
 \begin{equation}\label{eqn:anzahl_schnittmuster}

-  \prod_{i=n}^{1+n-k} 2i = 2^k \frac{n!}{(n-k)!}
+  \prod_{i=n}^{1+n-k} 2i = 2^k \cdot \frac{n!}{(n-k)!}

   \quad (n > m)
 \end{equation}
 \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
   \quad (n > m)
 \end{equation}
 \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle


@@ -1043,13 +1043,12 @@ 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
 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. 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.
+eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke \oes{16},
+\bs{16} und \ps{16} 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
 
 Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
 \emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen


@@ -1059,29 +1058,30 @@ Wert nach $1.000.000$~Iterationen allem Anschein nach dem Endwert schon sehr
 nahe ist.
 
 Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der
 nahe ist.
 
 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
-($\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 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
+Formel~\eqref{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 ($\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 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
 Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar.
 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.

-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.
+Die Hashtabelle würde mehr Arbeitsspeicher benötigen 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
 
 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
+zufällig erzeugt und überprüft, ob sie 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
 unterschiedlichen Schnittmuster abschätzen.
 
 unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der
 unterschiedlichen Schnittmuster abschätzen.
 


@@ -1104,8 +1104,8 @@ zufällige Schnittmuster erzeugt und der Anteil der zufälligen Schnittmuster,
 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
 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
-$3,4 \cdot 10^6$ für $\operatorname{BS}(32)$.
+\cdot 10^6$ unterschiedlichen 16-Schnittmustern für $\operatorname{OES}(32)$
+und $3,4 \cdot 10^6$ für $\operatorname{BS}(32)$.

 
 \begin{figure}
   \begin{center}
 
 \begin{figure}
   \begin{center}


@@ -1126,9 +1126,9 @@ $\operatorname{BS}(32)$. In Anbetracht der Tatsache, dass die Anzahl der
 unterschiedlichen 8-Schnittmuster für $\operatorname{PS}(16)$ in
 Abbildung~\ref{fig:count-cuts-16} bereits mehr als dreimal größer war als die
 Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$,
 unterschiedlichen 8-Schnittmuster für $\operatorname{PS}(16)$ in
 Abbildung~\ref{fig:count-cuts-16} bereits mehr als dreimal größer war als die
 Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$,

-ist dieser Umstand wenig verwunderlich. In einem kombinierten Graphen hätte
-man keine Details mehr erkennen können. Aufgrund der hohen Anzahl
-unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit
+ist dieser Umstand wenig verwunderlich. Entsprechend hätte man in einem
+kombinierten Graphen 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 zu einem Schnittmuster in der Menge äquivalent
 $\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedilchen
 Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
 Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent


@@ -1379,11 +1379,11 @@ von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
 Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
 gute Schnittmuster gesucht.
 
 Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
 gute Schnittmuster gesucht.
 

-Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster}
-als Individuen. Um zwei Individuen zu rekombinieren werden die ersten
-$r$~Schnitte des einen Schnittmusters verwendet und die letzten
-${c-r}$~Schnitte des zweiten Schmittmusters. $r$ ist eine Zufallsvariable mit
-$0 \leqq r \leqq c$.
+Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster},
+die in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als
+Individuen. Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte
+des einen Schnittmusters verwendet und die letzten ${c-r}$~Schnitte des
+zweiten Schmittmusters. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.

 
 Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
 auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
 
 Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
 auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die