Verwaltung dynamischer Partitionen auf linearen Listen

Verfasser: Simonic, Klaus-Martin
Sachtitel: Verwaltung dynamischer Partitionen auf linearen Listen
Herausgeber: Graz 1990. 47 Bl. 4
Impressum: Graz, Techn. Univ., Inst. f. Grundlagen d. Informationsverarbeitung, Diplomarb. v. 1990
Standort: Hauptbibliothek - Magazin
Signatur: II 74.092a

Abstract
Wir betrachten das Problem, eine Partition der Menge U={1,2,...,n} unter den Operationen find(u) (identifiziere die Menge, die u enthaelt), split(u) (spalte die Menge find(u) in 2 Teilmengen, welche alle Elemente kleiner gleich bzw. groesser u beinhalten) und combine(u) (die umgekehrte Operation zu split) zu verwalten. Die Hauptschwierigkeiten bei der Entwicklung eines effizienten Loesungsalgorithmus resultieren aus den inkompatiblen Anforderungen, der zu unterstuetzenden Befehle, an die Datenstruktur. Im speziellen behandeln wir balancierte Baeume (Theta(log n) Laufzeit, O(n) Speicher) und geschichtete Baeume (Theta(log log n) Laufzeit, O(n) Speicher). Bezueglich des Pointermaschinenmodells sind diese Schranken bestmoeglich. Treten nur die Operationen find und split bzw. find und combine auf, so koennen diese in O(l) amortisierter Zeit und O(n) Speicher realisiert werden. Diese Algorithemen benoetigen das Random Access Maschinenmodell und wurden wesentlich vereinfacht. Abschliessend diskutieren wir die Frage, ob ein linearer Algorithmus fuer das Gesamtproblem existiert.

Betreuer
AURENHAMMER

Institut für Informationsverarbeitung und Computergestützte neue Medien