Homepage von Boris Haase




Funkrechnen • Internet und Co • Programmieren mit Stair • Theoretische Informatik  (Vorherige | Nächste)



Theoretische Informatik

Theoretische Informatik

Das Folgende setzt die Mengenlehre voraus und beantwortet für \(n \in {}^{\nu}\mathbb{N}\) die Fragen: Wie lassen sich \(n\) Werte in \(\mathcal{O}(1)\) sortieren? Wie lässt sich das Minimal- bzw. Maximalgerüst eines Graphen mit \(n\) Knoten in \(\mathcal{O}({_e}n)\) berechnen? Was ist die Antwort auf das Halteproblem? Warum gilt \(P = NP\)?

Sei der Speicher teilweise in Form eines Baumes vom Grad \(k \in {}^{\nu}\mathbb{N}\) mit \(k^{\grave{m}}\) Speicherplätzen organisiert, wobei \(k^{\grave{m}} = 2^h\) mit \(h, m \in {}^{\nu}\mathbb{N}\) gelte. Jeder Speicherplatz sei in der Lage jeden zu sortierenden Wert komplett aufzunehmen. Kommen Werte mehrfach vor, wird jedem Wert ein fortlaufender Index angehängt: Dieser bildet mit dem alten Wert zusammen den neuen Wert. Jeder Wert sei im Stellenwertsystem zur Basis \(k\) kodiert und es seien o. B. d. A. maximal \(k^m\) Werte zu sortieren.

Von der Baumwurzel gehen \(k^m\) Datenleitungen ab, von den beiden Nachfolgern je \(k^{\acute{m}}\), von deren Nachfolgern je \(k^{m-2}\) usf. Jeder \(j\)-te Zwischenknoten korrespondiert hierarchisch mit der \(j\)-ten Stelle zur Basis \(k\) des zu sortierenden Wertes. Die Blätter können statt der Werte deren Adressen speichern. Dann lassen sich in einem Schritt alle Werte in den Blättern speichern und in einem weiteren sortiert in die Wurzel zurückholen. Es reicht aus die Werte so weit in den Baum zu schieben, bis sie sich trennen.

Gilt eine Beschränkung von einer Datenleitung pro Speicherplatz, sind die Werte nacheinander auszulesen. Das Anfügen von einem Index bei mehrfachen Werten kann nun entfallen, da mehrfache Werte in einer separaten Liste verwaltet werden können. Geht ein Wert durch einen Zwischenknoten, setzt dieser sein Bit auf 1, aber auf 0, falls der Zwischenknoten keinen auszulesenden Nachfolger hat.

Die Sortierreihenfolge bestimmt den ersten Wert. Speichern, Nachfolger prüfen, Bits maskieren und auslesen dauert \(\mathcal{O}(n)\). Die Komplexität erhöht sich durch Einsortieren eines zusätzlichen Wertes um \(\mathcal{O}({_e}n)\), da dies einer binären Suche entspricht. Sie ist antiproportional zur Anzahl der Baumknoten im Speicher. Das Verwenden von \(d \in {}^{\nu}\mathbb{N}\) Datenleitungen verringert sie um den Faktor \(\hat{d}\). Belegen die Werte das \(g\)-fache eines Speicherplatzes, erhöht sie sich um den Faktor \(g\).

Enthält der Speicher keinen Baum vom Grad \(k\), erhöht sie sich um den Faktor \({_k}n \), weil dann jeder Zwischenknoten zu einem Wert gelesen werden muss. Ein anderweitiges Nutzen der ersten \(k^p\) Speicherplätze mit \(p \in {}^{\nu}\mathbb{N}\) erfordert ein Durchsuchen aller Zwischenknoten der \(p\)-ten Stufe. Die Komplexität erhöht sich bei gut gefülltem Speicher marginal, andernfalls um den Worst-Case-Faktor \(\mathcal{O}(k^p)\).

Nun wird der optimale Sortieralgorithmus Bitsort vorgestellt. Er sortiert stabil mit der Zeitkomplexität \(\mathcal{O}(n)\) und benötigt \(\mathcal{O}(n)\) zusätzlichen Speicherplatz. Voraussetzungen: Der Vergleich zweier Werte benötigt die Zeitkomplexität \(\mathcal{O}(1)\), die Werte liegen als Bitfolge vor und alle Bits eines Wertes lassen sich ebenfalls in \(\mathcal{O}(1)\) abarbeiten. Ferner gelte, dass der Speicher teilweise als Binärbaum realisiert ist und der Weg von Wurzel bis Blatt ebenfalls in \(\mathcal{O}(1)\) durchlaufen werden kann.

