Korrekturen.
authorFlorian Forster <octo@verplant.org>
Thu, 24 Feb 2011 20:59:41 +0000 (21:59 +0100)
committerFlorian Forster <octo@verplant.org>
Thu, 24 Feb 2011 20:59:41 +0000 (21:59 +0100)
diplomarbeit.tex

index d23a996..6cd4078 100644 (file)
@@ -983,6 +983,10 @@ Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
 Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
 das \emph{Odd-Even-Transpositionsort}-Netzwerk.
 
+Im ersten Schritt wird eine Leitung ausgewählt und Maximum oder Minimum auf
+dieser Leitung angenommen. Dadurch ist der Weg durch das Sortiernetzwerk
+eindeutig festgelegt.
+
 \begin{figure}
   \centering
   \subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad
@@ -996,41 +1000,41 @@ das \emph{Odd-Even-Transpositionsort}-Netzwerk.
   \caption{Eine Leitung wird aus dem
   \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{8} entfernt: Auf der rot
   markierten Leitung wird $-\infty$ angelegt. Da der Wert bei jedem Komparator
-  am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die restlichen
-  Werte trotzdem noch richtig sortiert werden müssen, kann dieser Pfad
-  heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.}
+  nach unten weiter gegeben wird, ist der Pfad fest vorgegeben. Da die
+  restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
+  Pfad heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.}
   \label{fig:oe-transposition-cut}
 \end{figure}
 
-Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht
+Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht,
 beziehungsweise ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der
 Leitung geführt haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
 Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
 zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
 ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
 das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
-auf die keine Komparatoren mehr berührt
+die keine Komparatoren mehr berührt
 (Abbildung~\ref{fig:oe-transposition-cut1}).
 
 Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
-Komparatornetzwerk immer noch sortiert werden: Wir haben lediglich die
-Position des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss
-die Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum
-liegt. Wir haben nur angefangen, das Sortiernetzwerk unter diese Annahme
-auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage
+Komparatornetzwerk immer noch sortiert werden: Es wurde lediglich die
+\emph{Position}  des Minimums oder des Maximums in der Eingabe angenommen. Ein
+Sortiernetzwerk muss die Eingabe sortieren, unabhängig davon auf welcher
+Leitung das Minimum oder das Maximum liegt. Das Sortiernetzwerk unter diese
+Annahme auszuwerten -- über die verbleibenden Eingänge wurde keine Aussage
 getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
 mit $(n-1)$~Elementen darstellen.
 
-Wenn man die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in
+Wird die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in
 Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, bleibt das
 Sortiernetzwerk für $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung
-ein Minimum oder ein Maximum angenommen wird, bezeichnen wir das eliminieren
-einer Leitung auf diese Art und Weise als \emph{Minimum-Schnitt}
-beziehungsweise \emph{Maximum-Schnitt}.
+ein Minimum oder ein Maximum angenommen wird, wird das eliminieren einer
+Leitung auf diese Art und Weise als \emph{Minimum-Schnitt}, beziehungsweise
+\emph{Maximum-Schnitt} bezeichnet.
 
 Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
 Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
-markierten Komparatoren wurden verschoben, so dass sich eine kompaktere
+markierten Komparatoren sind verschoben, so dass sich eine kompaktere
 Darstellung ergibt. Außerdem ist das
 \emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der
 zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und
@@ -1048,10 +1052,9 @@ Der Eliminierungsschritt kann iterativ angewendet 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 auf diese Art und
 Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit
-$n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die
-nacheinander angewendet ein $n$-Sortiernetzwerk auf ein
-${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als
-\emph{$k$-Schnittmuster}.
+$n$~Eingängen reduziert werden. Als \emph{$k$-Schnittmuster} bezeichnet man
+die $k$~Minimum- und Maximum-Schnitte, die nacheinander angewendet ein
+$n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetz\-werk reduzieren.
 
 Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
 auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
@@ -1067,9 +1070,9 @@ ergeben sich insgesamt
   \quad (n > m)
 \end{displaymath}
 \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
-unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung
-und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks,
-führen beide Reihenfolgen zum selben Ergebnis.
+unterschiedlich. Wird beispielsweise das Minimum auf der untersten Leitung
+und das Maximum auf der obersten Leitung eines Standard-Sortiernetzwerks
+angenommen, führen beide möglichen Schnitt-Reihenfolgen zum selben Ergebnis.
 
 \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es
 möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
@@ -1095,8 +1098,8 @@ Möglichkeiten gibt. Ein Ausprobieren aller Möglichkeiten ist für große
 Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich.
 
 Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
-als die Anzahl der möglichen Schnittmuster. Für jeden Komparator auf der
-ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
+als die Anzahl der \emph{möglichen} Schnittmuster. Für jeden Komparator auf
+der ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
 Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
 unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
 der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die