Algorithmen und Datenstrukturen - Eine Einführung mit Java

von: Gunter Saake, Kai-Uwe Sattler

dpunkt, 2011

ISBN: 9783864910227

Sprache: Deutsch

552 Seiten, Download: 3638 KB

Format: EPUB, PDF, auch als Online-Lesen

geeignet für:

Apple iPod touch, iPhone und Android Smartphones

eBook anfordern

▸

Mehr zum Inhalt

Algorithmen und Datenstrukturen - Eine Einführung mit Java

	Vorwort	5
	Inhaltsverzeichnis	11
	I Grundlegende Konzepte	19
	1 Vorbemerkungen und Überblick	21
	1.1 Informatik, Algorithmen und Datenstrukturen	21
	1.2 Historischer Überblick: Algorithmen	23
	1.3 Historie von Programmiersprachen und Java	24
	1.4 Grundkonzepte der Programmierung in Java	27
	2 Algorithmische Grundkonzepte	33
	2.1 Intuitiver Algorithmusbegriff	33
	2.1.1 Beispiele für Algorithmen	33
	2.1.2 Bausteine für Algorithmen	37
	2.1.3 Pseudocode-Notation für Algorithmen	39
	2.1.4 Struktogramme	44
	2.1.5 Rekursion	44
	2.2 Sprachen und Grammatiken	47
	2.2.1 Begriffsbildung	48
	2.2.2 Reguläre Ausdrücke	49
	2.2.3 Backus-Naur-Form (BNF)	50
	2.3 Elementare Datentypen	52
	2.3.1 Datentypen als Algebren	52
	2.3.2 Signaturen von Datentypen	53
	2.3.3 Der Datentyp bool	54
	2.3.4 Der Datentyp integer	55
	2.3.5 Felder und Zeichenketten	56
	2.4 Terme	58
	2.4.1 Bildung von Termen	58
	2.4.2 Algorithmus zur Termauswertung	60
	2.5 Datentypen in Java	61
	2.5.1 Primitive Datentypen	61
	2.5.2 Referenzdatentypen	64
	2.5.3 Operatoren	67
	3 Algorithmenparadigmen	71
	3.1 Überblick über Algorithmenparadigmen	71
	3.2 Applikative Algorithmen	72
	3.2.1 Terme mit Unbestimmten	72
	3.2.2 Funktionsdefinitionen	73
	3.2.3 Auswertung von Funktionen	73
	3.2.4 Erweiterung der Funktionsdefinition	75
	3.2.5 Applikative Algorithmen	76
	3.2.6 Beispiele für applikative Algorithmen	77
	3.3 Imperative Algorithmen	85
	3.3.1 Grundlagen imperativer Algorithmen	85
	3.3.2 Komplexe Anweisungen	88
	3.3.3 Beispiele für imperative Algorithmen	91
	3.4 Das logische Paradigma	97
	3.4.1 Logik der Fakten und Regeln	97
	3.4.2 Deduktive Algorithmen	99
	3.5 Weitere Paradigmen	103
	3.5.1 Genetische Algorithmen	104
	3.5.2 Neuronale Netze	107
	3.6 Umsetzung in Java	110
	3.6.1 Ausdrücke und Anweisungen	111
	3.6.2 Methoden	118
	3.6.3 Applikative Algorithmen und Rekursion	124
	4 Literaturhinweise zum Teil I	131
	II Algorithmen	133
	5 Ausgewählte Algorithmen	135
	5.1 Suchen in sortierten Folgen	135
	5.1.1 Sequenzielle Suche	136
	5.1.2 Binäre Suche	138
	5.2 Sortieren	142
	5.2.1 Sortieren: Grundbegriffe	142
	5.2.2 Sortieren durch Einfügen	143
	5.2.3 Sortieren durch Selektion	145
	5.2.4 Sortieren durch Vertauschen: BubbleSort	147
	5.2.5 Sortieren durch Mischen: MergeSort	149
	5.2.6 QuickSort	153
	5.2.7 Sortierverfahren im Vergleich	157
	6 Formale Algorithmenmodelle	161
	6.1 Registermaschinen	161
	6.2 Abstrakte Maschinen	170
	6.3 Markov-Algorithmen	174
	6.4 Church'sche These	180
	6.5 Interpreter für formale Algorithmenmodelle in Java	182
	6.5.1 Java: Markov-Interpreter	182
	6.5.2 Registermaschine in Java	184
	7 Eigenschaften von Algorithmen	191
	7.1 Berechenbarkeit und Entscheidbarkeit	191
	7.1.1 Existenz nichtberechenbarer Funktionen	192
	7.1.2 Konkrete nichtberechenbare Funktionen	194
	7.1.3 Das Halteproblem	196
	7.1.4 Nichtentscheidbare Probleme	198
	7.1.5 Post'sches Korrespondenzproblem	199
	7.2 Korrektheit von Algorithmen	201
	7.2.1 Relative Korrektheit	201
	7.2.2 Korrektheit von imperativen Algorithmen	202
	7.2.3 Korrektheitsbeweise für Anweisungstypen	205
	7.2.4 Korrektheit imperativer Algorithmen an Beispielen	207
	7.2.5 Korrektheit applikativer Algorithmen	212
	7.3 Komplexität	214
	7.3.1 Motivierendes Beispiel	214
	7.3.2 Asymptotische Analyse	215
	7.3.3 Komplexitätsklassen	219
	7.3.4 Analyse von Algorithmen	222
	8 Entwurf von Algorithmen	225
	8.1 Entwurfsprinzipien	225
	8.1.1 Schrittweise Verfeinerung	225
	8.1.2 Einsatz von Algorithmenmustern	228
	8.1.3 Problemreduzierung durch Rekursion	228
	8.2 Algorithmenmuster: Greedy	229
	8.2.1 Greedy-Algorithmen am Beispiel	229
	8.2.2 Greedy: Optimales Kommunikationsnetz	231
	8.2.3 Verfeinerung der Suche nach billigster Kante	232
	8.3 Rekursion: Divide-and-conquer	234
	8.3.1 Das Prinzip „Teile und herrsche“	235
	8.3.2 Beispiel: Spielpläne für Turniere	236
	8.4 Rekursion: Backtracking	238
	8.4.1 Prinzip des Backtracking	239
	8.4.2 Beispiel: Das Acht-Damen-Problem	241
	8.5 Dynamische Programmierung	243
	8.5.1 Das Rucksackproblem	244
	8.5.2 Rekursive Lösung des Rucksackproblems	245
	8.5.3 Prinzip der dynamischen Programmierung	246
	9 Verteilte Berechnungen	249
	9.1 Kommunizierende Prozesse	249
	9.2 Modell der Petri-Netze	250
	9.2.1 Definition von Petri-Netzen	250
	9.2.2 Formalisierung von Petri-Netzen	254
	9.2.3 Das Beispiel der fünf Philosophen	256
	9.3 Programmieren nebenläufiger Abläufe	258
	9.3.1 Koordinierte Prozesse	259
	9.3.2 Programmieren mit Semaphoren	260
	9.3.3 Philosophenproblem mit Semaphoren	262
	9.3.4 Verklemmungsfreie Philosophen	264
	9.4 Beispielrealisierung in Java	266
	10 Literaturhinweise zum Teil II	273
	III Datenstrukturen	275
	11 Abstrakte Datentypen	277
	11.1 Signaturen und Algebren	278
	11.2 Algebraische Spezifikation	280
	11.2.1 Spezifikationen und Modelle	281
	11.2.2 Termalgebra und Quotiententermalgebra	282
	11.2.3 Probleme mit initialer Semantik	285
	11.3 Beispiele für abstrakte Datentypen	286
	11.3.1 Der Kellerspeicher (Stack)	287
	11.3.2 Beispiel für Kellernutzung	289
	11.3.3 Die Warteschlange (Queue)	293
	11.4 Entwurf von Datentypen	294
	12 Klassen, Schnittstellen und Objekte in Java	297
	12.1 Grundzüge der Objektorientierung	297
	12.2 Klassen und Objekte in Java	300
	12.3 Vererbung	305
	12.4 Abstrakte Klassen und Schnittstellen	312
	12.5 Ausnahmen	315
	12.6 Umsetzung abstrakter Datentypen	317
	13 Grundlegende Datenstrukturen	323
	13.1 Stack und Queue als Datentypen	323
	13.1.1 Implementierung des Stacks	327
	13.1.2 Implementierung der Queue	328
	13.1.3 Bewertung der Implementierungen	330
	13.2 Verkettete Listen	331
	13.3 Doppelt verkettete Listen	338
	13.4 Das Iterator-Konzept	343
	13.5 Java Collection Framework	346
	13.6 J2SE 5.0 und Generics	350
	14 Bäume	353
	14.1 Bäume: Begriffe und Konzepte	353
	14.2 Binärer Baum: Datentyp und Basisalgorithmen	356
	14.2.1 Der Datentyp „Binärer Baum“	356
	14.2.2 Algorithmen zur Traversierung	361
	14.3 Suchbäume	366
	14.3.1 Suchen in Suchbäumen	367
	14.3.2 Einfügen und Löschen	370
	14.3.3 Komplexität der Operationen	375
	14.4 Ausgeglichene Bäume	376
	14.4.1 Rot-Schwarz-Bäume	377
	14.4.2 AVL-Bäume	386
	14.4.3 B-Bäume	394
	14.5 Digitale Bäume	407
	14.5.1 Tries	408
	14.5.2 Patricia-Bäume	414
	14.6 Praktische Nutzung von Bäumen	415
	14.6.1 Sortieren mit Bäumen: HeapSort	415
	14.6.2 Sets mit binären Suchbäumen	421
	15 Hashverfahren	427
	15.1 Grundprinzip des Hashens	427
	15.2 Grundlagen und Verfahren	428
	15.2.1 Hashfunktionen	428
	15.2.2 Behandlung von Kollisionen	430
	15.2.3 Aufwand beim Hashen	434
	15.2.4 Hashen in Java	436
	15.3 Dynamische Hashverfahren	440
	15.3.1 Grundideen für dynamische Hashverfahren	441
	15.3.2 Erweiterbares Hashen	444
	15.3.3 Umsetzung des erweiterbaren Hashens	446
	16 Graphen	451
	16.1 Arten von Graphen	451
	16.1.1 Ungerichtete Graphen	452
	16.1.2 Gerichtete Graphen	453
	16.1.3 Gewichtete Graphen	454
	16.2 Realisierung von Graphen	455
	16.2.1 Knoten- und Kantenlisten	455
	16.2.2 Adjazenzmatrix	456
	16.2.3 Graphen als dynamische Datenstrukturen	456
	16.2.4 Transformationen zwischen Darstellungen	457
	16.2.5 Vergleich der Komplexität	458
	16.2.6 Eine Java-Klasse für Graphen	458
	16.3 Ausgewählte Graphenalgorithmen	461
	16.3.1 Breitendurchlauf	461
	16.3.2 Tiefendurchlauf	465
	16.3.3 Zyklenfreiheit und topologisches Sortieren	469
	16.4 Algorithmen auf gewichteten Graphen	472
	16.4.1 Kürzeste Wege	473
	16.4.2 Dijkstras Algorithmus	474
	16.4.3 A*-Algorithmus	477
	16.4.4 Kürzeste Wege mit negativen Kantengewichten	484
	16.4.5 Maximaler Durchfluss	487
	16.4.6 Der Ford-Fulkerson-Algorithmus	489
	16.5 Weitere Fragestellungen für Graphen	493
	17 Suchen in Texten	497
	17.1 Probleme der Worterkennung	497
	17.2 Knuth-Morris-Pratt	499
	17.3 Boyer-Moore	503
	17.4 Pattern Matching	509
	17.4.1 Reguläre Ausdrücke	509
	17.4.2 Endliche Automaten	510
	17.4.3 Java-Klassen für reguläre Ausdrücke	516
	17.4.4 Ähnlichkeit von Zeichenketten: Die Levenshtein-Distanz	517
	18 Literaturhinweise zum Teil III	521
	A Quelltext der Klasse IOUtils	523
	Abbildungsverzeichnis	527
	Tabellenverzeichnis	533
	Algorithmenverzeichnis	535
	Beispielverzeichnis	537
	Programmverzeichnis	539
	Literaturverzeichnis	541
	Index	545

Algorithmen und Datenstrukturen - Eine Einführung mit Java

von: Gunter Saake, Kai-Uwe Sattler

Algorithmen und Datenstrukturen - Eine Einführung mit Java

Kategorien

eBooks