From 47ffc866a95531de469b9a08e4a2accc5ecd7272 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Fri, 18 Feb 2011 12:09:35 +0100 Subject: [PATCH] =?utf8?q?Ich=20soll=20ausdr=C3=BCcklich=20sagen,=20wenn?= =?utf8?q?=20ich=20etwas=20selbst=20gefunden=20habe.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- diplomarbeit.tex | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 316954c..1b9788f 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -175,12 +175,12 @@ Definition handelt es sich bei dem \emph{Komparatornetzwerk} folglich gegebenes Komparatornetzwerk zu finden ist nach heutigem Kenntnisstand jedoch nicht \emph{effizient} möglich. -Beispielsweise sortiert das Komparatornetzwerk in -Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880 möglichen -Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4, 8, 6)$ -lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die -Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge -$(1, 0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt. +Beispielsweise sortiert das im Rahmen dieser Arbeit entdeckte +Komparatornetzwerk in Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880 +möglichen Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4, +8, 6)$ lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die +Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge $(1, +0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt. Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese -- 2.11.0