Seminar Wortbasierte Algorithmen, WS 98/99

Vortragsthemen

A. Einführung und geordnete Wörterbücher ohne Multiplikation

In diesem Vortrag soll zuerst die Wort-RAM eingeführt und diskutiert werden. Insbesondere sollen dabei das eingeschränkte Modell, das Multiplikationsmodell und das AC°-Modell besprochen werden. Danach soll ein geordnetes Wörterbuch von Andersson [2] beschrieben und erklärt werden, das im eingeschränkten Modell funktioniert, aber sehr viel Speicherplatz benötigt.

Literatur

  1. T. Hagerup, Sorting and searching on the word RAM, in Proc. 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998), Lecture Notes in Computer Science, Springer-Verlag, Berlin, Vol. 1373, pp. 366-398 [Sect. 1-4].

  2. A. Andersson, Sublogarithmic searching without multiplications, in Proc. 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1995), pp. 655-663.

B. Sortieren

Es sollen ein deterministischer und ein randomisierter Sortieralgorithmus von Andersson et al. [1] vorgestellt werden. Der deterministische Algorithmus sortiert n Schlüssel in O(n log log n) Zeit unter Benutzung von viel Speicherplatz. Der randomisierte Algorithmus sortiert unter gewissen Bedingungen in linearer erwarteter Zeit und linearem Platz.

Literatur

  1. A. Andersson, T. Hagerup, S. Nilsson, and R. Raman, Sorting in linear time?, J. Comput. System Sci., to appear [Sect. 1-3]. A preliminary version appeared in Proc. 27th Annual ACM Symposium on the Theory of Computing (STOC 1995), pp. 427-436.

  2. T. Hagerup, Sorting and searching on the word RAM, in Proc. 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998), Lecture Notes in Computer Science, Springer-Verlag, Berlin, Vol. 1373, pp. 366-398 [Sect. 5].

C. Kleine Wörterbücher

Es soll zuerst beschrieben werden, wie eine geringe Anzahl von Schlüsseln im AC°-Modell so verwaltet werden kann, daß jede Wörterbuch-Operation in konstanter Zeit ausgeführt werden kann. Die Ergebnisse sollen dann, soweit möglich, auf das Multiplikations-Modell übertragen werden, das mit üblichen Instruktionen auskommen muß. Die Ergebnisse sind statische und dynamische Konstantzeit-Wörterbücher für wenig Schlüssel. Dieses Thema kann wahlweise von zwei Personen bearbeitet werden.

Literatur

  1. T. Hagerup, Sorting and searching on the word RAM, in Proc. 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998), Lecture Notes in Computer Science, Springer-Verlag, Berlin, Vol. 1373, pp. 366-398 [Sect. 6.1 and 6.2].

  2. M. L. Fredman and D. E. Willard, Surpassing the information theoretic bound with fusion trees, J. Comput. System Sci. 47 (1993), pp. 424-436.

  3. M. L. Fredman and D. E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, J. Comput. System Sci. 48 (1994), pp. 533-551.

D. Exponentielle Suchbäume

Die exponentiellen Suchbäume von Andersson [1] sollen beschrieben und erklärt und mit den im letzten Vortrag vorgestellten statischen Wörterbüchern kombiniert werden. Die sich daraus ergebende Datenstruktur soll mit der Datenstruktur aus Vortrag A verglichen werden.

Literatur

  1. A. Andersson, Faster deterministic sorting and searching in linear space, in Proc. 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1996), pp. 135-141.

  2. T. Hagerup, Sorting and searching on the word RAM, in Proc. 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998), Lecture Notes in Computer Science, Springer-Verlag, Berlin, Vol. 1373, pp. 366-398 [Sect. 6.3].

E. Prioritätswarteschlangen

Eine Prioritätswarteschlange von Thorup [1] soll beschrieben und erklärt werden. Außerdem soll gezeigt werden, wie Sortieren und die Verwaltung von sogenannten monotonen Prioritätswarteschlangen in gewisser Weise äquivalente Probleme sind. Danach sollen Algorithmen für die Berechnung kürzester Wege in gerichteten Netzwerken vorgestellt werden. Diese Algorithmen basieren alle auf dem Algorithmus von Dijkstra, so daß es real darum geht, Prioritätswarteschlangen gewisser Art so effizient wie möglich zu realisieren. Dieses Thema kann wahlweise von zwei Personen bearbeitet werden.

Literatur

  1. M. Thorup, On RAM priority queues, in Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1996), pp. 59-67.

  2. R. Raman, Recent results on the single-source shortest paths problem, SIGACT News 28:2 (1997), pp. 81-87.

  3. R. Raman, Priority queues: Small, monotone and trans-dichotomous, in Proc. 4th Annual European Symposium on Algorithms (ESA 1996), Lecture Notes in Computer Science, Vol. 1136, Springer-Verlag, Berlin, pp. 121-137.

F. Berechnung kürzester Wege in ungerichteten Netzwerken

Es soll ein aufsehenerregendes Ergebnis von Thorup [1] vorgestellt werden, das besagt, daß kürzeste Wege von einem ausgezeichneten Startknoten zu allen anderen Knoten in einem ungerichteten Netzwerk mit nichtnegativen Kantenkosten in Linearzeit berechnet werden können.

Literatur

  1. M. Thorup, Undirected single source shortest paths in linear time, in Proc. 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1997), pp. 12-21.

  2. T. Hagerup, A description of Thorup's single-source-shortest-path algorithm, unpublished.

