Inhaltsverzeichnis

Vorwort zur 4. Auflage

V

Inhaltsverzeichnis

VI

Einleitung

X

Danksagungen

XII

1. Begriffsbildung

1

1.1. Algorithmus

1

1.2. Komplexität

4

1.3. Verbrauch und Komplexität

5

2. Gleichwertige Lösungen

8

2.1. Maximale Teilsumme

8

2.1.1. Summen und Teilsummen

8

2.1.2. Aufgabenstellung

9

2.1.3. Intuitive Lösung

9

2.1.4. Zeitkomplexität der Lösung

10

2.1.5. Zeit für Raum

12

2.1.6. Teile und herrsche

13

2.1.7. Die optimale Lösung

16

2.1.8. Messergebnisse

18

2.1.9. Gleichwertigkeit von Algorithmen

19

2.2. Komplexitätsformel

20

2.3. Datenstrukturen

21

2.3.1. Reihungen

22

2.3.2. Verkettete Listen

23

2.3.3. Gleichwertigkeit von Datenstrukturen

27

3. Rekursion und Wiederholung

30

3.1. Rekursive Algorithmen

30

3.1.1. Fakultät

30

3.1.2. Die Fibonacci-Zahlen

31

3.1.3. Die Ackermann-Funktion

34

3.1.4. Die mathematische Induktion

34

3.1.5. Permutationen

37

3.2. Abarbeitung von Datenstrukturen

38

3.2.1. Iterative Abarbeitung von rekursiven Datenstrukturen

38

3.2.2. Rekursive Abarbeitung von rekursiven Datenstrukturen

39

3.2.3. Rekursive Abarbeitung von Reihungen

40

3.2.4. Iteratoren

42

3.3. Rekursive Kurven

43

3.3.1. Schneeflockenkurve

44

3.3.2. Die Pfeilspitzenkurve

46

3.3.3. Die Hilbert-Kurve

48

3.3.4. Ersetzen der Rekursion durch Wiederholung

51

3.4. Zurückverfolgung

53

3.4.1. Labyrinth

53

3.4.2. Der Weg des Springers

54

3.4.3. Die acht Damen

57

4. Suchen

60

4.1. Textsuche

60

4.2. Suchen in Sammlungen

64

4.3. Suchen in einer Reihung

66

4.3.1. Suchen in einer unsortierten Reihung

66

4.3.2. Lineares Suchen in einer sortierten Reihung

68

4.3.3. Binäres Suchen in einer sortierten Reihung

69

4.4. Suchen in einer verketteten Liste

70

4.4.1. Lineares Suchen in einer unsortierten Liste

71

4.4.2. Lineares Suchen in einer sortierten Liste

72

4.5. Hash-Tabellen

72

4.5.1. Funktionalität

73

4.5.2. Datenorganisation

74

4.5.3. Hash-Funktionen

77

4.5.4. Weitere Aspekte

81

4.6. Zeitkomplexitäten beim Suchen

82

5. Sortierverfahren

85

5.1. Die Problemstellung

85

5.1.1. Präzisierung des Problems und Grundbegriffe

86

5.1.2. Zeitbedarf und Zeitkomplexität

87

5.1.3. Sortieralgorithmen in Java-Standardbibliotheken

88

5.1.4. Entwurfsmuster Strategie

89

5.2. Quadratische Sortierverfahren

91

5.2.1. Sortieren durch Vertauschen benachbarter Elemente

91

5.2.2. Sortieren durch Einfügen

93

5.2.3. Sortieren durch Auswählen

95

5.3. Unterquadratische Verfahren

96

5.4. Rekursive Verfahren

98

5.4.1. Quicksort

98

5.4.2. Sortieren mit Mischen

101

5.5. Logarithmische Verfahren

101

5.5.1. Halde

102

5.5.2. Die Haldenbedingung

103

5.5.3. Senken

103

5.5.4. Zwei Phasen des Heap Sorts

104

5.5.5. Sortieren auf der Halde

105

5.6. Externe Sortierverfahren

107

5.6.1. Mischen

107

5.6.2. Sortierkanal

109

5.6.3. Mischkanal

110

5.6.4. Fibonacci-Mischen

111

6. Baumstrukturen

114

6.1. Binärbaum

114

6.1.1. Definition

114

6.1.2. Suchen im sortierten Binärbaum

117

6.1.3. Darstellung von Binärbäumen

118

6.2. Sortieren mit Binärbäumen

119

6.2.1. Binärbaum als Halde

120

6.2.2. Senken im Binärbaum

121

6.2.3. Baumsort

123

6.2.4. Durchwandern eines Binärbaums

124

6.3. Operationen für Binärbäume

126

6.3.1. Binärbaum aus Knoten

126

6.3.2. Eintragen in einen sortierten Binärbaum

127

6.3.3. Löschen in Binärbäumen

128

6.4. Ausgeglichene Bäume

131

6.4.1. Eintragen in ausgeglichene Bäume

132

6.4.2. Löschen in ausgeglichenen Bäumen

136

6.5. 2-3-4-Bäume

137

6.5.1. Definition

137

6.5.2. Spalten

138

6.5.3. Einfügen

140

6.6. Rot-Schwarz-Bäume

142

6.7. B-Bäume

148

7. Klassen von Algorithmen

151

7.1. Was ist ein algorithmisches Problem?

151

7.2. Theoretische Lösbarkeit von Problemen

156

7.2.1. Definitionen

156

7.2.2. Beispiele

156

7.2.3. Das Halteproblem

159

7.2.4. Das Kachelproblem

161

7.2.5. Das Paligrammproblem

163

7.2.6. Gleichwertigkeit von Grammatiken

164

7.3. Praktische Lösbarkeit von Problemen

165

7.3.1. Das zweite Kachelproblem

166

7.3.2. Das Rucksackproblem

167

7.3.3. Das Aufteilungsproblem

167

7.3.4. Das Problem des Handelsreisenden

167

7.3.5. Hamiltonsche Wege durch einen Graphen

168

7.3.6. Das Erfüllbarkeitsproblem

169

7.4. Die Klassen P und NP

170

7.5. Ist P = NP?

171

7.6. Übersicht über Problemklassen

173

Literaturverzeichnis

174

Empfehlungen

174

Programmverzeichnis

176

Abbildungs- und Tabellenverzeichnis

178

Sachwortverzeichnis

181