Algorithmen: Algorithmen und Datenstrukturen

Algorithmen
Inhaltsverzeichnis
	Vorwort 11
		Besondere Merkmale 11
		Die Website zum Buch 13
		Das Buch als Unterrichtsmittel 14
		Kontext 14
		Danksagung 15
	Vorwort zur deutschen Ausgabe 16
		Webinhalte zum vorliegenden Buch 17
	Kapitel 1 -
Grundlagen 19
		Algorithmen 20
		Zusammenfassung der Themen 23
		1.1 Das grundlegende Programmiermodell 25
			1.1.1 Grundlegende Struktur eines Java-Programms 27
			1.1.2 Primitive Datentypen und Ausdrücke 28
			1.1.3 Anweisungen 31
			1.1.4 Kurzschreibweisen 34
			1.1.5 Arrays 36
			1.1.6 Statische Methoden 39
			1.1.7 APIs 47
			1.1.8 Strings 52
			1.1.9 Ein- und Ausgabe 54
			1.1.10 Binäre Suche 65
			1.1.11 Ausblick 69
		1.2 Datenabstraktion 81
			1.2.1 Abstrakte Datentypen 82
			1.2.2 Beispiele abstrakter Datentypen 92
			1.2.3 Abstrakte Datentypen implementieren 104
			1.2.4 Weitere Implementierungen abstrakter Datentypen 110
			1.2.5 Datentypdesign 116
		1.3 Multimengen, Warteschlangen und Stapel 139
			1.3.1 APIs 140
			1.3.2 Collections implementieren 151
			1.3.3 Verkettete Listen 162
			1.3.4 Zusammenfassung 176
		1.4 Analyse der Algorithmen 191
			1.4.1 Die wissenschaftliche Methode 191
			1.4.2 Beobachtungen 192
			1.4.3 Mathematische Modelle 198
			1.4.4 Klassifikationen der Wachstumsordnung 206
			1.4.5 Schnellere Algorithmen entwerfen 209
			1.4.6 Experimente zum Verdopplungsverhältnis 212
			1.4.7 Fallstricke 216
			1.4.8 Die Abhängigkeit von Eingaben reduzieren 218
			1.4.9 Speicherbedarf 221
			1.4.10 Ausblick 227
		1.5 Fallstudie Union-Find 238
			1.5.1 Verwaltung von Zusammenhangskomponenten 238
			1.5.2 Implementierungen 245
			1.5.3 Ausblick 257
	Kapitel 2 -
Sortieren 265
		2.1 Elementare Sortierverfahren 267
			2.1.1 Spielregeln 267
			2.1.2 Selectionsort 272
			2.1.3 Insertionsort 274
			2.1.4 Sortieralgorithmen grafisch darstellen 276
			2.1.5 Zwei Sortieralgorithmen vergleichen 277
			2.1.6 Shellsort 281
		2.2 Mergesort 294
			2.2.1 Abstraktes In-Place-Mergen 294
			2.2.2 Top-Down-Mergesort 296
			2.2.3 Bottom-Up-Mergesort 301
			2.2.4 Die Komplexität des Sortierens 304
		2.3 Quicksort 313
			2.3.1 Der grundlegende Algorithmus 313
			2.3.2 Laufzeitverhalten 318
			2.3.3 Algorithmische Verbesserungen 320
		2.4 Vorrangwarteschlangen 333
			2.4.1 API 334
			2.4.2 Einfache Implementierungen 336
			2.4.3 Heap-Definitionen 339
			2.4.4 Algorithmen für Heaps 341
			2.4.5 Heapsort 350
		2.5 Anwendungen 363
			2.5.1 Verschiedene Datentypen sortieren 364
			2.5.2 Welchen Sortieralgorithmus soll ich verwenden? 369
			2.5.3 Reduktionen 372
			2.5.4 Sortieranwendungen im kurzen Überblick 375
	Kapitel 3 -
Suchen 387
		3.1 Symboltabellen 389
			3.1.1 API 390
			3.1.2 Geordnete Symboltabellen 393
			3.1.3 Beispielclients 398
			3.1.4 Sequenzielle Suche in einer ungeordneten verketteten Liste 402
			3.1.5 Binäre Suche in einem geordneten Array 405
			3.1.6 Analyse der binären Suche 411
			3.1.7 Ausblick 413
		3.2 Binäre Suchbäume 424
			3.2.1 Grundlegende Implementierung 425
			3.2.2 Analyse 432
			3.2.3 Ordnungsbasierte Methoden und Löschen 435
		3.3 Balancierte Suchbäume 453
			3.3.1 2-3-Suchbäume 453
			3.3.2 Rot-Schwarz-Bäume 461
			3.3.3 Implementierung 470
			3.3.4 Löschen 473
			3.3.5 Eigenschaften von Rot-Schwarz-Bäumen 475
		3.4 Hashtabellen 489
			3.4.1 Hashfunktionen 490
			3.4.2 Hashing mit Verkettung 496
			3.4.3 Hashing mit linearer Sondierung 501
			3.4.4 Größenanpassung von Arrays 506
			3.4.5 Speicher 509
		3.5 Anwendungen 519
			3.5.1 Welche Symboltabellen-Implementierung soll ich verwenden? 519
			3.5.2 Mengen-APIs (Set) 522
			3.5.3 Wörterbuch-Anwendungen 526
			3.5.4 Indizierungsclients 531
			3.5.5 Dünn besetzte Vektoren 537
	Kapitel 4 -
Graphen 549
		4.1 Ungerichtete Graphen 553
			4.1.1 Glossar 554
			4.1.2 Datentyp für ungerichtete Graphen 557
			4.1.3 Tiefensuche 566
			4.1.4 Pfadsuche 572
			4.1.5 Breitensuche 577
			4.1.6 Zusammenhangskomponenten 583
			4.1.7 Symbolgraphen 589
			4.1.8 Zusammenfassung 597
		4.2 Gerichtete Graphen 607
			4.2.1 Glossar 607
			4.2.2 Datentyp für Digraphen 609
			4.2.3 Erreichbarkeit in Digraphen 612
			4.2.4 Zyklen und azyklische Digraphen 617
			4.2.5 Starker Zusammenhang in Digraphen 628
			4.2.6 Zusammenfassung 638
		4.3 Minimale Spannbäume 646
			4.3.1 Zugrunde liegende Prinzipien 648
			4.3.2 Datentyp eines kantengewichteten Graphen 651
			4.3.3 API und Testclient für minimale Spannbäume 655
			4.3.4 Der Algorithmus von Prim 658
			4.3.5 Eager-Version des Prim-Algorithmus 663
			4.3.6 Der Algorithmus von Kruskal 668
			4.3.7 Ausblick 671
		4.4 Kürzeste Pfade 680
			4.4.1 Eigenschaften der kürzeste Pfade 682
			4.4.2 Datentypen für kantengewichtete Digraphen 684
			4.4.3 Theoretische Grundlagen für Kürzeste-Pfade-Algorithmen 692
			4.4.4 Algorithmus von Dijkstra 694
			4.4.5 Azyklische kantengewichtete Digraphen 701
			4.4.6 Kürzeste Pfade in allgemeinen kantengewichteten Digraphen 711
			4.4.7 Ausblick 726
	Kapitel 5 -
