Algorithmen und Datenstrukturen - Eine Einführung mit Java
von: Gunter Saake, Kai-Uwe Sattler
dpunkt, 2006
ISBN: 9783898649612
Sprache: Deutsch
531 Seiten, Download: 2850 KB
Format: PDF, auch als Online-Lesen
Vorwort | 6 | ||
Vorwort zur 2. Auflage | 6 | ||
Vorwort zur 1. Auflage | 7 | ||
Danksagungen | 9 | ||
Inhaltsverzeichnis | 12 | ||
Teil I Grundlegende Konzepte | 20 | ||
1 Vorbemerkungen und Überblick | 22 | ||
1.1 Informatik, Algorithmen und | 22 | ||
Datenstrukturen | 22 | ||
1.2 Historischer Überblick: Algorithmen | 24 | ||
1.3 Historie von Programmiersprachen und | 25 | ||
Java | 25 | ||
1.4 Grundkonzepte der Programmierung in | 27 | ||
Java | 27 | ||
2 Algorithmische Grundkonzepte | 34 | ||
2.1 Intuitiver Algorithmusbegriff | 34 | ||
2.1.1 Beispiele für Algorithmen | 34 | ||
2.1.2 Bausteine für Algorithmen | 38 | ||
2.1.3 Pseudocode-Notation für Algorithmen | 40 | ||
2.1.4 Struktogramme | 45 | ||
2.1.5 Rekursion | 45 | ||
2.2 Sprachen und Grammatiken | 48 | ||
2.2.1 Begriffsbildung | 49 | ||
2.2.2 Reguläre Ausdrücke | 50 | ||
2.2.3 Backus-Naur-Form (BNF) | 51 | ||
2.3 Elementare Datentypen | 53 | ||
2.3.1 Datentypen als Algebren | 53 | ||
2.3.2 Signaturen von Datentypen | 54 | ||
2.3.3 Der Datentyp | 55 | ||
2.3.4 Der Datentyp | 56 | ||
2.3.5 Felder und Zeichenketten | 57 | ||
2.4 Terme | 59 | ||
2.4.1 Bildung von Termen | 59 | ||
2.4.2 Algorithmus zur Termauswertung | 61 | ||
2.5 Datentypen in Java | 62 | ||
2.5.1 Primitive Datentypen | 62 | ||
2.5.2 Referenzdatentypen | 64 | ||
2.5.3 Operatoren | 68 | ||
3 Algorithmenparadigmen | 72 | ||
3.1 Überblick über Algorithmenparadigmen | 72 | ||
3.2 Applikative Algorithmen | 73 | ||
3.2.1 Terme mit Unbestimmten | 73 | ||
3.2.2 Funktionsde.nitionen | 74 | ||
3.2.3 Auswertung von Funktionen | 74 | ||
3.2.4 Erweiterung der Funktionsde.nition | 76 | ||
3.2.5 Applikative Algorithmen | 77 | ||
3.2.6 Beispiele für applikative Algorithmen | 78 | ||
3.3 Imperative Algorithmen | 86 | ||
3.3.1 Grundlagen imperativer Algorithmen | 86 | ||
3.3.2 Komplexe Anweisungen | 89 | ||
3.3.3 Beispiele für imperative Algorithmen | 92 | ||
3.4 Das logische Paradigma | 98 | ||
3.4.1 Logik der Fakten und Regeln | 98 | ||
3.4.2 Deduktive Algorithmen | 100 | ||
3.5 Weitere Paradigmen | 104 | ||
3.5.1 Genetische Algorithmen | 105 | ||
3.5.2 Neuronale Netze | 108 | ||
3.6 Umsetzung in Java | 111 | ||
3.6.1 Ausdrücke und Anweisungen | 112 | ||
3.6.2 Methoden | 119 | ||
3.6.3 Applikative Algorithmen und Rekursion | 124 | ||
4 Literaturhinweise zum Teil I | 130 | ||
Teil II Algorithmen | 132 | ||
5 Ausgewählte Algorithmen | 134 | ||
5.1 Suchen in sortierten Folgen | 134 | ||
5.1.1 Sequenzielle Suche | 135 | ||
5.1.2 Binäre Suche | 137 | ||
5.2 Sortieren | 141 | ||
5.2.1 Sortieren: Grundbegriffe | 141 | ||
5.2.2 Sortieren durch Einfügen | 142 | ||
5.2.3 Sortieren durch Selektion | 144 | ||
5.2.4 Sortieren durch Vertauschen: BubbleSort | 146 | ||
5.2.5 Sortieren durch Mischen: MergeSort | 148 | ||
5.2.6 QuickSort | 152 | ||
5.2.7 Sortierverfahren im Vergleich | 156 | ||
6 Formale Algorithmenmodelle | 160 | ||
6.1 Registermaschinen | 160 | ||
6.2 Abstrakte Maschinen | 169 | ||
6.3 Markov-Algorithmen | 173 | ||
6.4 Church’sche These | 179 | ||
6.5 Interpreter für formale | 181 | ||
Algorithmenmodelle in Java | 181 | ||
6.5.1 Java: Markov-Interpreter | 181 | ||
6.5.2 Registermaschine in Java | 183 | ||
7 Eigenschaften von Algorithmen | 190 | ||
7.1 Berechenbarkeit und Entscheidbarkeit | 190 | ||
7.1.1 Existenz nichtberechenbarer Funktionen | 191 | ||
7.1.2 Konkrete nichtberechenbare Funktionen | 193 | ||
7.1.3 Das Halteproblem | 195 | ||
7.1.4 Nichtentscheidbare Probleme | 197 | ||
7.1.5 Post’sches Korrespondenzproblem | 198 | ||
7.2 Korrektheit von Algorithmen | 200 | ||
7.2.1 Relative Korrektheit | 200 | ||
7.2.2 Korrektheit von imperativen Algorithmen | 201 | ||
7.2.3 Korrektheitsbeweise für Anweisungstypen | 204 | ||
7.2.4 Korrektheit imperativer Algorithmen an | 206 | ||
Beispielen | 206 | ||
7.2.5 Korrektheit applikativer Algorithmen | 211 | ||
7.3 Komplexität | 213 | ||
7.3.1 Motivierendes Beispiel | 213 | ||
7.3.2 Asymptotische Analyse | 214 | ||
7.3.3 Komplexitätsklassen | 218 | ||
7.3.4 Analyse von Algorithmen | 221 | ||
8 Entwurf von Algorithmen | 224 | ||
8.1 Entwurfsprinzipien | 224 | ||
8.1.1 Schrittweise Verfeinerung | 224 | ||
8.1.2 Einsatz von Algorithmenmustern | 225 | ||
8.1.3 Problemreduzierung durch Rekursion | 225 | ||
8.2 Algorithmenmuster: Greedy | 226 | ||
8.2.1 Greedy-Algorithmen am Beispiel | 226 | ||
8.2.2 Greedy: Optimales Kommunikationsnetz | 228 | ||
8.2.3 Verfeinerung der Suche nach billigster Kante | 229 | ||
8.3 Rekursion: Divide-and-conquer | 231 | ||
8.3.1 Das Prinzip | 231 | ||
Teile und herrsche | 231 | ||
8.3.2 Beispiel: Spielpläne für Turniere | 233 | ||
8.4 Rekursion: Backtracking | 235 | ||
8.4.1 Prinzip des Backtracking | 236 | ||
8.4.2 Beispiel: Das Acht-Damen-Problem | 237 | ||
8.5 Dynamische Programmierung | 240 | ||
8.5.1 Das Rucksackproblem | 241 | ||
8.5.2 Rekursive Lösung des Rucksackproblems | 242 | ||
8.5.3 Prinzip der dynamischen Programmierung | 243 | ||
9 Verteilte Berechnungen | 246 | ||
9.1 Kommunizierende Prozesse | 246 | ||
9.2 Modell der Petri-Netze | 247 | ||
9.2.1 De.nition von Petri-Netzen | 247 | ||
9.2.2 Formalisierung von Petri-Netzen | 251 | ||
9.2.3 Das Beispiel der fünf Philosophen | 253 | ||
9.3 Programmieren nebenläu.ger Abläufe | 255 | ||
9.3.1 Koordinierte Prozesse | 256 | ||
9.3.2 Programmieren mit Semaphoren | 257 | ||
9.3.3 Philosophenproblem mit Semaphoren | 259 | ||
9.3.4 Verklemmungsfreie Philosophen | 261 | ||
9.4 Beispielrealisierung in Java | 263 | ||
10 Literaturhinweise zum Teil II | 270 | ||
Teil III Datenstrukturen | 272 | ||
11 Abstrakte Datentypen | 274 | ||
11.1 Signaturen und Algebren | 275 | ||
11.2 Algebraische Spezi.kation | 277 | ||
11.2.1 Spezi.kationen und Modelle | 278 | ||
11.2.2 Termalgebra und Quotiententermalgebra | 279 | ||
11.2.3 Probleme mit initialer Semantik | 282 | ||
11.3 Beispiele für abstrakte Datentypen | 283 | ||
11.3.1 Der Kellerspeicher (Stack) | 284 | ||
11.3.2 Beispiel für Kellernutzung | 286 | ||
11.3.3 Die Warteschlange (Queue) | 290 | ||
11.4 Entwurf von Datentypen | 291 | ||
12 Klassen, Schnittstellen und Objekte in Java | 294 | ||
12.1 Grundzüge der Objektorientierung | 294 | ||
12.2 Klassen und Objekte in Java | 297 | ||
12.3 Vererbung | 302 | ||
12.4 Abstrakte Klassen und Schnittstellen | 309 | ||
12.5 Ausnahmen | 312 | ||
12.6 Umsetzung abstrakter Datentypen | 314 | ||
13 Grundlegende Datenstrukturen | 318 | ||
13.1 Stack und Queue als Datentypen | 318 | ||
13.1.1 Implementierung des Stacks | 322 | ||
13.1.2 Implementierung der Queue | 323 | ||
13.1.3 Bewertung der Implementierungen | 325 | ||
13.2 Verkettete Listen | 326 | ||
13.3 Doppelt verkettete Listen | 333 | ||
13.4 Das Iterator-Konzept | 338 | ||
13.5 Java Collection Framework | 341 | ||
13.6 J2SE 5.0 und Generics | 345 | ||
14 Bäume | 348 | ||
14.1 Bäume: Begriffe und Konzepte | 348 | ||
14.2 Binärer Baum: Datentyp und | 351 | ||
Basisalgorithmen | 351 | ||
14.2.1 Der Datentyp | 351 | ||
Binärer Baum | 351 | ||
14.2.2 Algorithmen zur Traversierung | 356 | ||
14.3 Suchbäume | 361 | ||
14.3.1 Suchen in Suchbäumen | 362 | ||
14.3.2 Einfügen und Löschen | 365 | ||
14.3.3 Komplexität der Operationen | 370 | ||
14.4 Ausgeglichene Bäume | 371 | ||
14.4.1 Rot-Schwarz-Bäume | 372 | ||
14.4.2 AVL-Bäume | 381 | ||
14.4.3 B-Bäume | 389 | ||
14.5 Digitale Bäume | 396 | ||
14.5.1 Tries | 396 | ||
14.5.2 Patricia-Bäume | 402 | ||
14.6 Praktische Nutzung von Bäumen | 403 | ||
14.6.1 Sortieren mit Bäumen: HeapSort | 404 | ||
14.6.2 Sets mit binären Suchbäumen | 410 | ||
15 Hashverfahren | 416 | ||
15.1 Grundprinzip des Hashens | 416 | ||
15.2 Grundlagen und Verfahren | 417 | ||
15.2.1 Hashfunktionen | 417 | ||
15.2.2 Behandlung von Kollisionen | 419 | ||
15.2.3 Aufwand beim Hashen | 423 | ||
Aufwand beim Hashen mit Sondieren | 424 | ||
15.2.4 Hashen in Java | 425 | ||
15.3 Dynamische Hashverfahren | 429 | ||
15.3.1 Grundideen für dynamische Hashverfahren | 430 | ||
Fünfte Idee: Ausgeglichener Trie als Feld gespeichert | 432 | ||
15.3.2 Erweiterbares Hashen | 433 | ||
15.3.3 Umsetzung des erweiterbaren Hashens | 435 | ||
Lektionen aus erweiterbarem Hashen | 439 | ||
16 Graphen | 440 | ||
16.1 Arten von Graphen | 440 | ||
16.1.1 Ungerichtete Graphen | 441 | ||
16.1.2 Gerichtete Graphen | 442 | ||
16.1.3 Gewichtete Graphen | 443 | ||
16.2 Realisierung von Graphen | 444 | ||
16.2.1 Knoten- und Kantenlisten | 444 | ||
16.2.2 Adjazenzmatrix | 445 | ||
16.2.3 Graphen als dynamische Datenstrukturen | 445 | ||
16.2.4 Transformationen zwischen Darstellungen | 446 | ||
16.2.5 Vergleich der Komplexität | 447 | ||
16.2.6 Eine Java-Klasse für Graphen | 447 | ||
16.3 Ausgewählte Graphenalgorithmen | 449 | ||
16.3.1 Breitendurchlauf | 450 | ||
16.3.2 Tiefendurchlauf | 454 | ||
16.3.3 Zyklenfreiheit und topologisches Sortieren | 458 | ||
16.4 Algorithmen auf gewichteten | 460 | ||
Graphen | 460 | ||
16.4.1 Kürzeste Wege | 461 | ||
16.4.2 Dijkstras Algorithmus | 462 | ||
16.4.3 Kürzeste Wege mit negativen | 466 | ||
Kantengewichten | 466 | ||
16.4.4 Maximaler Durch.uss | 469 | ||
16.4.5 Der Ford-Fulkerson-Algorithmus für die | 471 | ||
Bestimmung des maximalen Flusses | 471 | ||
16.5 Weitere Fragestellungen für Graphen | 475 | ||
Problem des Handlungsreisenden | 475 | ||
Planare Graphen | 476 | ||
Einfärben von Graphen | 477 | ||
17 Suchen in Texten | 478 | ||
17.1 Probleme der Worterkennung | 478 | ||
17.2 Knuth-Morris-Pratt | 480 | ||
17.3 Boyer-Moore | 484 | ||
17.4 Pattern Matching | 490 | ||
17.4.1 Reguläre Ausdrücke | 490 | ||
17.4.2 Endliche Automaten | 491 | ||
17.4.3 Java-Klassen für reguläre Ausdrücke | 497 | ||
18 Literaturhinweise zum Teil III | 500 | ||
Anhang | 502 | ||
A Quelltext der Klasse | 502 | ||
Abbildungsverzeichnis | 506 | ||
Tabellenverzeichnis | 512 | ||
Algorithmenverzeichnis | 514 | ||
Beispielverzeichnis | 516 | ||
Programmverzeichnis | 518 | ||
Literaturverzeichnis | 520 | ||
Index | 524 | ||
Mehr eBooks bei www.ciando.com | 0 |