Algorithmen und Datenstrukturen, 4th Edition

Table of contents

1. Cover
2. Titel
3. Impressum
4. Vorwort
5. Inhaltsverzeichnis
6. I Grundlegende Konzepte
   1. 1 Vorbemerkungen und Überblick
      1. 1.1 Informatik, Algorithmen und Datenstrukturen
      2. 1.2 Historischer Überblick: Algorithmen
      3. 1.3 Historie von Programmiersprachen und Java
      4. 1.4 Grundkonzepte der Programmierung in Java
   2. 2 Algorithmische Grundkonzepte
      1. 2.1 Intuitiver Algorithmusbegriff
         1. 2.1.1 Beispiele für Algorithmen
         2. 2.1.2 Bausteine für Algorithmen
         3. 2.1.3 Pseudocode-Notation für Algorithmen
         4. 2.1.4 Struktogramme
         5. 2.1.5 Rekursion
      2. 2.2 Sprachen und Grammatiken
         1. 2.2.1 Begriffsbildung
         2. 2.2.2 Reguläre Ausdrücke
         3. 2.2.3 Backus-Naur-Form (BNF)
      3. 2.3 Elementare Datentypen
         1. 2.3.1 Datentypen als Algebren
         2. 2.3.2 Signaturen von Datentypen
         3. 2.3.3 Der Datentyp bool
         4. 2.3.4 Der Datentyp integer
         5. 2.3.5 Felder und Zeichenketten
      4. 2.4 Terme
         1. 2.4.1 Bildung von Termen
         2. 2.4.2 Algorithmus zur Termauswertung
      5. 2.5 Datentypen in Java
         1. 2.5.1 Primitive Datentypen
         2. 2.5.2 Referenzdatentypen
         3. 2.5.3 Operatoren
   3. 3 Algorithmenparadigmen
      1. 3.1 Überblick über Algorithmenparadigmen
      2. 3.2 Applikative Algorithmen
         1. 3.2.1 Terme mit Unbestimmten
         2. 3.2.2 Funktionsdefinitionen
         3. 3.2.3 Auswertung von Funktionen
         4. 3.2.4 Erweiterung der Funktionsdefinition
         5. 3.2.5 Applikative Algorithmen
         6. 3.2.6 Beispiele für applikative Algorithmen
      3. 3.3 Imperative Algorithmen
         1. 3.3.1 Grundlagen imperativer Algorithmen
         2. 3.3.2 Komplexe Anweisungen
         3. 3.3.3 Beispiele für imperative Algorithmen
      4. 3.4 Das logische Paradigma
         1. 3.4.1 Logik der Fakten und Regeln
         2. 3.4.2 Deduktive Algorithmen
      5. 3.5 Weitere Paradigmen
         1. 3.5.1 Genetische Algorithmen
         2. 3.5.2 Neuronale Netze
      6. 3.6 Umsetzung in Java
         1. 3.6.1 Ausdrücke und Anweisungen
         2. 3.6.2 Methoden
         3. 3.6.3 Applikative Algorithmen und Rekursion
   4. 4 Literaturhinweise zum Teil I
