Weitere ToDos abgearbeitet.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index e9203fb..a58d629 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -280,13 +280,13 @@ Sortiereigenschaft besitzt, sind mit dieser Methode nur 65.536 Tests notwendig
 -- eine Zahl, die für aktuelle Prozessoren keine Herausforderung darstellt.
 Für die Überprüfung eines Komparatornetzwerks mit 32~Leitungen sind jedoch
 bereits etwa 4,3~Milliarden Tests notwendig, die einen Rechner durchaus
-mehrere Minuten beschäftigen. Das ist deshalb problematisch, weil die im
+mehrere Stunden beschäftigen. Das ist deshalb problematisch, weil die im
 Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende
 Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines
-Zwischenergebnisses fünf Minuten in Anspruch nimmt, sind für eine Million
-Iterationen fast zehn Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
-auf 1000~Computern mit je 4~Prozessoren verteilt wird, werden über 20~Stunden
-für einen Lauf benötigt.
+Zwischenergebnisses drei Stunden in Anspruch nimmt, sind für eine Million
+Iterationen etwa 340~Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
+auf 1000~Computern mit je 4~Prozessoren verteilt wird, wird etwa ein Monat für
+einen Lauf benötigt.
 
 \subsubsection{Evolutionäre Algorithmen}
 
@@ -846,23 +846,14 @@ Batcher} zeigt in~\cite{B1968}, dass in diesem Fall
 \end{displaymath}
 gilt.
 
-% gnuplot:
-% oem(n,m) = ((n*m) <= 1) ? (n*m) : oem(ceil(.5*n), ceil(.5*m)) + oem(floor(.5*n), floor(.5*m)) + floor(.5*(n+m-1.0))
-% oem1(n) = oem(ceil(.5*n),floor(.5*n))
-% oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)
-
-%\begin{itemize}
-%\item Pairwise sorting-network
-%\end{itemize}
-
-\subsection{Das Pairwise-Sorting-Netzwerk}
-
-Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
-für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
-Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
-Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
-\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
-das \emph{Odd-Even-Mergesort}-Netzwerk.
+%\subsection{Das Pairwise-Sorting-Netzwerk}
+%
+%Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
+%für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
+%Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
+%Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
+%\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
+%das \emph{Odd-Even-Mergesort}-Netzwerk.
 
 \newpage
 \section{Transformation von Sortiernetzwerken}
@@ -1264,8 +1255,12 @@ die bei Sortiernetzwerken verfolgt werden können:
 
 \begin{figure}
   \centering
-  \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
-  \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
+  \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das
+  Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in~\cite{G1972}
+  veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
+  \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das
+  Netzwerk wurde von \textit{D. Van~Voorhis} 1974 in~\cite{V1974}
+  veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
   \caption{Das effizienteste und das schnellste Sortiernetzwerk für
   16~Leitungen, das derzeit bekannt ist.}
   \label{fig:16-best-known}
@@ -1333,7 +1328,7 @@ Bewertungsfunktion verwendet. Die Werte
   w_{\mathrm{Schichten}}    &=& 1
 \end{eqnarray*}
 geben dem Einsparen eines Komparators ein höheres Gewicht als dem Einsparen
-einer Schicht. \todo{Fehler hier noch was?}
+einer Schicht.
 
 \subsection{Selektion}