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

geeignet für:

eBook anfordern

▸

Mehr zum Inhalt

Algorithmen und Datenstrukturen - Eine Einführung mit Java

	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

Algorithmen und Datenstrukturen - Eine Einführung mit Java

von: Gunter Saake, Kai-Uwe Sattler

Algorithmen und Datenstrukturen - Eine Einführung mit Java

Kategorien

eBooks