Strings 737
		5.1 Stringsortierverfahren 745
			5.1.1 Schlüsselindiziertes Zählen 746
			5.1.2 LSD-Sortierverfahren 749
			5.1.3 MSD-Sortierverfahren 752
			5.1.4 3-Wege-Quicksort für Strings 762
			5.1.5 Welchen Stringsortieralgorithmus soll ich verwenden? 767
		5.2 Tries 773
			5.2.1 Tries 775
			5.2.2 Eigenschaften von Tries 785
			5.2.3 Ternäre Suchtries 789
			5.2.4 TST-Eigenschaften 792
			5.2.5 Welche Symboltabellen-Implementierung soll ich für Strings verwenden? 795
		5.3 Teilstringsuche 800
			5.3.1 Ein kurzer geschichtlicher Abriss 800
			5.3.2 Brute-Force-Teilstringsuche 801
			5.3.3 Teilstringsuche nach Knuth-Morris-Pratt 804
			5.3.4 Teilstringsuche nach Boyer-Moore 812
			5.3.5 Fingerprint-Suche nach Rabin-Karp 817
			5.3.6 Zusammenfassung 822
		5.4 Reguläre Ausdrücke 829
			5.4.1 Muster mit regulären Ausdrücken 830
			5.4.2 Abkürzungen 832
			5.4.3 Reguläre Ausdrücke in Anwendungen 834
			5.4.4 Nichtdeterministische endliche Automaten 836
			5.4.5 Simulation eines NEA 839
			5.4.6 Konstruktion eines NEA für einen regulären Ausdruck 842
		5.5 Datenkomprimierung 851
			5.5.1 Spielregeln 852
			5.5.2 Binärdaten lesen und schreiben 853
			5.5.3 Beschränkungen 857
			5.5.4 Aufwärmübung: Genomik 860
			5.5.5 Lauflängencodierung 863
			5.5.6 Huffman-Komprimierung 868
			5.5.7 LZW-Komprimierung 882
	Kapitel 6 -
Im Kontext 895
		Ereignisgesteuerte Simulation 899
		B-Bäume 909
		Suffixarrays 918
		Netzwerkflussalgorithmen 928
		Reduktion 946
		Nicht effizient lösbare Probleme 953
		Allgemeine Übungen zu der Kollisionssimulation 966
		Allgemeine Übungen zu B-Bäumen 968
		Allgemeine Übungen zu Suffixarrays 969
		Allgemeine Übungen zu Max-Fluss 971
		Allgemeine Übungen zu Reduktionen und scheinbarer Unlösbarkeit 973
	Register 975
Vorwort
	Besondere Merkmale
	Die Website zum Buch
	Das Buch als Unterrichtsmittel
	Kontext
	Danksagung
Vorwort zur deutschen Ausgabe
	Webinhalte zum vorliegenden Buch
Kapitel 1 -
Grundlagen
	Algorithmen
	Zusammenfassung der Themen
	1.1 Das grundlegende Programmiermodell
		1.1.1 Grundlegende Struktur eines Java-Programms
		1.1.2 Primitive Datentypen und Ausdrücke
		1.1.3 Anweisungen
		1.1.4 Kurzschreibweisen
		1.1.5 Arrays
		1.1.6 Statische Methoden
		1.1.7 APIs
		1.1.8 Strings
		1.1.9 Ein- und Ausgabe
		1.1.10 Binäre Suche
		1.1.11 Ausblick
	1.2 Datenabstraktion
		1.2.1 Abstrakte Datentypen
		1.2.2 Beispiele abstrakter Datentypen
		1.2.3 Abstrakte Datentypen implementieren
		1.2.4 Weitere Implementierungen abstrakter Datentypen
		1.2.5 Datentypdesign
	1.3 Multimengen, Warteschlangen und Stapel
		1.3.1 APIs
		1.3.2 Collections implementieren
		1.3.3 Verkettete Listen
		1.3.4 Zusammenfassung
	1.4 Analyse der Algorithmen
		1.4.1 Die wissenschaftliche Methode
		1.4.2 Beobachtungen
		1.4.3 Mathematische Modelle
		1.4.4 Klassifikationen der Wachstumsordnung
		1.4.5 Schnellere Algorithmen entwerfen
		1.4.6 Experimente zum Verdopplungsverhältnis
		1.4.7 Fallstricke
		1.4.8 Die Abhängigkeit von Eingaben reduzieren
		1.4.9 Speicherbedarf
		1.4.10 Ausblick
	1.5 Fallstudie Union-Find
		1.5.1 Verwaltung von Zusammenhangskomponenten
		1.5.2 Implementierungen
		1.5.3 Ausblick
Kapitel 2 -
Sortieren
	2.1 Elementare Sortierverfahren
		2.1.1 Spielregeln
		2.1.2 Selectionsort
		2.1.3 Insertionsort
		2.1.4 Sortieralgorithmen grafisch darstellen
		2.1.5 Zwei Sortieralgorithmen vergleichen
		2.1.6 Shellsort
	2.2 Mergesort
		2.2.1 Abstraktes In-Place-Mergen
		2.2.2 Top-Down-Mergesort
		2.2.3 Bottom-Up-Mergesort
		2.2.4 Die Komplexität des Sortierens
	2.3 Quicksort
		2.3.1 Der grundlegende Algorithmus
		2.3.2 Laufzeitverhalten
		2.3.3 Algorithmische Verbesserungen
	2.4 Vorrangwarteschlangen
		2.4.1 API
		2.4.2 Einfache Implementierungen
		2.4.3 Heap-Definitionen
		2.4.4 Algorithmen für Heaps
		2.4.5 Heapsort
	2.5 Anwendungen
		2.5.1 Verschiedene Datentypen sortieren
		2.5.2 Welchen Sortieralgorithmus soll ich verwenden?
		2.5.3 Reduktionen
		2.5.4 Sortieranwendungen im kurzen Überblick
Kapitel 3 -
Suchen
	3.1 Symboltabellen
		3.1.1 API
		3.1.2 Geordnete Symboltabellen
		3.1.3 Beispielclients
		3.1.4 Sequenzielle Suche in einer ungeordneten verketteten Liste
		3.1.5 Binäre Suche in einem geordneten Array
		3.1.6 Analyse der binären Suche
		3.1.7 Ausblick
	3.2 Binäre Suchbäume
		3.2.1 Grundlegende Implementierung
		3.2.2 Analyse
		3.2.3 Ordnungsbasierte Methoden und Löschen
	3.3 Balancierte Suchbäume
		3.3.1 2-3-Suchbäume
		3.3.2 Rot-Schwarz-Bäume
		3.3.3 Implementierung
		3.3.4 Löschen
		3.3.5 Eigenschaften von Rot-Schwarz-Bäumen
	3.4 Hashtabellen
		3.4.1 Hashfunktionen
		3.4.2 Hashing mit Verkettung
		3.4.3 Hashing mit linearer Sondierung
		3.4.4 Größenanpassung von Arrays
		3.4.5 Speicher
	3.5 Anwendungen
		3.5.1 Welche Symboltabellen-Implementierung soll ich verwenden?
		3.5.2 Mengen-APIs (Set)
		3.5.3 Wörterbuch-Anwendungen
		3.5.4 Indizierungsclients
		3.5.5 Dünn besetzte Vektoren