G. Wörterbücher im AC°-Modell: Obere Schranken

Es soll die beste bekannte Konstruktion eines statischen ungeordneten Wörterbuchs im AC°-Modell [1] beschrieben und erläutert werden. Wahlweise kann auf Erweiterungen für dynamische und/oder geordnete Wörterbücher eingegangen werden.

Literatur

  1. T. Hagerup, Simpler and faster dictionaries on the AC° PRAM, in Proc. 25th International Colloquium on Automata, Languages and Programming (ICALP 1998), Lecture Notes in Computer Science, Vol. 1443, Springer-Verlag, Berlin, pp. 79-90.

  2. A. Andersson, P. B. Miltersen, S. Riis, and M. Thorup, Static dictionaries on AC° RAMs: Query time Theta(sqrt(log n/log log n)) is necessary and sufficient, Tech. Rep. No. RS-97-14, BRICS, Dept. of Computer Science, Univ. of Aarhus, 1997 [Sect. 1-4]. A preliminary version appeared in Proc. 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1996), pp. 441-450.

H. Wörterbücher im AC°-Modell: Untere Schranken

Es soll gezeigt werden, daß das Wörterbuch aus dem vorigen Vortrag für bestimmte Zusammenhänge zwischen Schlüsselanzahl, Wortlänge und zur Verfügung stehendem Platz optimal ist.

Literatur

  1. A. Andersson, P. B. Miltersen, S. Riis, and M. Thorup, Static dictionaries on AC° RAMs: Query time Theta(sqrt(log n/log log n)) is necessary and sufficient, Tech. Rep. No. RS-97-14, BRICS, Dept. of Computer Science, Univ. of Aarhus, 1997 [Sect. 5]. A preliminary version appeared in Proc. 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1996), pp. 441-450.

  2. P. Beame, A switching lemma primer, manuscript, 1994.

  3. T. Hagerup, Simpler and faster dictionaries on the AC° PRAM, in Proc. 25th International Colloquium on Automata, Languages and Programming (ICALP 1998), Lecture Notes in Computer Science, Vol. 1443, Springer-Verlag, Berlin, pp. 79-90.

I. Randomisiertes Sortieren im eingeschränkten Modell

Es soll ein randomisierter Algorithmus von Thorup [1] vorgestellt werden, der n Elemente im eingeschränkten Modell in O(n log log n) Zeit und O(n) Platz sortieren kann.

Literatur

  1. M. Thorup, Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations, in Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1997), pp. 352-359.

J. Deterministisches Sortieren im eingeschränkten Modell mit linearem Speicherplatz

Es soll ein deterministischer Algorithmus von Thorup [1] vorgestellt werden, der n Elemente im eingeschränkten Modell in O(n(log log n)^2) Zeit und O(n) Platz sortieren kann.

Literatur

  1. M. Thorup, Faster deterministic sorting and priority queues in linear space, Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), pp. 550-555.

K. Schnelle Konstruktion statischer Wörterbücher

Die Artikel von Miltersen [1] und Hagerup [2] beschäftigen sich beide mit dem Problem, schnell ein statisches Wörterbuch für n vorgegebene Schlüssel zu erstellen, das danach Anfragen sehr schnell beantworten kann. Die Ergebnisse der beiden Artikel sollen besprochen werden.

Literatur

  1. P. B. Miltersen, Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries, in Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), pp. 556-563.

  2. T. Hagerup, Fast deterministic construction of static dictionaries, in Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), to appear.

L. Wann kann schneller sortiert werden?

Ben-Amram und Galil [1] haben sich genauer angeschaut, unter welchen Umständen Sortieren in o(n log n) Zeit möglich ist. Der Vortrag soll ihre Ergebnisse vorstellen und sie mit unserem Wissen aus früheren Vorträgen kontrastieren. Dabei sollen die unteren Schranken ausführlicher als die oberen Schranken behandelt werden.

Literatur

  1. A. M. Ben-Amram and Z. Galil, When can we sort in o(n log n) time?, in Proc. 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1993), pp. 538-546.

M. Wörterbücher mit allgemeineren Operationszeiten

Dieser Vortrag beschreibt, wie das Wörterbuch aus Vortrag A so verallgemeinert werden kann, daß nicht alle Operationen gleich viel Zeit benötigen. Z.B. können Einfügen und Streichen auf Kosten von Suchen billiger gemacht werden.

Literatur

  1. G. S. Brodal, Predecessor queries in dynamic integer sets, in Proc. 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1997), Lecture Notes in Computer Science, Springer-Verlag, Berlin, Vol. 1200, pp. 21-32.

N. Wörterbücher ohne Multiplikation in linearem Platz

Dieser Vortrag geht der Frage nach, wieviel langsamer das ungeordnete statische Wörterbuch aus Vortrag G wird, wenn keine exotischen AC°-Instruktionen, sondern nur die des eingeschränkten Modells zur Verfügung stehen.

Literatur

  1. A. Brodnik, P. B. Miltersen, and J. I. Munro, Trans-dichotomous algorithms without multiplication - some upper and lower bounds, in Proc. 5th International Workshop on Algorithms and Data Structures (WADS 1997), Lecture Notes in Computer Science, Vol. 1272, Springer, Berlin, pp. 426-439 [Sect. 1-3].