Ist \(p \in {}^{\nu}\mathbb{N}\) die Anzahl der parallelen Schritte für paralleles Bitsort, so ist die Zeitkomplexität \(\mathcal{O}(\hat{p} n)\). Jedes Einfügen in den stets sortierten Baum bzw. Ausgeben eines Wertes hat die Zeitkomplexität \(\mathcal{O}(1)\). Der Speicher sei mit folgender Intelligenz versehen: Jeder Baumknoten speichert den ihn erreichenden Wert selbständig und kann ihn an den nächsten Baumknoten weitergeben, wenn er schon besucht wurde, bzw. andernfalls seine Adresse an die Zentraleinheit zurückgeben. Der Wurzel entspricht kein Bitwert.

Begonnen wird bei dem höchstwertigen Bit eines Wertes. Jedes seiner nacheinander abgearbeiteten Bits bestimmt den nächsten Knoten innerhalb des Binärbaumes. Wurden alle Bits abgearbeitet oder ergibt sich ein Unterschied zum verglichenen Bit und wurde der zugehörige Knoten noch nicht besucht, speichert der folgende Knoten ggf. die nicht im Baum liegende Adresse der restlichen Bitkette des Wertes bzw. die Anzahl der Werte für diesen Knoten bei unerheblicher Reihenfolge gleicher Werte.

Die Zeitkomplexität aller Verfahren, die Werte mit einer Bitlänge \(b = q a \in {}^{\nu}\mathbb{N}\) bei Adresslänge \(a \in {}^{\nu}\mathbb{N}\) sortieren, erhöht sich pro Wert von \(\mathcal{O}(1)\) auf \(\mathcal{O}(q)\). Ist \(r\) der Durchschnittswert von \(q\), ist in der Zeitkomplexität des Sortierverfahrens mindestens ein \(\mathcal{O}(n)\) durch \(\mathcal{O}(r n)\) zu ersetzen. Ist \(s \in {}^{\nu}\mathbb{N}\) die durchschnittliche Anzahl der verschiedenen (!) Werte, die in einem Bucket nach Sortierung bis Bitlänge \(a\) landen und deren Bitlänge größer als \(a\) ist, so beträgt die Zeitkomplexität des Verfahrens \(\mathcal{O}(({_e}s + r) n)\).

Dabei werden die erwähnten Werte eines Buckets pro Bucket in einem AVL-Baum abgelegt oder in einem B-Baum bei Ablage in einem zum Hauptspeicher relativ langsamen externen Speicher. Dort wird jeweils nur mit dem signifikanten Teilwert der Adresslänge eines Wertes gearbeitet. Der Verzicht auf vollständig sortierte Werte nach jedem Abarbeiten eines Wertes reduziert die komplette Sortierung durch Verwendung von zwei Hauptspeicherbereichen zeitlich auf \(\mathcal{O}(r n)\).

Der zweite Hauptspeicherbereich wird nach jedem Durchlauf gelöscht, um für den nächsten Durchlauf zur Verfügung zu stehen, bis ein Bucket abgearbeitet ist. In den ersten Hauptspeicherbereich werden stets nur die Adressen in der aktuellen Sortierreihenfolge zurückgeschrieben, bevor die Werte mit gleichem soeben abgearbeitetem Teilwert weiter sortiert werden. Für den schnellen Zugriff auf jeden Teilwert ist jeder Wert zusammenhängend im Speicher abzulegen.

Die Verwendung des \(\mathcal{O}(r n)\)-Verfahrens für die Stammdaten und des \(\mathcal{O}(({_e}s + r) n)\)-Verfahrens für die Bewegungsdaten kombiniert beide gut. Damit lassen sich insbesondere schnell Tabellenindizes anlegen. Bei umfangreichen Tabellen macht es einen deutlichen Unterschied, ob ein Index in \(\mathcal{O}(r n)\) statt in \(\mathcal{O}(r {_e}n n)\) angelegt wird und sich dann ein Wert durchschnittlich in \(\mathcal{O}({_e}s + r)\) statt in \(\mathcal{O}({_e}n + r)\) oder schlechter suchen lässt. Sortieren durch Mischen sortierter Listen ist ebenfalls in \(\mathcal{O}(r n)\) möglich.

Diskussion von Bitsort: Es ist unter den angegebenen Voraussetzungen optimal sowie für die parallele Programmierung, den schnellen laufenden Aufbau von Tabellenindizes in Datenbanken und die Suche darin gut geeignet. Seine Hardwareimplementierung ist eher ungewöhnlich.

