Inhaltsverzeichnis

des Lehrbuchs

Grundkurs Algorithmen und Datenstrukturen (Springer Verlag , 6. Auflage, 2018)

Inhaltsverzeichnis
Vorwort zur 6. Auflage
Inhaltsverzeichnis
Einleitung

1. Begriffsbildung
1.1. Algorithmus
1.2. Komplexität
1.3. Verbrauch und Komplexität

2. Gleichwertige Lösungen
2.1. Maximale Teilsumme
2.1.1. Summen und Teilsummen
2.1.2. Aufgabenstellung
2.1.3. Intuitive Lösung
2.1.4. Zeitkomplexität der Lösung
2.1.5. Zeit für Raum
2.1.6. Teile und herrsche
2.1.7. Die optimale Lösung
2.1.8. Messergebnisse
2.1.9. Gleichwertigkeit von Algorithmen

2.2. Komplexitätsformel

2.3. Datenstrukturen
2.3.1. Reihungen
2.3.2. Verkettete Listen
2.3.3. Gleichwertigkeit von Datenstrukturen
2.3.4. Berechnung von Ausdrücken

3. Rekursion und Wiederholung
3.1. Rekursive Algorithmen
3.1.1. Fakultät
3.1.2. Die Fibonacci-Zahlen
3.1.3. Die Ackermann-Funktion
3.1.4. Die mathematische Induktion
3.1.5. Permutationen

3.2. Abarbeitung von Datenstrukturen
3.2.1. Iterative Abarbeitung von rekursiven Datenstrukturen
3.2.2. Rekursive Abarbeitung von rekursiven Datenstrukturen
3.2.3. Rekursive Abarbeitung von Reihungen
3.2.4. Iteratoren
3.2.5. Lambda-Ausdrücke

3.3. Rekursive Kurven
3.3.1. Schneeflockenkurve
3.3.2. Die Pfeilspitzenkurve
3.3.3. Die Hilbert-Kurve
3.3.4. Ersetzen der Rekursion durch Wiederholung

3.4. Zurückverfolgung
3.4.1. Labyrinth
3.4.2. Der Weg des Springers
3.4.3. Die acht Damen

4. Suchen
4.1. Textsuche

4.2. Suchen in Sammlungen

4.3. Suchen in einer Reihung
4.3.1. Suchen in einer unsortierten Reihung
4.3.2. Lineares Suchen in einer sortierten Reihung
4.3.3. Binäres Suchen in einer sortierten Reihung

4.4. Suchen in einer verketteten Liste
4.4.1. Lineares Suchen in einer unsortierten Liste
4.4.2. Lineares Suchen in einer sortierten Liste
4.4.3. Listen funktional

4.5. Hash-Tabellen
4.5.1. Funktionalität
4.5.2. Datenorganisation
4.5.3. Hash-Funktionen
4.5.4. Weitere Aspekte

4.6. Zeitkomplexitäten beim Suchen

5. Sortierverfahren
5.1. Die Problemstellung
5.1.1. Präzisierung des Problems und Grundbegriffe
5.1.2. Zeitbedarf und Zeitkomplexität
5.1.3. Sortieralgorithmen in Java-Standardbibliotheken
5.1.4. Entwurfsmuster Strategie

5.2. Quadratische Sortierverfahren
5.2.1. Sortieren durch Vertauschen benachbarter Elemente
5.2.2. Sortieren durch Einfügen
5.2.3. Sortieren durch Auswählen
5.3. Unterquadratische Verfahren

5.4. Rekursive Verfahren
5.4.1. Quicksort
5.4.2. Sortieren mit Mischen

5.5. Logarithmische Verfahren
5.5.1. Halde
5.5.2. Die Haldenbedingung
5.5.3. Senken
5.5.4. Zwei Phasen des Heap Sorts
5.5.5. Sortieren auf der Halde

5.6. Sortieren von Listen
5.7. Externe Sortierverfahren
5.7.1. Mischen
5.7.2. Sortierkanal
5.7.3. Mischkanal
5.7.4. Fibonacci-Mischen

6. Baumstrukturen
6.1. Binärbaum
6.1.1. Definition
6.1.2. Suchen im sortierten Binärbaum
6.1.3. Darstellung von Binärbäumen

6.2. Sortieren mit Binärbäumen
6.2.1. Binärbaum als Halde
6.2.2. Senken im Binärbaum
6.2.3. Baumsort
6.2.4. Durchwandern eines Binärbaums

6.3. Operationen für Binärbäume
6.3.1. Binärbaum aus Knoten
6.3.2. Eintragen in einen sortierten Binärbaum
6.3.3. Löschen in Binärbäumen

6.4. Ausgeglichene Bäume
6.4.1. Eintragen in ausgeglichene Bäume
6.4.2. Löschen in ausgeglichenen Bäumen

6.5. 2-3-4-Bäume
6.5.1. Definition
6.5.2. Spalten
6.5.3. Einfügen

6.6. Rot-Schwarz-Bäume

6.7. B-Bäume

6.8. Bäume in den Standardklassen

7. Klassen von Algorithmen
7.1. Was ist ein algorithmisches Problem?

7.2. Theoretische Lösbarkeit von Problemen
7.2.1. Definitionen
7.2.2. Beispiele
7.2.3. Das Halteproblem
7.2.4. Das Kachelproblem
7.2.5. Das Paligrammproblem
7.2.6. Gleichwertigkeit von Grammatiken

7.3. Praktische Lösbarkeit von Problemen
7.3.1. Das zweite Kachelproblem
7.3.2. Das Rucksackproblem
7.3.3. Das Aufteilungsproblem
7.3.4. Das Problem des Handelsreisenden
7.3.5. Hamiltonsche Wege durch einen Graphen
7.3.6. Das Erfüllbarkeitsproblem

7.4. Die Klassen P und NP

7.5. Ist P = NP?

7.6. Übersicht über Problemklassen

Verzeichnisse
Literaturverzeichnis
Empfehlungen
Java 8
Programmverzeichnis
Abbildungs- und Tabellenverzeichni
Sachwortverzeichnis