Inhaltsverzeichnis

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