Algorithmen und Datenstrukturen, 5th Edition

Table of contents

1. Vorwort
2. Vorwort zur 4. Auflage
3. Vorwort zur 3. Auflage
4. Vorwort zur 2. Auflage
5. Vorwort zur 1. Auflage
6. Danksagungen
7. Inhaltsverzeichnis
8. Teil I Grundlegende Konzepte
9. 1 Vorbemerkungen und Überblick
10. 1.1 Informatik, Algorithmen und Datenstrukturen
11. 1.2 Historischer Überblick: Algorithmen
12. 1.3 Historie von Programmiersprachen und Java
13. 1.4 Grundkonzepte der Programmierung in Java
14. 2 Algorithmische Grundkonzepte
15. 2.1 Intuitiver Algorithmusbegriff
16. 2.1.1 Beispiele für Algorithmen
17. 2.1.2 Bausteine für Algorithmen
18. 2.1.3 Pseudocode-Notation für Algorithmen
19. 2.1.4 Struktogramme
20. 2.1.5 Rekursion
21. 2.2 Sprachen und Grammatiken
22. 2.2.1 Begriffsbildung
23. 2.2.2 Reguläre Ausdrücke
24. 2.2.3 Backus-Naur-Form (BNF)
25. 2.3 Elementare Datentypen
26. 2.3.1 Datentypen als Algebren
27. 2.3.2 Signaturen von Datentypen
28. 2.3.3 Der Datentyp bool
29. 2.3.4 Der Datentyp integer
30. 2.3.5 Felder und Zeichenketten
31. 2.4 Terme
32. 2.4.1 Bildung von Termen
33. 2.4.2 Algorithmus zur Termauswertung
34. 2.5 Datentypen in Java
35. 2.5.1 Primitive Datentypen
36. 2.5.2 Referenzdatentypen
37. 2.5.3 Operatoren
38. 3 Algorithmenparadigmen
39. 3.1 Überblick über Algorithmenparadigmen
40. 3.2 Applikative Algorithmen
41. 3.2.1 Terme mit Unbestimmten
42. 3.2.2 Funktionsdefinitionen
43. 3.2.3 Auswertung von Funktionen
44. 3.2.4 Erweiterung der Funktionsdefinition
45. 3.2.5 Applikative Algorithmen
46. 3.2.6 Beispiele für applikative Algorithmen
47. 3.3 Imperative Algorithmen
48. 3.3.1 Grundlagen imperativer Algorithmen
49. 3.3.2 Komplexe Anweisungen
50. 3.3.3 Beispiele für imperative Algorithmen
51. 3.4 Das logische Paradigma
52. 3.4.1 Logik der Fakten und Regeln
53. 3.4.2 Deduktive Algorithmen
54. 3.5 Weitere Paradigmen
55. 3.5.1 Genetische Algorithmen
56. 3.5.2 Neuronale Netze
57. 3.6 Umsetzung in Java
58. 3.6.1 Ausdrücke und Anweisungen
59. 3.6.2 Methoden
60. 3.6.3 Applikative Algorithmen und Rekursion
61. 4 Literaturhinweise zum Teil I
62. Teil II Algorithmen
63. 5 Ausgewählte Algorithmen
64. 5.1 Suchen in sortierten Folgen
65. 5.1.1 Sequenzielle Suche
66. 5.1.2 Binäre Suche
67. 5.2 Sortieren
68. 5.2.1 Sortieren: Grundbegriffe
69. 5.2.2 Sortieren durch Einfügen
70. 5.2.3 Sortieren durch Selektion
71. 5.2.4 Sortieren durch Vertauschen: BubbleSort
72. 5.2.5 Sortieren durch Mischen: MergeSort
73. 5.2.6 QuickSort
74. 5.2.7 Sortierverfahren im Vergleich
75. 6 Formale Algorithmenmodelle
76. 6.1 Registermaschinen
77. 6.2 Abstrakte Maschinen
78. 6.3 Markov-Algorithmen
79. 6.4 Church’sche These
80. 6.5 Interpreter für formale Algorithmenmodelle in Java
81. 6.5.1 Java: Markov-Interpreter
82. 6.5.2 Registermaschine in Java
83. 7 Eigenschaften von Algorithmen
84. 7.1 Berechenbarkeit und Entscheidbarkeit
85. 7.1.1 Existenz nichtberechenbarer Funktionen
86. 7.1.2 Konkrete nichtberechenbare Funktionen
87. 7.1.3 Das Halteproblem
88. 7.1.4 Nichtentscheidbare Probleme
89. 7.1.5 Post’sches Korrespondenzproblem
90. 7.2 Korrektheit von Algorithmen
91. 7.2.1 Relative Korrektheit
92. 7.2.2 Korrektheit von imperativen Algorithmen
93. 7.2.3 Korrektheitsbeweise für Anweisungstypen
94. 7.2.4 Korrektheit imperativer Algorithmen an Beispielen
95. 7.2.5 Korrektheit applikativer Algorithmen
96. 7.3 Komplexität
97. 7.3.1 Motivierendes Beispiel
98. 7.3.2 Asymptotische Analyse
99. 7.3.3 Komplexitätsklassen
100. 7.3.4 Analyse von Algorithmen
101. 8 Entwurf von Algorithmen
102. 8.1 Entwurfsprinzipien
103. 8.1.1 Schrittweise Verfeinerung
104. 8.1.2 Einsatz von Algorithmenmustern
105. 8.1.3 Problemreduzierung durch Rekursion
106. 8.2 Algorithmenmuster: Greedy
107. 8.2.1 Greedy-Algorithmen am Beispiel
108. 8.2.2 Greedy: Optimales Kommunikationsnetz
109. 8.2.3 Verfeinerung der Suche nach billigster Kante
110. 8.3 Rekursion: Divide-and-conquer
111. 8.3.1 Das Prinzip »Teile und herrsche «
112. 8.3.2 Beispiel: Spielpläne für Turniere
113. 8.4 Rekursion: Backtracking
114. 8.4.1 Prinzip des Backtracking
115. 8.4.2 Beispiel: Das Acht-Damen-Problem
116. 8.4.3 Beispiel: Tic Tac Toe mit Backtracking
117. 8.5 Dynamische Programmierung
118. 8.5.1 Das Rucksackproblem
119. 8.5.2 Rekursive Lösung des Rucksackproblems
120. 8.5.3 Prinzip der dynamischen Programmierung
121. 9 Verteilte Berechnungen
122. 9.1 Kommunizierende Prozesse
123. 9.2 Modell der Petri-Netze
124. 9.2.1 Definition von Petri-Netzen
125. 9.2.2 Formalisierung von Petri-Netzen
126. 9.2.3 Das Beispiel der fünf Philosophen
127. 9.3 Programmieren nebenläufiger Abläufe
128. 9.3.1 Koordinierte Prozesse
129. 9.3.2 Programmieren mit Semaphoren
130. 9.3.3 Philosophenproblem mit Semaphoren
131. 9.3.4 Verklemmungsfreie Philosophen
132. 9.4 Beispielrealisierung in Java
133. 10 Literaturhinweise zum Teil II
134. Teil III Datenstrukturen
135. 11 Abstrakte Datentypen
136. 11.1 Signaturen und Algebren
137. 11.2 Algebraische Spezifikation
138. 11.2.1 Spezifikationen und Modelle
139. 11.2.2 Termalgebra und Quotiententermalgebra
140. 11.2.3 Probleme mit initialer Semantik
141. 11.3 Beispiele für abstrakte Datentypen
142. 11.3.1 Der Kellerspeicher (Stack)
143. 11.3.2 Beispiel für Kellernutzung
144. 11.3.3 Die Warteschlange (Queue)
145. 11.4 Entwurf von Datentypen
146. 12 Klassen, Schnittstellen und Objekte in Java
147. 12.1 Grundzüge der Objektorientierung
148. 12.2 Klassen und Objekte in Java
149. 12.3 Vererbung
150. 12.4 Abstrakte Klassen und Schnittstellen
151. 12.5 Ausnahmen
152. 12.6 Umsetzung abstrakter Datentypen
153. 12.6.1 Lambda-Ausdrücke in Java 8
154. 13 Grundlegende Datenstrukturen
155. 13.1 Stack und Queue als Datentypen
156. 13.1.1 Implementierung des Stacks
157. 13.1.2 Implementierung der Queue
158. 13.1.3 Bewertung der Implementierungen
159. 13.2 Verkettete Listen
160. 13.3 Doppelt verkettete Listen
161. 13.4 Das Iterator-Konzept
162. 13.5 Java Collection Framework
163. 13.6 J2SE 5.0 und Generics
164. 14 Bäume
165. 14.1 Bäume: Begriffe und Konzepte
166. 14.2 Binärer Baum: Datentyp und Basisalgorithmen
167. 14.2.1 Der Datentyp »Binärer Baum«
168. 14.2.2 Algorithmen zur Traversierung
169. 14.3 Suchbäume
170. 14.3.1 Suchen in Suchbäumen
171. 14.3.2 Einfügen und Löschen
172. 14.3.3 Komplexität der Operationen
173. 14.4 Ausgeglichene Bäume
174. 14.4.1 Rot-Schwarz-Bäume
175. 2-3-4-Bäume
176. 14.4.2 AVL-Bäume
177. 14.4.3 B-Bäume
178. 14.5 Digitale Bäume
179. 14.5.1 Tries
180. 14.5.2 Patricia-Bäume
181. 14.6 Praktische Nutzung von Bäumen
182. 14.6.1 Sortieren mit Bäumen: HeapSort
183. 14.6.2 Sets mit binären Suchbäumen
184. 15 Hashverfahren
185. 15.1 Grundprinzip des Hashens
186. 15.2 Grundlagen und Verfahren
187. 15.2.1 Hashfunktionen
188. 15.2.2 Behandlung von Kollisionen
189. 15.2.3 Aufwand beim Hashen
190. 15.2.4 Hashen in Java
191. 15.3 Dynamische Hashverfahren
192. 15.3.1 Grundideen für dynamische Hashverfahren
193. 15.3.2 Erweiterbares Hashen
194. 15.3.3 Umsetzung des erweiterbaren Hashens
195. 16 Graphen
196. 16.1 Arten von Graphen
197. 16.1.1 Ungerichtete Graphen
198. 16.1.2 Gerichtete Graphen
199. 16.1.3 Gewichtete Graphen
200. 16.2 Realisierung von Graphen
201. 16.2.1 Knoten- und Kantenlisten
202. 16.2.2 Adjazenzmatrix
203. 16.2.3 Graphen als dynamische Datenstrukturen
204. 16.2.4 Transformationen zwischen Darstellungen
205. 16.2.5 Vergleich der Komplexität
206. 16.2.6 Eine Java-Klasse für Graphen
207. 16.3 Ausgewählte Graphenalgorithmen
208. 16.3.1 Breitendurchlauf
209. 16.3.2 Tiefendurchlauf
210. 16.3.3 Zyklenfreiheit und topologisches Sortieren
211. 16.4 Algorithmen auf gewichteten Graphen
212. 16.4.1 Kürzeste Wege
213. 16.4.2 Dijkstras Algorithmus
214. 16.4.3 A*-Algorithmus
215. 16.4.4 Kürzeste Wege mit negativen Kantengewichten
216. 16.4.5 Maximaler Durchfluss
217. 16.4.6 Der Ford-Fulkerson-Algorithmus für die Bestimmung des maximalen Flusses
218. 16.5 Weitere Fragestellungen für Graphen
219. Problem des Handlungsreisenden
220. Planare Graphen
221. Einfärben von Graphen
222. 17 Algorithmen auf Texten
223. 17.1 Probleme der Worterkennung
224. 17.2 Knuth-Morris-Pratt
225. 17.3 Boyer-Moore
226. 17.4 Pattern Matching
227. 17.4.1 Reguläre Ausdrücke
228. 17.4.2 Endliche Automaten
229. 17.4.3 Java-Klassen für reguläre Ausdrücke
230. 17.5 Ähnlichkeit von Zeichenketten
231. 17.5.1 Levenshtein-Distanz
232. 17.5.2 n-Gramme
233. 17.5.3 Zusammenfassung
234. 18 Literaturhinweise zum Teil III
235. Teil IV Anhang
236. A Quelltext der Klasse IOUtils
237. Abbildungsverzeichnis
238. Tabellenverzeichnis
239. Algorithmenverzeichnis
240. Beispielverzeichnis
241. Programmverzeichnis
242. Literaturverzeichnis
243. Index