X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=c0213f2c4b4596093891772c68de0885916bc83c;hb=c145acd32aa61c8e213cd1a15ccf79bf30563a5e;hp=1b9788f85c040ec22d35094376bbf96f19207578;hpb=47ffc866a95531de469b9a08e4a2accc5ecd7272;p=diplomarbeit.git

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 1b9788f..c0213f2 100644
--- 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
-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
@@ -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.
 
-\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