Sei \(n \in {}^{\nu}\mathbb{N}\) die Anzahl der Knoten eines endlichen schlichten zusammenhängenden Graphen. (Ist er nicht schlicht, lässt ein Aussortieren in \(\mathcal{O}(n)\) nur die kleinste parallele Kante und keine Schlingen zu. Ist er nicht zusammenhängend, werden in \(\mathcal{O}(n)\) alle isolierten Knoten entfernt.) Bei Ausschluss negativer Gewichte benötigt der Algorithmus von Dijkstra \(\mathcal{O}(n)\) Schritte für jeden minimalen Weg in dem Graphen, da Sortieren sowie paralleles Addieren und Vergleichen in \(\mathcal{O}(1)\) möglich ist.

Dessen Minimal- oder Maximalgerüst lässt sich in \(\mathcal{O}({_e}n n)\) oder gar in \(\mathcal{O}({_e}n)\) berechnen: Die Kanten eines Knotens lassen sich parallel in \(\mathcal{O}(n)\) bzw. \(\mathcal{O}(1)\) sortieren. Seien alle Kanten zu Beginn weiß gefärbt. Jeder Knoten hängt die kleinere und dann die größere Zahl der beteiligten Knoten der Kante mit dem kleinsten Gewicht aller weiß gefärbten Kanten, die von ihm ausgehen, an dieses Bit für Bit als Wert an. Er speichert den kleinsten Wert, der ihn erreicht. Dies ist in \(\mathcal{O}(n)\) bzw. \(\mathcal{O}(1)\) möglich.

Das Schwarzfärben der Kanten zwischen jeweils zwei Knoten desselben Minimalgerüsts benötigt maximal die gleiche Zeit. Jeder Knoten hat dann einen nächsten Nachbarknoten. Ein Fortfahren mit den weiß gefärbten Kanten in \(\mathcal{O}({_e}n)\) kann den kleinsten Wert eines Minimalgerüsts in \(\mathcal{O}(n)\) bzw. \(\mathcal{O}(1)\) bestimmen, bis das gesamte Minimalgerüst in \(\mathcal{O}({_e}n n)\) bzw. \(\mathcal{O}({_e}n)\) entstanden ist. Für ein Maximalgerüst werden alle Kantengewichte von einer hinreichend großen Konstanten subtrahiert.

Haltesatz: Um ein festes \(r_m\) der Zahl \(0,r_{1}r_{2}...r_{m}\) zu erreichen, hält ein Programm für beliebige (Pseudo-) Zufallszahlen \(r_j \in {}^{\nu}\mathbb{N}\) mit \(k \in {}^{\nu}\mathbb{N}^{*}\) Stellen und Basis \(p := 2^k\) in \(m \in \mathbb{N}^{*}\) Schritten mit der Wahrscheinlichkeit \(\hat{p}\).

Beweis: Dies ist ein optimales Ergebnis der Wahrscheinlichkeitsrechnung (vgl. [973], S. 10 - 40).\(\square\)

Bemerkung: Zufall ist unentscheidbar. Damit existieren Programme, die mit beliebiger Wahrscheinlichkeit halten, und es folgen die Gödelschen Unvollständigkeitssätze. Der Gödelsatz "Ich bin nicht beweisbar." ist insofern sophistisch, als er das Scheinargument Petitio Principii ex negativo aufweist. Um das Halteproblem zu lösen, ist ein Selbstbezug unsinnig, der ein Halten gleichzeitig gebietet und verbietet. Die Selbstreferenz macht das Diagonalargument für das Halteproblem unzulässig.

Satz: Ist \(\mathcal{L}\) die Menge aller (Typ-0-) Sprachen \(L_k\) aus endlichen Wörtern mit Maximallänge \(\nu\) für mittendliches \(|\mathcal{L}| = 2^{({\nu}^{\grave{\nu}}-1)/\acute{\nu}}\) (unter Anwendung der geometrischen Reihe) und \(k \in \{1, …, |\mathcal{L}|\}\), gilt \(P = NP = \mathcal{L}\).

Beweis: Da sich jede deterministische Turingmaschine auch als nichtdeterministisch auffassen lässt (vgl. [972], S. 162, 318 und 361 f.), gilt \(P \subseteq NP\). Es enthält \(P\) alle linearen Sprachen \(L_k\) und \(NP\) nur solche.\(\square\)

© 2006-2019 by Boris Haase


Valid XHTML 1.0 • Datenschutz • Haftungsausschluss • PDF-Version • Literatur • Schlagwörter • Definitionen • Statistik • PHP-Code • RSS-Feed • MWiki • Seitenbeginn