Homepage von Boris Haase




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



Theoretische Informatik

Theoretische Informatik

Im Folgenden setzen wir die Mengenlehre voraus und beantworten für \(n \in {}^{c}\mathbb{N}\) die Fragen: Wie lassen sich \(n\) Werte in \(\mathcal{O}(1)\) sortieren? Wie können wir das Minimal- bzw. Maximalgerüst eines Graphen mit \(n\) Knoten in \(\mathcal{O}(\log \, n)\) berechnen? Lässt sich das Halteproblem lösen? Warum gilt \(P = NP\)?

Sei der Speicher teilweise in Form eines Baumes vom Grad \(k \in {}^{c}\mathbb{N}\) mit \(k^{\grave{m}}\) Speicherplätzen organisiert, wobei \(k^{\grave{m}} = 2^h\) mit \(h, m \in {}^{c}\mathbb{N}\) gelte. Jeder Speicherplatz sei in der Lage jeden zu sortierenden Wert komplett aufzunehmen. Kommen Werte mehrfach vor, hängen wir jedem Wert einen fortlaufenden Index an: 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. In den Blättern können wir 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, müssen wir die Werte nacheinander auslesen. 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, wenn 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}(\log \, n)\), da dies einer binären Suche entspricht. Sie ist antiproportional zur Anzahl der Baumknoten im Speicher. Verwenden wir \(d \in {}^{c}\mathbb{N}\) Datenleitungen, verringert sie sich 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 \(\log_{k}n\), weil dann jeder Zwischenknoten zu einem Wert gelesen werden muss. Wollen wir mit \(p \in {}^{c}\mathbb{N}\) die ersten \(k^p\) Speicherplätze anderweitig nutzen, so sind alle Zwischenknoten der \(p\)-ten Stufe zu durchsuchen. 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. Wir gehen davon aus, dass der Vergleich zweier Werte die Zeitkomplexität \(\mathcal{O}(1)\) benötigt, die Werte als Bitfolge vorliegen und sich alle Bits eines Wertes ebenfalls in \(\mathcal{O}(1)\) abarbeiten lassen. Wir setzen ferner voraus, 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 {}^{c}\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.

Wir beginnen 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, speichern wir ggf. die nicht im Baum liegende Adresse der restlichen Bitkette des Wertes im folgenden Knoten bzw. die Anzahl der Werte für diesen Knoten, wenn es auf die Reihenfolge gleicher Werte nicht ankommt.

Die Zeitkomplexität aller Verfahren, die Werte mit einer Bitlänge \(b = q a \in {}^{c}\mathbb{N}\) bei Adresslänge \(a \in {}^{c}\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 {}^{c}\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}((\log \, s + r) n)\).

Dabei werden die erwähnten Werte eines Buckets pro Bucket in einem AVL-Baum abgelegt oder in einem B-Baum, wenn wir sie in einem zum Hauptspeicher relativ langsamen externen Speicher ablegen. Dort arbeiten wir jeweils nur mit dem signifikanten Teilwert der Adresslänge eines Wertes. Verzichten wir auf vollständig sortierte Werte nach jedem Abarbeiten eines Wertes, reduziert sich 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 schreiben wir stets nur die Adressen in der aktuellen Sortierreihenfolge zurück, bevor wir die Werte mit gleichem soeben abgearbeitetem Teilwert weiter sortieren. Jeder Wert ist zusammenhängend im Speicher abzulegen, damit wir auf jeden Teilwert schnell zugreifen können.

Die Verwendung des \(\mathcal{O}(r n)\)-Verfahrens für die Stammdaten und des \(\mathcal{O}((\log \, 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 n \, \log n)\) angelegt wird und sich dann ein Wert durchschnittlich in \(\mathcal{O}(\log \, s + r)\) statt in \(\mathcal{O}(\log \, 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 eignet sich gut für parallele Programmierung. Es ist unter den angegebenen Voraussetzungen optimal sowie für den schnellen laufenden Aufbau von Tabellenindizes in eventuell relativ schnell wachsenden Datenbanken und die Suche. Suchbäume brauchen nicht ausgeglichen zu werden. Sind alle Werte nacheinander zu lesen und ist keiner davon zu groß, übertrifft seine Geschwindigkeit alle heute bekannten Sortierverfahren. Seine Hardwareimplementierung ist eher ungewöhnlich.

Sei \(n \in {}^{c}\mathbb{N}\) die Anzahl der durchnummerierten Knoten eines endlichen schlichten zusammenhängenden Graphen. (Ist er nicht schlicht, lassen wir durch Aussortieren in \(\mathcal{O}(n)\) nur die kleinste parallele Kante und keine Schlingen zu. Ist er nicht zusammenhängend, entfernen wir in \(\mathcal{O}(n)\) alle isolierten Knoten.) 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 können wir in \(\mathcal{O}(n \, \log \, n)\) oder gar in \(\mathcal{O}(\log \, 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. Fahren wir mit den weiß gefärbten Kanten in \(\mathcal{O}(\log \, n)\) Schritten fort, lässt sich der kleinste Wert eines Minimalgerüsts in \(\mathcal{O}(n)\) bzw. \(\mathcal{O}(1)\) bestimmen, bis das gesamte Minimalgerüst in \(\mathcal{O}(n \, \log \, n)\) bzw. \(\mathcal{O}(\log \, n)\) entstanden ist. Für ein Maximalgerüst subtrahieren wir alle Kantengewichte von einer hinreichend großen Konstanten.

Satz: Jede Turingmaschine mit wohldefinierter Berechnungsvorschrift hält irgendwann an.

Beweis: Wird ein (unendliches) Fortsetzen weder implizit noch explizit vorgeschrieben, muss jede Turingmaschine anhalten. Ein Selbstbezug, der dies gleichzeitig gebietet und verbietet, ist unsinnig.\(\square\)

Bemerkung: Das vergleichbare Barbierparadoxon macht den letzten Satz des Beweises verständlich (s. [968], S. 324). Somit wird das Halteproblem neu positiv beantwortet. Das \(P\)-\(NP\)-Problem löst der

Satz: Ist \(\mathcal{L}\) die Menge aller (Typ-0-) Sprachen \(L_k\) aus endlichen Wörtern mit Maximallänge \(c\) für unkonkretes \(|\mathcal{L}| = 2^{({c}^{\grave{c}}-1)/\acute{c}}\) (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\). Weil \(P\) alle Sprachen \(L_k\) enthält und \(NP\) nur solche, folgt die Behauptung.\(\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