Kapitel 4 -
Graphen
	4.1 Ungerichtete Graphen
		4.1.1 Glossar
		4.1.2 Datentyp für ungerichtete Graphen
		4.1.3 Tiefensuche
		4.1.4 Pfadsuche
		4.1.5 Breitensuche
		4.1.6 Zusammenhangskomponenten
		4.1.7 Symbolgraphen
		4.1.8 Zusammenfassung
	4.2 Gerichtete Graphen
		4.2.1 Glossar
		4.2.2 Datentyp für Digraphen
		4.2.3 Erreichbarkeit in Digraphen
		4.2.4 Zyklen und azyklische Digraphen
		4.2.5 Starker Zusammenhang in Digraphen
		4.2.6 Zusammenfassung
	4.3 Minimale Spannbäume
		4.3.1 Zugrunde liegende Prinzipien
		4.3.2 Datentyp eines kantengewichteten Graphen
		4.3.3 API und Testclient für minimale Spannbäume
		4.3.4 Der Algorithmus von Prim
		4.3.5 Eager-Version des Prim-Algorithmus
		4.3.6 Der Algorithmus von Kruskal
		4.3.7 Ausblick
	4.4 Kürzeste Pfade
		4.4.1 Eigenschaften der kürzeste Pfade
		4.4.2 Datentypen für kantengewichtete Digraphen
		4.4.3 Theoretische Grundlagen für Kürzeste-Pfade-Algorithmen
		4.4.4 Algorithmus von Dijkstra
		4.4.5 Azyklische kantengewichtete Digraphen
		4.4.6 Kürzeste Pfade in allgemeinen kantengewichteten Digraphen
		4.4.7 Ausblick
Kapitel 5 -
Strings
	Spielregeln
	Alphabete
	5.1 Stringsortierverfahren
		5.1.1 Schlüsselindiziertes Zählen
		5.1.2 LSD-Sortierverfahren
		5.1.3 MSD-Sortierverfahren
		5.1.4 3-Wege-Quicksort für Strings
		5.1.5 Welchen Stringsortieralgorithmus soll ich verwenden?
	5.2 Tries
		5.2.1 Tries
		5.2.2 Eigenschaften von Tries
		5.2.3 Ternäre Suchtries
		5.2.4 TST-Eigenschaften
		5.2.5 Welche Symboltabellen-Implementierung soll ich für Strings verwenden?
	5.3 Teilstringsuche
		5.3.1 Ein kurzer geschichtlicher Abriss
		5.3.2 Brute-Force-Teilstringsuche
		5.3.3 Teilstringsuche nach Knuth-Morris-Pratt
		5.3.4 Teilstringsuche nach Boyer-Moore
		5.3.5 Fingerprint-Suche nach Rabin-Karp
		5.3.6 Zusammenfassung
	5.4 Reguläre Ausdrücke
		5.4.1 Muster mit regulären Ausdrücken
		5.4.2 Abkürzungen
		5.4.3 Reguläre Ausdrücke in Anwendungen
		5.4.4 Nichtdeterministische endliche Automaten
		5.4.5 Simulation eines NEA
		5.4.6 Konstruktion eines NEA für einen regulären Ausdruck
	5.5 Datenkomprimierung
		5.5.1 Spielregeln
		5.5.2 Binärdaten lesen und schreiben
		5.5.3 Beschränkungen
		5.5.4 Aufwärmübung: Genomik
		5.5.5 Lauflängencodierung
		5.5.6 Huffman-Komprimierung
		5.5.7 LZW-Komprimierung
Im Kontext
	Ereignisgesteuerte Simulation
	B-Bäume
	Suffixarrays
	Netzwerkflussalgorithmen
	Reduktion
	Nicht effizient lösbare Probleme
	Allgemeine Übungen zu der Kollisionssimulation
	Allgemeine Übungen zu B-Bäumen
	Allgemeine Übungen zu Suffixarrays
	Allgemeine Übungen zu Max-Fluss
	Allgemeine Übungen zu Reduktionen und scheinbarer Unlösbarkeit
