Mir wird ein Vergleichsnetzwerk vorgestellt. Wie kann ich feststellen, ob das Vergleichsnetzwerk ein Sortiernetzwerk ist? In der Abbildung unten sehen Sie ein Beispiel für ein Netzwerk zum Sortieren von Auswahlsortierungen und Einfügungen. Ziel ist es, ein Vergleichsnetzwerk zu haben und numerische Werte zu sortieren. Wenn ich in diesem Fall 2 ^ n Werte teste 2 ^ 8. Dies ist eine Menge Arbeit | nicht effizienter Weg, um es zu testen. Ich suche nach einem mathematischen Modell / Beweis, um zu überprüfen, ob dies ein gültiges Sortiernetzwerk ist.

Im Allgemeinen ist die Überprüfung, ob ein bestimmtes Vergleichsnetzwerk tatsächlich ein korrektes Sortiernetzwerk ist, ein vollständiges Co-NP-Problem. Wenn Sie dies durch Testen überprüfen möchten, müssen Sie exponentiell viele Tests versuchen.

Insbesondere gibt es Sortiernetzwerke, die alle bis auf einen Wert korrekt sortieren. Sie können also nicht hoffen, zu testen, ob das Netzwerk korrekt ist oder nicht, indem Sie ihm einfach einige Eingaben zuführen.

Eine Standardmethode besteht darin, zu testen, ob alle Eingaben, die nur aus Nullen und Einsen bestehen, korrekt sortiert werden. Wenn dies der Fall ist, werden alle Eingaben sortiert (auch diejenigen, die nicht auf Nullen und Einsen beschränkt sind). Dies erfordert jedoch exponentiell viele Tests. Darüber hinaus kann die Anzahl der Tests nicht wesentlich reduziert werden: Für Null-Eins-Eingaben kann nachgewiesen werden, dass mindestens Tests erforderlich sind, bis das Sortiernetzwerk korrekt ist.2 n - n - $2^n$$2^n-n-1$

Alternativ kann man Tests verwenden, bei denen die Eingaben Permutationen von . Dies reduziert die Anzahl der benötigten Tests etwas, aber Sie benötigen immer noch exponentiell viele Tests. Insbesondere sind Tests notwendig und ausreichend.C ( n , ⌊ n / 2 ⌋ ) - $1,2,\dots,n$$C(n, \lfloor n/2 \rfloor)-1$

Beweise für diese Tatsachen finden Sie in den folgenden Abhandlungen:

Zur rechnerischen Komplexität der Überprüfung des optimalen Sortiernetzwerks . Ian Parberry. Parle'91 Parallele Architekturen und Sprachen Europa, 1991.

Grenzen der Größe von Testsätzen zum Sortieren und zugehörigen Netzwerken . Moon Jung Chung und B. Ravikumar. Discrete Mathematics, Bd. 81, S. 1–9, April 1990.

Zitieren Sie Ihre Frage:

Ich suche nach einem mathematischen Modell / Beweis, um zu überprüfen, ob dies ein gültiges Sortiernetzwerk ist.

Während sich die (ausgezeichnete) Antwort von DW mit dem allgemeinen Fall befasst, werde ich Ihr spezifisches Beispiel betrachten. Ein Netzwerk dieser Form mit Eingängen kann durch Induktion als Sortiernetzwerk dargestellt werden: (Abbildung siehe Abbildung)$n$

1. $n=1$ Eingang wird immer sortiert;
2. Angenommen, ein Netzwerk der Größe dieser Form ist ein Sortiernetzwerk, und betrachten Sie ein Netzwerk der Größe . $n-1$$n$
   1. Die "Diagonale" ganz links bringt das größte Element immer korrekt an die Position (in Ihrem Fall ).b $n$$b_8$
   2. Sie haben ein kleineres, ähnliches Netzwerk mit den verbleibenden Elementen.$n-1$
   3. Dieses kleinere Netzwerk sortiert alle verbleibenden Elemente nach der induktiven Hypothese.

Wenn Sie sich ein allgemeines Sortiernetzwerk ansehen, wissen Sie möglicherweise nicht, wie Sie nachweisen können, dass es jede Folge von Werten (mit der richtigen Länge für das Sortiernetzwerk) korrekt sortiert. Aber ich habe diesen schönen Trick gelernt, wie man die Aufgabe vereinfacht:

Das 0-1-Prinzip

Wenn ein Sortiernetzwerk jede Sequenz (mit der richtigen Länge), die nur aus "0" und "1" besteht, korrekt sortiert, sortiert es jede Sequenz (mit der richtigen Länge) korrekt. Natürlich sind "0" und "1" Platzhalter für bestimmte Elemente in der Domäne des Sortiernetzwerks.

Sie können also einen Beweis wie folgt erstellen:

1. Nehmen Sie zwei verschiedene Elemente aus der Domäne des Sortiernetzwerks und nennen Sie sie "0" und "1", so dass "0" <"1" ist.
2. Konstruieren Sie alle Binärzeichenfolgen mit der genauen Länge des Sortiernetzwerks
3. In diesen Zeichenfolgen ersetzen Sie das 0-Bit und das 1-Bit durch "0" und "1".
4. Wenden Sie diese Zeichenfolgen auf das Sortiernetzwerk an
5. Jede Zeichenfolge muss nach 000..01 ... 1 sortiert sein

$2^n$

$n$$2^n$$n$

Können wir es billiger machen?

Leider können wir wahrscheinlich nicht viel billiger sein als ausführliche Tests, zumindest nicht, wenn wir eine Turing-Maschine verwenden, um die Proofs zu konstruieren. Wenn Sie sich ein bestimmtes Sortiernetzwerk ansehen, haben Sie möglicherweise eine kreative Idee, wie Sie einen einfachen Beweis erstellen können. Im Allgemeinen ist ein Algorithmus zum Erstellen solcher Beweise jedoch sehr wahrscheinlich so komplex wie das Testen aller binären Zeichenfolgen. Der Grund dafür ist, dass das Proofing-Sortiernetzwerk mit der NP-Gesamtkomplexitätsklasse zusammenhängt, wie in den anderen Antworten beschrieben.

$2^{\sqrt n}$

Ausblick / Ausblick

Ist dein Gehirn eine Turingmaschine?

Eine philosophische Konsequenz ist: Wenn Sie glauben, dass Sie einen kreativen Beweis für die Richtigkeit jedes Sortiernetzwerks finden können, dann glauben Sie auch, dass Ihr Gehirn sehr wahrscheinlich keine Turing-Maschine ist.

Parallele Sortierung

Das "0-1-Prinzip" wird auch verwendet, um die Richtigkeit paralleler Sortieralgorithmen zu beweisen. Ich habe eine (hoffentlich) schöne Präsentation darüber auf Github .

Sortiernetzwerk korrigieren

Wenn eine der Zeichenfolgen falsch sortiert ist (Sie haben also bewiesen, dass das Sortiernetzwerk falsch ist), können Sie damit ein Sortiernetzwerk ohne diesen Fehler erstellen. Fügen Sie einfach einen zusätzlichen Vergleich zur Position des "1-0-Randes" in der falschen Ergebniszeichenfolge hinzu.