7. II Algorithmen
   1. 5 Ausgewählte Algorithmen
      1. 5.1 Suchen in sortierten Folgen
         1. 5.1.1 Sequenzielle Suche
         2. 5.1.2 Binäre Suche
      2. 5.2 Sortieren
         1. 5.2.1 Sortieren: Grundbegriffe
         2. 5.2.2 Sortieren durch Einfügen
         3. 5.2.3 Sortieren durch Selektion
         4. 5.2.4 Sortieren durch Vertauschen: BubbleSort
         5. 5.2.5 Sortieren durch Mischen: MergeSort
         6. 5.2.6 QuickSort
         7. 5.2.7 Sortierverfahren im Vergleich
   2. 6 Formale Algorithmenmodelle
      1. 6.1 Registermaschinen
      2. 6.2 Abstrakte Maschinen
      3. 6.3 Markov-Algorithmen
      4. 6.4 Church’sche These
      5. 6.5 Interpreter für formale Algorithmenmodelle in Java
         1. 6.5.1 Java: Markov-Interpreter
         2. 6.5.2 Registermaschine in Java
   3. 7 Eigenschaften von Algorithmen
      1. 7.1 Berechenbarkeit und Entscheidbarkeit
         1. 7.1.1 Existenz nichtberechenbarer Funktionen
         2. 7.1.2 Konkrete nichtberechenbare Funktionen
         3. 7.1.3 Das Halteproblem
         4. 7.1.4 Nichtentscheidbare Probleme
         5. 7.1.5 Post’sches Korrespondenzproblem
      2. 7.2 Korrektheit von Algorithmen
         1. 7.2.1 Relative Korrektheit
         2. 7.2.2 Korrektheit von imperativen Algorithmen
         3. 7.2.3 Korrektheitsbeweise für Anweisungstypen
         4. 7.2.4 Korrektheit imperativer Algorithmen an Beispielen
         5. 7.2.5 Korrektheit applikativer Algorithmen
      3. 7.3 Komplexität
         1. 7.3.1 Motivierendes Beispiel
         2. 7.3.2 Asymptotische Analyse
         3. 7.3.3 Komplexitätsklassen
         4. 7.3.4 Analyse von Algorithmen
   4. 8 Entwurf von Algorithmen
      1. 8.1 Entwurfsprinzipien
         1. 8.1.1 Schrittweise Verfeinerung
         2. 8.1.2 Einsatz von Algorithmenmustern
         3. 8.1.3 Problemreduzierung durch Rekursion
      2. 8.2 Algorithmenmuster: Greedy
         1. 8.2.1 Greedy-Algorithmen am Beispiel
         2. 8.2.2 Greedy: Optimales Kommunikationsnetz
         3. 8.2.3 Verfeinerung der Suche nach billigster Kante
      3. 8.3 Rekursion: Divide-and-conquer
         1. 8.3.1 Das Prinzip »Teile und herrsche«
         2. 8.3.2 Beispiel: Spielpläne für Turniere
      4. 8.4 Rekursion: Backtracking
         1. 8.4.1 Prinzip des Backtracking
         2. 8.4.2 Beispiel: Das Acht-Damen-Problem
      5. 8.5 Dynamische Programmierung
         1. 8.5.1 Das Rucksackproblem
         2. 8.5.2 Rekursive Lösung des Rucksackproblems
         3. 8.5.3 Prinzip der dynamischen Programmierung
   5. 9 Verteilte Berechnungen
      1. 9.1 Kommunizierende Prozesse
      2. 9.2 Modell der Petri-Netze
         1. 9.2.1 Definition von Petri-Netzen
         2. 9.2.2 Formalisierung von Petri-Netzen
         3. 9.2.3 Das Beispiel der fünf Philosophen
      3. 9.3 Programmieren nebenläufiger Abläufe
         1. 9.3.1 Koordinierte Prozesse
         2. 9.3.2 Programmieren mit Semaphoren
         3. 9.3.3 Philosophenproblem mit Semaphoren
         4. 9.3.4 Verklemmungsfreie Philosophen
      4. 9.4 Beispielrealisierung in Java
   6. 10 Literaturhinweise zum Teil II
