|
Folien
Übungen
Programme
Bilder
 Zurück
|
Multimedia-Ergänzungen zum Buch: Algorithmen und Datenstrukturen, Kapitel 6: Manipulation von Mengen
|
|
|
Datenstrukturen
zur Repräsentation einer Kollektion von Datenmengen, auf der gewisse
Operationen ausgeführt werden sollen, wurden erstmals von Aho, Hopcroft
und Ullman systematisch behandelt. Die abstrakte Behandlung solcher Mengenmanipulationsprobleme
erleichtert in vielen Fällen den Entwurf und die Analyse von Algorithmen
aus verschiedenen Anwendungsgebieten.
Man formuliert Algorithmen zunächst auf hohem Niveau unter Rückgriff auf
Strukturen und Operationen zur Manipulation von Mengen, die in herkömmlichen
Programmiersprachen üblicherweise nicht vorkommen. In einem zweiten
Schritt überlegt man sich dann, wie die Kollektion von Datenmengen und
die benötigten Operationen implementiert, also programmtechnisch
realisiert werden können. Besonders erfolgreich war dieser Ansatz bei der
Verbesserung und Neuentwicklung von Algorithmen auf Graphen.
Einen
wichtigen Spezialfall eines Mengenmanipulationsproblems, das sogenannte Wörterbuchproblem,
haben wir im
Kapitel 1 und besonders im Kapitel 5 bereits ausführlich behandelt. Dort
ging es um die Frage, wie eine Menge von Schlüsseln abgespeichert werden
soll, damit die Operationen Suchen (Zugriff), Einfügen und Entfernen von Schlüsseln
möglichst effizient ausführbar sind. Wir werden sehen, dass die im
Kapitel 5 zur Lösung des Wörterbuchproblems benutzten Bäume auch für
viele andere Mengenmanipulationsprobleme benutzt werden können.
Wir gehen in diesem Kapitel davon aus, dass die Datenmengen stets Mengen
ganzzahliger Schlüssel sind, obwohl die Schlüssel in den meisten
Anwendungen lediglich zur eindeutigen Identifizierung der „eigentlichen“ Information
dienen.
|
|
Bei Fragen zu
dem Inhalt des Buches senden Sie bitte eine Email an ad-buch@informatik.uni-freiburg.de.
|
|