Register
	Numerics
		2-3-Suchbäume 453
			globale Eigenschaften 459
			lokale Transformationen 458
		2-Bit-Codedekomprimierung 861
		2-Bit-Codekomprimierung 860
		2-Summen-Problem 209
		3-Summen-Problem 210
		3-Wege-Quicksort für Strings 762
			Performance 766
			Randomisierung 765
	A
		Ablaufplanung
			Methode des kritischen Pfades 708
			mit Deadlines 710
			parallele Aufgaben 705
			Vorrangbedingungen 617
		Abrundungsfunktion 395
		Abstrakte Datentypen 82
			Accumulator 114
			Beispiele 92, 110
			Client-Code 83
			Collections 140
			Date 110
			Design 116
			Ein-/Ausgabe 101
			geerbte Methoden 83
			Generics 141
			grafischer Akkumulator 114
			Gültigkeitsbereich 107
			implementieren 104
			Instanzmethoden 106
			Instanzvariablen 105
			Konstruktoren 105
			Objekte 84
			Objekte als Argumente 89
			Objekte als Rückgabewerte 89
			Objekte erzeugen 85
			Objekte verwenden 87
			Referenztypen 84
			String 99
			Zuweisungen 87
		Adjazenzlisten 559, 560
		Adjazenzmatrix 559
		Adjazenzmengen 563
		ADT siehe abstrakte Datentypen
		Algorithmen
			3-Wege-Quicksort für Strings 764
			Analyse 191
			Bottom-Up-Mergesort 303
			Boyer-Moore-Teilstringsuche 816
			Breitensuche 580
			der augmentierenden Pfade 934
			Dijkstra 150, 378
			euklidischer 21
			Fingerprint-Suche 821
			Ford-Fulkerson 934
			generische 694
			Greedy- 650
			Heaps 341, 345
			Heapsort 352
			Huffman 379
			Huffman-Komprimierung 879
			Insertionsort 275
			Johnson 734
			KMP-Teilstringsuche 811
			Kruskal 379
			Las-Vegas 820
			LSD-Sortierverfahren 750
			LZW-Dekomprimierung 888
			LZW-Komprimierung 885
			Monte-Carlo 820
			MSD-Sortierverfahren 755
			Musterabgleich 845
			optimale 255
			Prim 378
			Quick-Find 245
			Quicksort 314
			Quick-Union 247
			Rabin-Karp-Teilstringsuche 821
			randomisierte 219
			schnellere entwerfen 209
			Selectionsort 273
			Shellsort 283
			Suche in B-Bäumen 916
			Suffixarray-Implementierung 926
			Tiefensuche 567
			Top-Down-Mergesort 298
			Verbesserungen 320
			Vorrangwarteschlange 345
		Algorithmendesign
			Reduktionen 372
		Aliasing 38
		Allokation
			sequenzielle 176
			verkettete 176
		Alphabete 741
			API 741
			spezifizierte 754
			Standard- 742
			Zahlen 744
		Analysen
			Algorithmen 191
			Beobachtungen 192
			mathematische Modelle 198
			Messdaten 196
			Problemgröße 192
			wissenschaftliche Methoden 191
		Anweisungen 31
			Aufrufe 32
			bedingte 33
			Block- 33
			break 34
			continue 34
			Deklarationen 32
			foreach 142
			Rückgabewerte 32
			Schleifen 33
			Zuweisungen 32
		API
			Accumulator 113
			Alphabete 741
			B-Baum 915
			Date 110
			Digraphen 609
			entwerfen 117
			Flussnetzwerk 933
			für abstrakten Datentyp 82
			für starke Komponenten 631
			für ungerichtete Graphen 557
			kantengewichtete Digraphen 684
			kantengewichtete Graphen 651
			Math 47
			Mengen 522
			minimale Spannbäume 656
			Particle 903
			Pfadsuche 572
			SET 522
			spezifizieren 108
			StdDraw 62
			String 100
			Suffixarrays 922
			Symbolgraphen 590
			Symboltabelle 390
			Union-Find 241
			Zusammenhangskomponenten 583
		Arrays 36
			Aliasing 38
			ausgefranste 38
			Duplikate 372
			eindimensionale 36
			erzeugen 36
			geordnete 405
			Größenanpassung 155, 346, 506
			initialisieren 36
			Iteration 158
			Objekte 90
			partitionieren 313
			sortieren 267
			Speicherbedarf 224
			traversieren 167
			Überlauf 156
			unveränderliche Schlüssel 346
			verwenden 37
			von Objekten 90
			Zeichen 740
			zeichenindizierte 743
			zweidimensionale 38
		ASCII-Codierung 856
		Assertionen 129
		Aufrufe 32
		Aufrundungsfunktion 395
		Ausdrücke 28, 30
			arithmetische 147
			boolesche 31
		Ausgabe 54
			binäre 853
			formatierte 56
			Standardausgabe 55
		Ausgangsgrad 608
		Ausgefranste Arrays 38
		Ausnahmen 128
		Autoboxing 141
		Automaten
			deterministische endliche 806
			nichtdeterministische endliche 836
		Autounboxing 142
		AVL-Suchbäume 484
		Azyklische Graphen 555
		Azyklische kantengewichtete Digraphen 701
			kürzeste Pfade 701
			Kürzeste-Pfade-Problem 711
			längste Pfade 704
	B
		B*-Bäume 968
		Bad-Character-Heuristik 813
		Bag-Implementierung 174
		Bags 143
		Balancierte Suchbäume 453
			Eins-zu-eins-Repräsentation 463
			Farbrepräsentation 463
			Implementierung 470
			Löschen 473
			Rotationen 464
		Bäume
			Definition 250
			der kürzesten Pfade 683
			Heap-geordnete 339
		B-Bäume 909
			API 915
			Konventionen 911
			Kostenmodell 910
			Performance 915
			Repräsentation 914
			Speicherbedarf 917
			Suchen und Einfügen 912
		Bedingte Anweisungen 33
		Befehlszeilenargumente 53
		Bellman-Ford-Algorithmus 715
			Ablaufprotokoll 716
			Arbitrage-Beispiel 723
			Erkennung negativer Zyklen 721
			Implementierung 717
			negative Gewichte 720
		Benachbarte Knoten 554
		BFS (breadth-first search) siehe Breitensuche
		Bibliotheken
			buchspezifische 48
			eigene 50
			externe 45
			Java 48
		Binäre Ein-/Ausgabe 853
		Binäre Heaps 339, 340
			Definition 340
			Repräsentation 340
		Binäre Suchbäume 424
			Analyse 432
			Analyse ordnungsbasierter Operationen 441
			auf-/abrunden 435
			Auswahl 436
			AVL 484
			Bereichsabfragen 441
			Einfügen 429
			Floor/Ceiling 435
			löschen 439
			Minimum/Maximum 435
			ordnungsbasierte Methoden 435
			Rang ermitteln 437
			Rekursion 430
			Repräsentation 425
			Suchen 426
		Binäre Suche 65, 408
			Analyse 411
			Entwicklungsclient 66
			im Array 65
			Kosten 412
			Laufzeitverhalten 68
			Positivlisten 66
			Weiße Listen 66
		Bipartite Graphen 556
		Blockanweisungen 33
		Boltzmann-Konstante 967
		Boruvka, O. 672
		Bottom-Up
			Heaps 342
			Mergesort 301, 303
		Boyer-Moore-Teilstringsuche 812, 813
		break-Anweisungen 34
		Breitensuche 577
			Ablaufprotokoll 578
			Algorithmus 580
			Kürzeste-Pfade-Problem 577
			Laufzeitverhalten 581
		BST siehe Binäre Suchbäume
		Burrows-Wheeler-Transformation 970
	C
		Callback-Mechanismus 364
		Chazelle, B. 672
		Church-Turing-These 954
		Code Refactoring 919
		Collections
			Arrays 155
			Generics 153
			Iteration 158
			Iterator 159
			iterierbare 142
			Stapel fester Kapazität 151
			verkettete Listen 162
		Comparator (Schnittstelle) 366
		continue-Anweisungen 34
		Cook-Levin-Theorem 963
		CPM-Methode 708
	D
		Daten
			komprimieren 851
			Pipelining 59
			umleiten 59
		Datenabstraktion 81
		Datenkomprimierung 851
			2-Bit-Codedekomprimierung 861
			2-Bit-Codekomprimierung 860
			ASCII-Codierung 856
			Beschränkungen 857
			Binärdaten 853
			binäre Speicherauszüge 855
			Genomik 860
			Huffman 868
			Komprimierungsrate 852
			Lauflängencodierung 863
			LZW 883
			Modell 852
			Unentscheidbarkeit 859
			universelle 857
			verlustlose 852
		Datenstrukturen
			Adjazenzlisten 560
			Adjazenzmatrix 559
			B-Bäume 910
			Tries 775
		Datentypdesign 116
		Datentypen
			abstrakte 82
			APIs entwerfen 117
			Deque 186
			Digraphen 609
			kantengewichtete Digraphen 684
			kantengewichtete Graphen 651
			Kapselung 116
			Nachbedingungen 129
			Nebeneffekte 129
			primitive 28, 371
			sortieren 371
			Steque 186
			Stringumwandlung 122
			Umwandlung 30
			ungerichtete Graphen 557
			unveränderliche 126
			verschiedene sortieren 364
			Vorbedingungen 129
			Vorrangwarteschlange 334
			Wrapper-Klassen 123
			Wrappertypen 123
		DEA
			Haltezustand 807
			Konstruktion 808
			Nichtübereinstimmungsübergang 806
			Simulation 806
			Übereinstimmungsübergang 806
		Deklarationen 32
			Gültigkeitsbereich 32
			mit Initialisierung 34
		Deque 186
		Design by Contract 128
		Deterministische endliche Automaten siehe DEA
		DFS (depth-first search) siehe Tiefensuche
		Dichte Graphen 556
		Digraphen
			Anfangsknoten 608
			Aufbau 608
			Ausgangsgrad 608
			azyklische 617, 619
			Datentyp 609
			einfacher Zyklus 608
			Eingabeformat 610
			Eingangsgrad 608
			Endknoten 608
			Erreichbarkeit 612, 636
			euklidische 644
			gerichteter Pfad 608
			gerichteter Zyklus 608
			Gitter- 644
			Hamilton-Pfad 643
			Kosaraju-Algorithmus 631
			letzter gemeinsamer Vorgänger 642
			Pfad mit kürzestem Nachfolgerabstand 642
			Pfadsuche 616
			Postorder-Knotenreihenfolge 622
			Preorder-Knotenreihenfolge 622
			Repräsentation 610
			Speicherbereinigung 615
			starke Komponenten 629
			starke Zusammenhangs- komponenten 629
			starker Zusammenhang 628
			symbolische Namen 610
			topologische Ordnung 622
			transitive Hülle 636
			umgekehrte Postorder-Knotenreihenfolge 622
			Umkehrung 610
			Zykluserkennung 619
		Dijkstra, Edsgar 148
		Dijkstra-Algorithmus 378, 694
			Ablaufprotokoll 696
			Datenstrukturen 695
			Varianten 698
		d-näre Heaps 346
		Doppelte Sondierung 516
		Dünne Graphen 556
		Duplikate 372
	E
		Eager deletion 391
		Eindimensionale Arrays 36
		Eingabe 54
			binäre 853
		Eingabemodelle 218
		Eingangsgrad 608
		Entropie-optimales Sortieren 321
		Entscheidnungsprobleme 957
		Entwicklungsclient 66
		Entwurfsmuster 564
		Ereignisgesteuerte Simulation 899, 900
			Code 905
			Ereignisse 904
			Performance 909
		Erfüllbarkeitsprobleme 956
		Erreichbarkeit 612, 636
		Euklidische Graphen 604
		Euklidischer Algorithmus 21
		Eulersche Zyklen 604
		Exceptions siehe Ausnahmen
		Externe Bibliotheken 45
	F
		Fail-Fast-Iterator 180
		FBC siehe fragile Basisklasse
		FIFO-Warteschlangen 144
		Fingerprint-Suche 817
			Grundkonzept 817
			Hashfunktion 818
			Monte-Carlo-Korrektur 820
		Ford-Fulkerson-Algorithmus 934
		foreach-Anweisungen 142
		Formatierte Ausgabe 56
		for-Schleifen 35
		Fragile Basisklasse 133
		Fredman, M. L. 671
		Funktionsabstraktion 27
	G
		Geerbte Methoden 83
		Generics 141
		Gerichtete Graphen siehe Digraphen
		Gewichtetes Quick-Union 251
			Ablaufprotokoll 253
			Analyse 251
			mit Pfadkompression 255
		Gittergraphen 605
		Graphenverarbeitung
			Bellman-Ford-Algorithmus 715, 716
			Breitensuche 577
			Dijkstra-Algorithmus 694
			Entwurfsmuster 564
			Erreichbarkeit 612
			Komponenten 583
			Kosaraju-Algorithmus 631
			kritischer Pfad 706
			Kruskal-Algorithmus 668
			kürzeste Pfade 680
			längste Pfade 704
			minimale Spannbäume 646
			Pfadsuche 572
			Prim-Algorithmus 658
			Schnitte 649
			starke Komponenten 629
			starke Zusammenhangs- komponenten 629
			Symbolgraphen 589
			Tiefensuche 566
			transitive Hülle 636
			ungerichtete Graphen 553
			Union-Find 587
		Greedy-Algorithmus 650
		GREP 847
		Gültigkeitsbereich 32, 107
	H
		Hamilton'sche Zyklen 604
		Hamiltonpfadprobleme 957
		Handles 133
		Hashattacke 517
		Hashfunktionen 490
		Hashing
			doppelte Sondierung 516
			Kollisionsauflösung 496
			Kuckucks- 517
			mit linearer Sondierung 501
			mit offener Adressierung 501
			mit Verkettung 496
		Hashtabellen 489
		Heap-Ordnung
			Bottom-Up-Verfahren 342
			Top-Down-Verfahren 342
		Heaps
			Algorithmen 341
			binäre 339, 340
			Definition 339
			d-näre 346
			Größenanpassung von Arrays 346
			größtes Element entfernen 343
			Konstruktion 350
			neues Element einfügen 343
			Operationen 344
			Repräsentation 340
			unveränderliche Schlüssel 346
		Heapsort 350
			Ablaufprotokoll 352
			absteigendes Sortieren 353
			Algorithmus 352
			grafisches Ablaufprotokoll 353
			Heap-Konstruktion 350
		Horner-Schema 818
		Huffman-Codierung 868, 869
			Dekomprimierung 871
			Implementierung 878
			Komprimierung 872
			Optimalität 875
			präfixfreier Code 868
			Preorder-Traversierung 877
			Triekonstruktion 873
		Huffman-Kompression 379
	I
		Implementierungsvererbung 121
		Implikationsgraphen 643
		Indizierungsclients 531
		Infixnotation 30
		Inkrement-/Dekrement-Operatoren 34
		Inorder-Traversierung 441
		In-Place-Mergen 294
		In-Place-Partitionierung 317
		Insertionsort
			Ablaufprotokoll 275
			Algorithmus 275
			Performance 274
		Instanzmethoden 106
		Instanzvariablen 105, 107
		Interface siehe Schnittstellen
		Interpolationssuche 420
		Intervallgraphen 605
		Invertierter Index 533
		Iteration 158, 392
		Iteratoren 159
			Fail-Fast 180
			Stapel 147
	J
		Jarnik-Algorithmus 671
		Johnson-Algorithmus 734
		Josephus-Problem 187
	K
		Kanten
			kreuzende 649
			kritische 676
			parallele 553
			reflexive 553
			ungerichtete Graphen 553
		Kantengewichtete Digraphen
			API 684
			Dijkstra-Algorithmus 694
			negative Zyklen 713
			Optimalitätsbedingungen 692
			Pfadgewicht 680
		Kantengewichtete Graphen
			Datentyp 651
			Kreiseigenschaft 674
			kritische Kanten 676
			Kruskal-Algorithmus 668
			minimaler Spannbaum 646
			minimaler Spannwald 646
			Repräsentation 652
		Kantenrelaxation 689
		Kapselung 116
		Kendall-Tau-Distanz 373
		Kleene'sche Satz 837
		KMP-Teilstringsuche 804, 806
			DEA-Konstruktion 808
			DEA-Simulation 806
			endliche Automaten 806
			Musterzeiger zurücksetzen 805
		Knoten
			benachbarte 554
			Exzentrizität 601
			Farbe wechseln 468
			Farbrepräsentation 463
			Quelle 640
			Rotationen 464
			Senke 640
			ungerichtete Graphen 553
		Knotenrelaxation 691
		Knoten-Verbund 162
		Knuth-Morris-Pratt siehe KMP
		Kollisionen
			auflösen 902
			Behandlung 902
			Ereignisse 904
			Simulationscode 905
			vorhersagen 901
		Kollisionsauflösung 496
		Komponenten 583
			starke 629
		Konstruktoren 105
		Kosaraju-Algorithmus 631
		Kostenmodelle 203
			B-Bäume 910
			Sortieren 269
			Suche 397
			Union-Find 243
		Kreiseigenschaft 674
		Kreuzende Kanten 649
		Kruskal-Algorithmus 379, 668
		Kuckucks-Hashing 517
		Kürzeste-Pfade-Problem 680
			azyklische kantengewichtete Digraphen 701
			Baum der kürzesten Pfade 683
			Bellman-Ford-Algorithmus 715
			Client-Abfragemethoden 691
			Datenstrukturen 689
			Dijkstra-Algorithmus 694
			Eigenschaften 682
			generischer Algorithmus 694
			Kantenrelaxation 689
			Knotenrelaxation 691
			negative Gewichte 713
			Optimalitätsbedingungen 692
			theoretische Grundlagen 692
		Kürzeste-Pfade-Probleme
			mit einem Startknoten (SSSP) 577
		Kurzschlussoperatoren 71
		Kurzschreibweisen 34
	L
		Labyrinth 566
		Längste Pfade 704
		Lauflängencodierung 863
			Bitmaps 864
			Implementierung 865
		Laufzeitanalysen
			amortisierte 220
			Beobachtungen 192
			Fallstricke 216
			Kostenmodelle 203
			mathematische Modelle 198
			Speicherbedarf 221
			Tilde-Approximation 199
			Wachstumshypothesen 202
			Wachstumsordnungen 206
			wissenschaftliche Methoden 191
		Laufzeitverhalten
			binäre Suche 68
			grafische Darstellung 196
			Quicksort 318
			Stoppuhr 196
		Lazy deletion 391
		LIFO-Prinzip 146
		Lineare Programmierung 951
		Lineare Sondierung 501
			Analyse 505
			Clusterbildung 504
		Listen
			ungeordnete verkettete 402
			verkettete 162
		Loitering 157
		Lokale Variablen 107
		Löschen
			sofortiges 391
			verzögertes 391
		LSD-Radixsort 751
		LSD-Sortierverfahren 749
		LZW-Codierung
			Vorausschauzeichen 883
		LZW-Komprimierung 883
			Dekomprimierung 884
			Implementierung 887
			Probleme 886
			Trie-Repräsentation 883
	M
		Mark-and-Sweep-Speicherbereinigung 615
		Mathematische Modelle
			Kostenmodell 203
			Näherungswerte für die Laufzeit bestimmen 200
			Tilde-Approximation 199
			Wachstumshypothesen 202
		Max-Fluss-Min-Schnitt-Theorem 935
		Max-Fluss-Problem 931
		Maxwell-Boltzmann-Verteilung 967
		Medianstatistik 373
		Median-von-Drei-Partitionierung 321
		Mehrwege-Mergesort 312
		Mehrwege-Mischen 348
		Mengen-APIs 522
		Merge-Operationen 294
		Mergesort 294
			Algorithmus 298, 303
			Bottom-Up 301, 303
			In-Place-Mergen 294
			Mehrwege-Mergesort 312
			Top-Down 296, 298
			verbessern 299
		Methoden
			geerbte 83
			Namen überladen 42
			Nebeneffekte 42
			Pass-by-Value 42
			Rekursion 43
			statische 39
			Trémaux 566
			wissenschaftliche 191
		Minimale Spannbäume 646
			API 656
			Dijkstra-Algorithmus 694
			Greedy-Algorithmus 650
			Kruskal-Algorithmus 668
			Prim-Algorithmus 658
			Schnitteigenschaft 649
			Testclient 656
		Minimaler Spannwald 646, 647
		Min-Schnitt-Problem 936
		Mischsortieren 294
		Mischtypoperatoren 31
		Modell der festen Scheibe 899
		Modulare Programmierung 44
		Modultests 45
		Monte-Carlo-Algorithmus 820
		Moore'sches Gesetz 215
		MSD-Sortierverfahren 752
			Performance 759
			Performancedaten 767
			Zufallsstring-Modell 759
		Multimengen 143
			Implementierung 174
		Musterabgleich
			Genomik 835
			Kleene'sche Satz 837
			NEA-Konstruktion 842
			NEA-Simulation 839
			nichtdeterministische endliche Automaten 836
			reguläre Ausdrücke 829
	N
		Natürliche Ordnung (Sortieren) 270
		NEA
			Erreichbarkeit 840
			Konstruktion 842
			Repräsentation 840
			Simulation 839
			Teilstringsuche 836
		Negativlisten 524
		Netzwerkflüsse 928
			API 933
			Flussnetzwerk 931
			Ford-Fulkerson-Algorithmus 934
			Max-Fluss-Problem 931
			Performance 944
			physikalisches Modell 929
			Restnetzwerk 932
			s-t-Fluss 931
		Nichtdeterminismus 958
		Nichtdeterministische endliche Automaten siehe NEA
		NP-Probleme 956
		NP-Vollständigkeit 962
		null-Schlüssel 391
	O
		Objekte
			als Argumente 89
			als Rückgabewerte 89
			Arrays 90
			Eigenschaften 92
			erzeugen 85
			geometrische 95
			Gleichheit 123
			Identität 84
			instanziieren 85
			Speicherbedarf 223
			Verhalten 84
			verwenden 87
			Zustand 84
		Operatoren
			Dekrement/Inkrement 34
			Mischtyp- 31
			Vergleichs- 31
			zusammengesetzte 34
		Optimalitätsbedingungen
			kantengewichtete Digraphen 692
			Schnitt 677
		Optimierungsprobleme 957
		Ordnungen
			alternative 366
			natürliche 270
			totale 270
		Ordnungsstatistik 373
	P
		Parallele Kanten 553
		Parametervariablen 107
		Parametrisierte Typen 141
		Partitionierung 313
			3-Wege 324
			In-Place 317
			Median-von-Drei 321
			Pivotelement 313
		Pass-by-Value 42
		Pattern Matching siehe Musterabgleich
		Pfade
			einfache 554
			kritische 706
			kürzeste augmentierende 941
		Pfadsuche 572
			Ablaufprotokoll 575
			Digraphen 616
		Pipelining 59
		Pivotelement 313
		Positivlisten 66, 524
		Postorder-Knotenreihenfolge 622
		Potenzgesetz 198
		P-Probleme 958
		Präfixfreier Code 868
		Preorder-Knotenreihenfolge 622
		Preorder-Traversierung 877
		Prim-Algorithmus 378, 658
			Ablaufprotokoll der Eager-Version 665
			Ablaufprotokoll der Lazy-Version 661
			Datenstrukturen 659
			Eager-Version 663
			Laufzeit 663
			Lazy-Version 661
		Prioritätswarteschlangen siehe Vorrangwarteschlangen
		Probleme
			Entscheidungs- 957
			Erfüllbarkeits- 956
			Hamiltonpfad 957
			Klassifizierung 964
			NP 956
			Optimierungs- 957
			P 958
			Such- 956
		Problemgröße 192
		Programmbeispiele
			Bag-Implementierung 175
			Dedup 523
			dünnbesetzte Vektoren 537
			FIFO-Warteschlange 172
			Filter 523
			FrequencyCounter 399
			Indizierungsclients 531
			invertierter Index 533
			LIFO-Stapel 161
			Positiv-/Negativlisten 524
			Stapel mit verketteter Liste 170
			Union-Find 244
			Wörterbuch-Clients 526
		Programmiermodell 25
		Programmiersprache
			streng typisiert 32
		Promotion 30
	Q
		Quelle 640
		Queue 144
			Implementierung 171
		Quick-Find 245
			Ablaufprotokoll 246
			Analyse 246
		Quicksort 313
			3-Wege-Partitionierung 324
			Ablaufprotokoll 314
			Algorithmus 314
			Entropie-optimales Sortieren 321
			In-Place-Partitionierung 317
			Laufzeitverhalten 318
			Median-von-Drei-Partitionierung 321
			partitionieren 313
			Pivotelement 313
			Sortierwechsel zu Insertionsort 321
			Verbesserungen 320
		Quick-Union 247
			Ablaufprotokoll 249
			Analyse 249
			gewichtetes 251
	R
		Rangfolgen 373
		Rangkorrelationskoeffizienten 373
		Records 163
		Reduktion 372, 946
			auf Sortieren 946
			Duplikate 372
			in Polynomialzeit 960
			Kendall-Tau-Distanz 373
			Kürzeste-Pfade-Problem 948
			lineare Programmierung 951
			Max-Fluss-Problem 948
			Medianstatistik 373
			Ordnungsstatistik 373
			Vorrangwarteschlangen 373
		Referenztypen 84, 141
		Reflexive Kanten 553
		Reguläre Ausdrücke 829
			Abkürzungen 832
			Beschränkungen 836
			Escapesequenzen 833
			GREP 847
			Klammern 830
			nichtdeterministische endliche Automaten 836
			Oder-Operation 830
			Sternhülle 830
			Sternoperationen 833
			Sternoperator 830
			Teilstringsuche 834
			Validitätsprüfung 834
			Verkettung 830
			Zeichenmengendeskriptoren 832
		Rekursion 43
			binäre Suchbäume 430
			Inorder-Traversierung 441
		Restnetzwerk 932, 938
		Rot-Schwarz-Suchbäume 461
			Eigenschaften 475
			Eins-zu-eins-Repräsentation 463
			Farben wechseln 468
			Farbrepräsentation 463
		Rückgabewerte 32, 89
		Rückrufmechanismus 364
	S
		Samplesort 331
		Schleifen
			for 35
			innere 201
			Rumpf 33
			while 33
		Schlüssel
			doppelte 391
			Gleichheit 392
			Iteration 392
			null 391
			Shannon-Entropie 325
			sortieren 267
		Schlüsselindiziertes Zählen 746
		Schnitteigenschaft 649
		Schnitt-Optimalitätsbedingungen 677
		Schnittstellen
			implements 121
			in Java 121
			Vererbung 120
		Selbstorganisierende Suche 420
		Selectionsort 272
			Ablaufprotokoll 273
			Algorithmus 273
			Datenverschiebung 273
			Laufzeit 272
			Performance 272
		Senke 640
		Sequenzielle Allokation 176
		Shannon-Entropie 325
		Shellsort 281
			Ablaufprotokoll 283, 284
			Abstandsfolge 282
			Algorithmus 283
			grafisches Ablaufprotokoll 285
		Sichtbarkeitsmodifizierer 105
		Simulationen
			Code 905
			ereignisgesteuerte 899, 900
			zeitgesteuerte 900
		Sofortiges Löschen 391
		Sollin, M. 672
		Sortieranwendungen 375
			ereignisgesteuerte Simulation 377
			Informationssuche 376
			kombinatorische Suche 378
			kommerzielle Datenverarbeitung 376
			numerische Berechnungen 378
			Operations Research 377
			Stringverarbeitung 379
		Sortieren
			absteigendes 353
			Anwendungen 363
			Arrays 267
			Bottom-Up-Mergesort 301
			Callback-Mechanismus 364
			Datentypen 270
			Duplikate 372
			durch Auswählen 272
			elementare Verfahren 267
			Entropie-optimales 321
			grafisches Ablaufprotokoll 277
			Heapsort 350
			In-Place-Mergen 294
			Komplexität 304
			Kostenmodell 269
			Mischsortieren 294
			natürliche Ordnung 270
			primitive Datentypen 371
			Rückrufmechanismus 364
			Schlüssel 267
			Sortieralgorithmen vergleichen 277
			Speicherbedarf 270
			Spielregeln 267
			Top-Down-Mergesort 296
			topologisches 618
			totale Ordnung 270
			verifizieren 269
			verschiedene Datentypen 364
			Zeiger-Sortieren 365
		Sortierverfahren
			3-Wege-Quicksort für Strings 762
			LSD 749
			Mergesort 294
			MSD 752
			Quicksort 313
			Selectionsort 272
			Shellsort 281
			stabile 368
		Spannbäume 555
		Speicherauszüge 855
		Speicherbedarf 221
			Arrays 224
			Objekte 223
			String-Objekte 226
			Teilstrings 226
			verkettete Listen 224
		Speicherbereinigung 615
			Loitering 157
			verwaiste Elemente 157
		Speicherverwaltung 125
		Stabilität 368
		Stack 146
		Stack-Implementierung 167
		Standardalphabete 742
		Standardausgabe 55
		Standardeingabe 58
		Standardgrafik 61
		Stapel 146
			fester Kapazität 151
			Implementierung 167
		Starke Komponenten 629
		Starke Zusammenhangskomponenten 629
		Statische Methoden 39
			aufrufen 40
			Bibliothek 44
			definieren 40
		Steque 186
		Streng typisierte Programmiersprache 32
		Stringindizierung 920
		Strings 52
			3-Wege-Quicksort 762
			Alphabete 741
			Anwendungsbereiche 738
			automatische Umwandlung 53
			Befehlszeilenargumente 53
			Datenkomprimierung 851
			Huffman-Komprimierung 868
			Lauflängencodierung 863
			LSD-Sortierverfahren 749
			MSD-Sortierverfahren 752
			Reguläre Ausdrücke 829
			schlüsselindiziertes Zählen 746
			Sortierverfahren 745
			Speicherbedarf 226
			Spielregeln 739
			Suffixarrays 920
			Teilstrings 226, 740
			Teilstringsuche 800
			Tries 773
			Umwandlung 52
			Unveränderlichkeit 739
			Verkettung 52, 740
			Zahlen 744
			Zeichen 739
			Zeichenarrays 740
			zeichenindizierte Arrays 743
		Stringumwandlung 122
		Strukturen 163
		s-t-Schnitt 936
		Subclassing 121
		Subtyping 120
		Suchbäume
			2-3 453
			balancierte 453
			binäre 424
			Eins-zu-eins-Repräsentation 463
			Farben wechseln 468
			Farbrepräsentation 463
			Rotationen 464
			Rot-Schwarz- 461
			Tries 775
		Suche
			binäre 405
			erfolglose 777
			erfolgreiche 776
			Interpolationssuche 420
			Kostenmodell 397
			selbstorganisierende 420
			sequenzielle 402
		Suchprobleme 956
		Suchtries, ternäre 789
		Suffixarrays 918
			API 922
			Brute-Force-Lösung 919
			Implementierung 925
			Performance 925
			Sortierlösung 920
			Stringindizierung 920
			Teilstrings 918
		Symbolgraphen 589
		Symboltabellen
			Abrundungsfunktion 395
			API 390, 393
			Aufrundungsfunktion 395
			Beispielclient 398
			Definition 389
			Floor/Ceiling 395
			Für und Wider von Implementierungen 415
			Generics 390
			geordnete 393
			Gleichheit 396
			Kostenmodell 397
			Kostenvergleich verschiedener Implementierungen 520
			löschen 391
			Minimum/Maximum 394
			Performance-Client 399
			Rang/Auswahl 395
			redundante Methoden 396
		Systemsortierverfahren (Java) 371
	T
		Tarjan, R. E. 671
		Teilgraphen 554
		Teilstrings 740
		Teilstringsuche 800
			Boyer-Moore 812
			Brute-Force-Implementierung 801
			Fingerprint-Suche 817
			geschichtlicher Abriss 800
			Knuth-Morris-Pratt 804
			Rabin-Karp 817
			reguläre Ausdrücke 834
			Vorkommensheuristik 813
		Ternäre Suchtries 789
			Alphabete 793
			Eigenschaften 792
			hybride 794
			Suchen/Einfügen 791
			Suchkosten 792
			Verzweigungsgrad 1 794
		Tiefensuche 566
			Ablauf 569
			Ablaufprotokoll 570
			Algorithmus 567
			Labyrinth 566
			Pfade mit einem Startknoten 572
			Single-Source-Path (SSP) 572
			Traversierung 620
			Trémaux Methode 566
			Union-Find 587
			Zusammenhang feststellen 570
			Zusammenhangskomponenten 583
			Zweifärbbarkeit 587
			Zykluserkennung 587
		Tilde-Approximation 199
		Tilde-Notation 199
		Top-Down
			Heaps 342
			Mergesort 296, 298
		Topologisches Sortieren 618
		Totale Ordnung (Sortieren) 270
		Transaktionen-Beispiel 364
		Transitive Hülle 636
		Trémaux-Methode 566
		Tries
			durchsuchen 776
			Eigenschaften 775, 785
			Einfügen/Suchen 777, 786
			längster Präfix 783
			löschen 784
			LZW-Komprimierung 883
			Platzhalterübereinstimmung 782
			Preorder-Traversierung 877
			Repräsentation 777, 869, 883
			Speicherbedarf 787
			ternäre Suchtries 789
			Verzweigungsgrad 1 788
		Tschebyschow-Ungleichung 328
		Tukey Ninther 331
		Turingmaschine 954
		Typparameter 141
		Typumwandlung 30
	U
		Umgekehrte Postorder-Knotenreihenfolge 622
		Ungerichtete Graphen 553
			Adjazenzlisten 559, 560
			Adjazenzmatrix 559
			azyklische 555
			Baum 555
			benachbarte Knoten 554
			bipartite 556
			Brücken 604
			dichte 556
			dünne 556
			Durchmesser 601
			euklidische 604
			eulersche Zyklen 604
			Gelenkpunkt 604
			Gittergraphen 605
			Hamilton'sche Zyklen 604
			Intervallgraphen 605
			isomorphe 603
			Kanten 553
			Kantenzusammenhang 604
			Knoten 553
			kreisfreie 555
			Mittelpunkt 601
			Pfad 554
			Radius 601
			Spannbaum 555
			Taillenweite 602
			Teilgraphen 554
			zusammenhängende 555
			Zusammenhangskomponenten 555
			zweifacher Zusammenhang 604
			Zyklus 554
		Union-Find 238
			Tiefensuche 587
		Universelle Datenkomprimierung 857
		Unveränderlichkeit (final) 126
	V
		Variablen
			Instanzvariablen 105, 107
			lokale 107
			Parametervariablen 107
		Vektoren, dünnbesetzte 537
		Verdopplungsverhältnis 212
		Vererbung
			Implementierung 121
			Schnittstellen 120
		Vergleiche 31
			Sortieralgorithmen 277
		Vergleichsoperatoren 31
		Verifizierung
			sortieren 269
		Verkettete Allokation 176
		Verkettete Listen 162
			am Anfang einfügen 164
			am Ende einfügen 165
			an anderen Position einfügen/ entfernen 166
			erstellen 163
			Speicherbedarf 224
			traversieren 167
			vom Anfang entfernen 165
		Verkettung 740
		Verzögertes Löschen 391
		Vorkommensheuristik 813
		Vorrangbedingungen 617
		Vorrangwarteschlangen 333
			Algorithmus 345
			API 334
			Arrayrepräsentation (geordnet) 337
			Arrayrepräsentation (ungeordnet) 336
			Client 335
			Comparator 367
			einfache Implementierungen 336
			Größenanpassung 346
			größtes Element entfernen 343
			indizierte 346
			Mehrwege-Mischen 348
			neues Element einfügen 343
			Repräsentation mit verketteten Listen 338
			unveränderliche Schlüssel 346
	W
		Wachstumshypothesen 202
		Wachstumsordnung
			exponentielle 207
			Klassifikation 206
			konstante 206
			kubische 207
			leicht überlinear 206
			lineare 206
			logarithmische 206
			quadratische 206
			unterer Grenzwert 211
			Verdopplungsverhältnis 212
		Wald von Bäumen 248
		Warteschlangen 144
			Deque 186
			Implementierung 171
			Steque 186
		while-Schleifen 33
		Wissenschaftliche Methoden 191, 278
		Wörterbuch-Clients 526
		Wrapper-Klassen 123
		Wrappertypen 123
	Z
		Zahlen 744
		Zeichen 739
		Zeichenarrays 740
		Zeiger-Sortieren 365
		Zeitgesteuerte Simulation 900
		Zipf'sches Gesetz 422
		Zufallsstring-Modell 759
		Zugriffsmodifizierer 105
		Zusammenhangskomponenten 555
			API 583
			berechnen 583
			Gelenkpunkt 604
			starke 629
			verwalten 238
		Zusicherungen 129
		Zuweisungen 32
			abstrakte Datentypen 87
			implizite 34
		Zweidimensionale Arrays 38
		Zweifärbbarkeit 587
		Zyklen
			einfache 554
			einfache in Digraphen 608
			gerichtete 608, 617
			negative 713
			negative Zyklen erkennen 721
		Zykluserkennung 587
Copyright