BibTeX für Moritz Arbeit.

[diplomarbeit.git] / diplomarbeit.tex

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 1b9788f..c0213f2 100644 (file)
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -209,8 +209,17 @@ Die Eingabe kann mittels
 \end{displaymath}
 auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme vom
 Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das
 \end{displaymath}
 auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme vom
 Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das

-Verhalten jedes einzelnen Komparators nicht, so dass die Annahme auf einen
-Widerspruch geführt wird.
+Verhalten jedes einzelnen Komparators nicht: Wenn bei der Permutation eine
+Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen
+wurden, liegen jetzt entsprechend eine Null und eine Eins an, die genauso
+vertauscht werden oder nicht, wie das bei der Permutation der Fall war. Liegen
+zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als $a_i$
+oder zwei Zahlen größer oder gleich $a_i$. Da im Fall der 0-1-Folge zwei
+gleiche Zahlen am Komparator anliegen, dürfen wir davon ausgehen, dass sich
+der Komparator so verhält, wie er sich bei der Permutation verhalten hat --
+ohne das Ergebnis zu beeinflussen. Entsprechend kommen an den Ausgängen $i-1$
+und $i$ eine Null und eine Eins in der falschen Reihenfolge an. Das steht im
+Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden.

 
 Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
 Komplexitätsklasse
 
 Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
 Komplexitätsklasse


@@ -972,7 +981,7 @@ 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.
 
 und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks,
 führen beide Reihenfolgen zum selben Ergebnis.
 

-\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass es
+\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es

 möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
 vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster reduziert,
 die Menge der so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die
 möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
 vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster reduziert,
 die Menge der so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die