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

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 1b9788f..336208a 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