O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Algorithmen und Datenstrukturen, 5th Edition

Book Description

  • Solides Lehrbuch - grundlegend und umfassend * Java als Implementierungssprache, unter Berücksichtigung der Spezifika von Java mit Netzanschluss: Programmbeispiele/Animationen Autoren sind sehr angesehen und kompetent

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