8. III Datenstrukturen
   1. 11 Abstrakte Datentypen
      1. 11.1 Signaturen und Algebren
      2. 11.2 Algebraische Spezifikation
         1. 11.2.1 Spezifikationen und Modelle
         2. 11.2.2 Termalgebra und Quotiententermalgebra
         3. 11.2.3 Probleme mit initialer Semantik
      3. 11.3 Beispiele für abstrakte Datentypen
         1. 11.3.1 Der Kellerspeicher (Stack)
         2. 11.3.2 Beispiel für Kellernutzung
         3. 11.3.3 Die Warteschlange (Queue)
      4. 11.4 Entwurf von Datentypen
   2. 12 Klassen, Schnittstellen und Objekte in Java
      1. 12.1 Grundzüge der Objektorientierung
      2. 12.2 Klassen und Objekte in Java
      3. 12.3 Vererbung
      4. 12.4 Abstrakte Klassen und Schnittstellen
      5. 12.5 Ausnahmen
      6. 12.6 Umsetzung abstrakter Datentypen
   3. 13 Grundlegende Datenstrukturen
      1. 13.1 Stack und Queue als Datentypen
         1. 13.1.1 Implementierung des Stacks
         2. 13.1.2 Implementierung der Queue
         3. 13.1.3 Bewertung der Implementierungen
      2. 13.2 Verkettete Listen
      3. 13.3 Doppelt verkettete Listen
      4. 13.4 Das Iterator-Konzept
      5. 13.5 Java Collection Framework
      6. 13.6 J 2SE 5.0 und Generics
   4. 14 Bäume
      1. 14.1 Bäume: Begriffe und Konzepte
      2. 14.2 Binärer Baum: Datentyp und Basisalgorithmen
         1. 14.2.1 Der Datentyp »Binärer Baum«
         2. 14.2.2 Algorithmen zur Traversierung
      3. 14.3 Suchbäume
         1. 14.3.1 Suchen in Suchbäumen
         2. 14.3.2 Einfügen und Löschen
         3. 14.3.3 Komplexität der Operationen
      4. 14.4 Ausgeglichene Bäume
         1. 14.4.1 Rot-Schwarz-Bäume
         2. 14.4.2 AVL-Bäume
         3. 14.4.3 B-Bäume
      5. 14.5 Digitale Bäume
         1. 14.5.1 Tries
         2. 14.5.2 Patricia-Bäume
      6. 14.6 Praktische Nutzung von Bäumen
         1. 14.6.1 Sortieren mit Bäumen: HeapSort
         2. 14.6.2 Sets mit binären Suchbäumen
   5. 15 Hashverfahren
      1. 15.1 Grundprinzip des Hashens
      2. 15.2 Grundlagen und Verfahren
         1. 15.2.1 Hashfunktionen
         2. 15.2.2 Behandlung von Kollisionen
         3. 15.2.3 Aufwand beim Hashen
         4. 15.2.4 Hashen in Java
      3. 15.3 Dynamische Hashverfahren
         1. 15.3.1 Grundideen für dynamische Hashverfahren
         2. 15.3.2 Erweiterbares Hashen
         3. 15.3.3 Umsetzung des erweiterbaren Hashens
   6. 16 Graphen
      1. 16.1 Arten von Graphen
         1. 16.1.1 Ungerichtete Graphen
         2. 16.1.2 Gerichtete Graphen
         3. 16.1.3 Gewichtete Graphen
      2. 16.2 Realisierung von Graphen
         1. 16.2.1 Knoten- und Kantenlisten
         2. 16.2.2 Adjazenzmatrix
         3. 16.2.3 Graphen als dynamische Datenstrukturen
         4. 16.2.4 Transformationen zwischen Darstellungen
         5. 16.2.5 Vergleich der Komplexität
         6. 16.2.6 Eine Java-Klasse für Graphen
      3. 16.3 Ausgewählte Graphenalgorithmen
         1. 16.3.1 Breitendurchlauf
         2. 16.3.2 Tiefendurchlauf
         3. 16.3.3 Zyklenfreiheit und topologisches Sortieren
      4. 16.4 Algorithmen auf gewichteten Graphen
         1. 16.4.1 Kürzeste Wege
         2. 16.4.2 Dijkstras Algorithmus
         3. 16.4.3 A*-Algorithmus
         4. 16.4.4 Kürzeste Wege mit negativen Kantengewichten
         5. 16.4.5 Maximaler Durchfluss
         6. 16.4.6 Der Ford-Fulkerson-Algorithmus
      5. 16.5 Weitere Fragestellungen für Graphen
   7. 17 Suchen in Texten
      1. 17.1 Probleme der Worterkennung
      2. 17.2 Knuth-Morris-Pratt
      3. 17.3 Boyer-Moore
      4. 17.4 Pattern Matching
         1. 17.4.1 Reguläre Ausdrücke
         2. 17.4.2 Endliche Automaten
         3. 17.4.3 Java-Klassen für reguläre Ausdrücke
         4. 17.4.4 Ähnlichkeit von Zeichenketten: Die Levenshtein-Distanz
   8. 18 Literaturhinweise zum Teil III
9. A Quelltext der Klasse IOUtils
10. Abbildungsverzeichnis
11. Tabellenverzeichnis
12. Algorithmenverzeichnis
13. Beispielverzeichnis
14. Programmverzeichnis
15. Literaturverzeichnis
16. Index