Datenstrukturen Und Effiziente Algorithmen: Band 1: Sortieren Und Suchen

ISBN-13: 9783322867872 / Niemiecki / Miękka / 2012 / 327 str.

Kurt Mehlhorn

Opis

Der Entwurf und die Analyse von Datenstrukturen und effizienten Algorithmen hat in den letzten Jahren groe Bedeutung erlangt: Algorithmus ist der zentrale Begriff der Informatik und Effizienz bedeutet Geld. Ich habe den Stoff in drei Bande und neun Kapitel gegliedert. Band 1: Sortieren und Suchen (Kapitel I bis ill) Band 2: Graphenalgorithmen und NP-Vollstandigkeit (Kapitel IV bis VI) Band 3: Mehrdimensionales Suchen und Algorithmische Geometrie (Kapitel VII und Vill), Algorithmische Paradigmen (Kapitel IX) Die Bande 2 und 3 haben Band 1 als gemeinsame Basis, sind aber voneinander un- abhangig. Groe Teile dieser Bande konnen ohne detaillierte Kenntnis von Band 1 gelesen werden; eine Kenntnis der algorithmischen Grundprinzipien, wie sie etwa in Kapitel I oder in vielen anderen Buchern uber Datenstrukturen und Algorith- men vermittelt werden, genugt. Die spezifischen Voraussetzungen fur die Bande 2 und 3 sind in den jeweiligen Vorworten angegeben. In allen drei Banden stellen wir wichtige effiziente Algorithmen fur die grundlegenden Probleme in dem jeweiligen Gebiet vor und analysieren sie. Wir messen dabei Effizienz durch die Laufzeit auf einem realistischen Modell einer Rechenanlage, das wir in Kapitel I einfuhren. Die meisten der vorgestellten Algorithmen wurden erst in den letzten Jahren gefunden; die Informatik ist ja schlielich eine sehr junge Wissenschaft. Es gibt kaum Satze in diesem Buch, die alter als 20 Jahre sind, und mindestens die Halfte des Stoffes ist junger als 10 Jahre. Ich habe stets versucht, den Leser bis an den Stand der Forschung heranzufuhren.

Spis treści

I. Grundlagen.- I.1. Maschinenmodelle: RAM und RASP.- I.2. Berechnungen mit Zufallszahlen.- I.3. Eine höhere Programmiersprache.- I.4. Strukturierte Datentypen.- I.4.1. Schlangen und Keller.- I.4.2. Listen.- I.4.3. Bäume.- I.5. Rekursion.- I.6. Asymptotische Aussagen.- I.7. Hintergrundspeicher.- I.8. Übungen.- I.9. Bibliographische Anmerkungen.- II. Sortieren.- II.1. Allgemeine Sortierverfahren.- II.1.1. Sortieren durch Auswahl, ein erster Versuch.- II.1.2. Sortieren durch Auswahl: Heapsort.- II.1.3. Sortieren durch Teilen: Quicksort.- II.1.4. Sortieren durch Mischen.- II.1.5. Vergleich mehrerer Algorithmen.- II.1.6. Untere Schranken.- II.2. Sortieren durch Verteilen.- II.2.1. Sortieren von Wörtern durch Verteilen.- II.2.2. Sortieren reeller Zahlen durch Verteilen.- II.3. Nochmals: Untere Schranken für Sortieren.- II.4. Der lineare Median-Algorithmus.- II.5. Übungen.- II.6. Bibliographische Anmerkungen.- III. Mengen.- III.1. Digitale Suchbäume.- III.1.1. TRIES.- III.1.2. Statische TRIES oder Komprimierung dünnbesetzter Tafeln.- III.2. Hashing.- III.2.1. Hashing mit Verkettung.- III.2.2. Hashing mit offener Adressierung.- III.2.3. Perfektes Hashing.- III.2.4. Universelles Hashing.- III.2.5. Erweiterbares Hashing.- III.3. Suchen in geordneten Mengen.- III.3.1. Binäre Suche und Suchbäume.- III.3.2. Interpolationssuche.- III.4. Gewichtete Bäume.- III.4.1. Optimale gewichtete Bäume, dynamisches Programmieren und Mustererkennung.- III.4.2. Nahezu optimale binäre Suchbäume.- III.5. Balancierte Bäume.- III.5.1. Gewichtsbalancierte Bäume.- III.5.2. Höhenbalancierte Bäume.- III.5.3. Weitere Betrachtungen zu (a,b)-Bäumen.- III.5.3.1. Mischbare Warteschlangen.- III.5.3.2. Amortisierung von Rebalancierungskosten und Sortieren vorsortierter Files.- III.5.3.3. Fingerbäume.- III.5.3.4. Randanalyse.- III.6. Dynamische gewichtete Bäume.- III.6.1. Selbstorganisierende Datenstrukturen — Analyse im amortisierten und im mittleren Fall.- III.6.1.1. Selbstorganisierende lineare Listen.- III.6.1.2. Splay-Bäume.- III.6.2. D-Bäume.- III.6.3. Eine Anwendung auf mehrdimensionales Suchen.- III.7. Ein Vergleich von Suchstrukturen.- III.8. Teilmengen eines kleinen Universums.- III.8.1. Das boolesche Feld (Bitvektor).- III.8.2. Verwaltung dynamischer Partitionen von linearen Listen.- III.8.3. Das Union-Find-Problem.- III.9. Übungen.- III.10. Bibliographische Anmerkungen.