Algorithmen und Datenstrukturen

Abbildungsverzeichnis

1–1	Compiler und Interpreter bei Java
1–2	Struktur eines Java-Programms
2–1	Notation für Struktogramme
2–2	Beispiel eines Struktogramms
2–3	Schleifen und bedingte Anweisung im Struktogramm
2–4	Türme von Hanoi
2–5	Signaturgraph für natürliche Zahlen
2–6	Zuweisung von Referenzen
2–7	Tic-Tac-Toe-Spielfeld
3–1	Semantik imperativer Algorithmen am Beispiel
3–2	Auswertung der Anfrage add(3,2,5)
3–3	Auswertung der Anfrage add(3,2,X)
3–4	Auswertungszweige der Anfrage add(X,Y,1)
3–5	Zwei Lösungen des Acht-Damen-Problems
3–6	Grundmodell des Perzeptrons
3–7	XOR-Problem
3–8	Neuronales Netz für XOR
3–9	Sichtbarkeit und Gültigkeitsbereich von Variablen
3–10	Prinzip des Pythagoras-Baumes
3–11	Ausgabe des Programms zum Pythagoras-Baum
5–1	Binäres Suchen in einer sortierten Folge
5–2	InsertionSort am Beispiel
5–3	SelectionSort am Beispiel
5–4	BubbleSort am Beispiel
5–5	MergeSort am Beispiel
5–6	Pivot-Element beim QuickSort
5–7	QuickSort am Beispiel
5–8	RadixSort am Beispiel
6–1	Ein- und Ausgabebefehle einer Registermaschine
6–2	Arithmetische Befehle von Registermaschinen
6–3	Sprung- und Stoppbefehle einer Registermaschine
6–4	Aufbau einer Registermaschine
6–5	Registermaschine zur Berechnung des Primzahltests
6–6	Abstrakte Maschine
7–1	Die Maschine STOP
7–2	Die Maschine SELTSAM
7–3	Asymptotische obere Schranke: O-Notation
8–1	Spielablauf für Tic Tac Toe
8–2	Ausführung eines Spielzugs
8–3	Eingabe für Kommunikationsnetz
8–4	Errechnetes Kommunikationsnetz
8–5	Spielplan T₂
8–6	Konstruktion des Spielplans T_k+1
8–7	Spielplan T₃
8–8	Labyrinth-Suche und Backtracking
8–9	Acht-Damen-Problem
8–10	Nicht alle Konfigurationen lassen sich zu einer Lösung erweitern
8–11	Konfigurationsraum beim Vier-Damen-Problem
8–12	Lösungsbaum für Tic Tac Toe
8–13	Bewertung von Spielzügen in Tic Tac Toe
8–14	Lösungsraum beim Rucksackproblem
8–15	Feld der Funktionswerte des Rucksackproblems
9–1	Shared Memory vs. Message Passing
9–2	Petri-Netz für Produzenten-Verbraucher-System
9–3	Petri-Netz mit Marken
9–4	Petri-Netz nach Feuern von produce
9–5	Petri-Netz nach Feuern von deliver
9–6	Produzenten-Verbraucher-System mit Puffergröße 2 als Bedingungs-Ereignis-Netz
9–7	Stellen-Transitions-Netz für Puffergröße 2
9–8	Stellen-Transitions-Netz mit Kapazität
9–9	Grafische Darstellung des formal beschriebenen Petri-Netzes P
9–10	Modellierungsprimitive für Petri-Netze
9–11	Philosophenproblem als Petri-Netz: Ein Philosoph
9–12	Stellen aller 5 Philosophen
9–13	Fünf Philosophen mit Verklemmungsmöglichkeit
9–14	Zustände von Prozessen
9–15	Erzeuger-Verbraucher-System als Petri-Netz
11–1	Verdeutlichung des Stack-Prinzips
11–2	Auswertung eines arithmetischen Terms mit einem Stack
11–3	Auswertung eines arithmetischen Terms mit zwei Kellern
11–4	Verdeutlichung des Queue-Prinzips
12–1	Objekt am Beispiel
12–2	Klassenkonzept
12–3	Generalisierung vs. Spezialisierung
12–4	Einfach- vs. Mehrfachvererbung
12–5	Probleme ohne Mehrfachvererbung
12–6	Kontrollfluss beim Auslösen einer Ausnahme
13–1	Prinzip der verketteten Liste
13–2	Einfügen am Beginn einer verketteten Liste
13–3	Einfügen und Löschen am Ende einer verketteten Liste
13–4	Doppelt verkettete Liste
13–5	Anhängen am Ende einer doppelt verketteten Liste
13–6	Aufbau einer Skip-Liste
13–7	Suche in einer Skip-Liste
13–8	Randomisierte Skip-Liste
13–9	Iterator-Konzept
13–10	Struktur des Java Collection Framework
14–1	Beispiele für Baumstrukturen
14–2	Begriffe in einem Baum
14–3	Baum mit Niveau der Höhe 4
14–4	Arithmetischer Ausdruck als Baum
14–5	Baumstruktur in einem Dateisystem
14–6	Pseudoknoten für die Realisierung eines Binärbaumes
14–7	Beispiel eines binären Baumes
14–8	Suche im binären Suchbaum
14–9	Einfügen im binären Suchbaum
14–10	Löschen im binären Suchbaum
14–11	»Gute« und »schlechte« Suchbäume
14–12	Vollständiges Ausgleichen eines Baumes
14–13	2-3-4-Baum
14–14	Repräsentation von 3- und 4-Knoten im Rot-Schwarz-Baum
14–15	Fall 1 des Splittens im Rot-Schwarz-Baum
14–16	Fall 2A des Splittens
14–17	Fall 2B des Splittens
14–18	Einfügen im Rot-Schwarz-Baum: Beispiel
14–19	Rotationen beim Einfügen von »13«
14–20	AVL-Eigenschaft am Beispiel
14–21	Einfache Rotation
14–22	Doppelrotation
14–23	Ergebnis der Rotationen aus Beispiel 14.1
14–24	Struktur einer Seite im B-Baum
14–25	Suchen im B-Baum
14–26	Einfügen im B-Baum
14–27	Aufbau eines B-Baumes
14–28	Löschen im B-Baum I
14–29	Löschen im B-Baum II
14–30	Struktur eines Knotens im Trie
14–31	Beispiel eines Tries
14–32	Einfügen in einen binären Trie
14–33	Patricia-Baum
14–34	Heap-Struktur
14–35	Darstellung eines Heaps als Feld
14–36	Entfernen der Wurzel im Heap
14–37	Aufbau eines Heaps
14–38	Sortierung des Heaps
14–39	Prinzip des Iterators für einen Suchbaum (Inorder-Durchlauf)
15–1	Beispiel für eine Hashtabelle
15–2	Hashtabelle mit verketteten Überläufern
15–3	Lineares Sondieren
15–4	Quadratisches Sondieren
15–5	Hashtabellen beim Cuckoo-Hashing
15–6	Hashtabellen beim Cuckoo-Hashing nach Verdrängen von 129
15–7	Hashtabellen beim Cuckoo-Hashing nach kaskadierendem Verdrängen
15–8	Erweiterbares Hashen: Beispiel der Tiefe d = 2
15–9	Erweiterbares Hashen mit verdoppelter Feldgröße
15–10	Aufteilen eines Blockes beim erweiterbaren Hashen
16–1	G_u: Beispiel für ungerichteten Graphen
16–2	G_g: Beispiel für gerichteten Graphen
16–3	Beispiel für gewichteten Graphen
16–4	Graph als dynamische Datenstruktur
16–5	Breitendurchlauf am Beispiel nach initialem Schritt
16–6	Breitendurchlauf in den folgenden Schritten
16–7	Durch Breitendurchlauf erzeugter aufspannender Baum
16–8	Beispielgraph für Tiefendurchlauf
16–9	Die ersten acht Zwischenzustände beim Tiefendurchlauf
16–10	Die Zwischenzustände 9 bis 16 beim Tiefendurchlauf
16–11	Eingabe für topologisches Sortieren
16–12	Topologisches Sortieren durch Tiefensuche mit DFS
16–13	Topologisches Sortieren durch Tiefensuche II
16–14	Gewichteter Graph
16–15	Dijkstras Algorithmus: Initialisierung
16–16	Dijkstras Algorithmus nach erstem Durchlauf
16–17	Dijkstras Algorithmus nach zweitem Schleifendurchlauf
16–18	Dijkstras Algorithmus nach drittem Schleifendurchlauf
16–19	Dijkstras Algorithmus nach viertem Schleifendurchlauf
16–20	A*-Algorithmus: Beispiel
16–21	A*-Algorithmus: Beispiel im 2. Schritt
16–22	Graph mit negativen Kantengewichten
16–23	Bellman-Ford-Algorithmus: Initialisierung
16–24	Bellman-Ford-Algorithmus: Schleifendurchlauf für i = 1
16–25	Bellman-Ford-Algorithmus: Schleifendurchlauf für i = 2
16–26	Bellman-Ford-Algorithmus: Schleifendurchlauf für i = 3
16–27	Bellman-Ford-Algorithmus: Schleifendurchlauf für i = 4
16–28	Graph mit negativ gewichtetem Zyklus
16–29	Paketvermittlung in Computernetzwerk
16–30	Graph mit Kapazitäten mit leerem Fluss
16–31	Ford-Fulkerson: Auswahl des ersten Pfades
16–32	Ford-Fulkerson: Adjustierung der Kantenbeschriftung und Auswahl des zweiten Pfades
16–33	Ford-Fulkerson: Auswahl des dritten Pfades
16–34	Ford-Fulkerson: Auswahl des vierten Pfades
16–35	Ford-Fulkerson: Auswahl des fünften Pfades
16–36	Ford-Fulkerson: Abschluss der Berechnung
16–37	Beispiel der PageRank-Berechnung
16–38	K₅ und K_3,3
16–39	Ländernachbarschaft in Europa als Graph
17–1	Ablauf beim Brute-Force-Algorithmus
17–2	Knuth-Morris-Pratt-Algorithmus am Beispiel
17–3	Berechnung der next-Tabelle
17–4	Boyer-Moore: Verschiebung des Musters bei Nichtübereinstimmung I
17–5	Boyer-Moore: Verschiebung des Musters bei Nichtübereinstimmung II
17–6	Boyer-Moore: Suffix-Tabelle
17–7	Boyer-Moore-Algorithmus am Beispiel
17–8	Beispiel für einen nichtdeterministischen endlichen Automaten
17–9	Konstruktion eines NEA aus regulären Ausdrücken I
17–10	Konstruktion eines NEA aus regulären Ausdrücken II
17–11	Aus »A BA« konstruierter NEA
17–12	Repräsentation eines NEA
17–13	Ablauf bei Erkennung von »AABA«
17–14	Matrix zur Bestimmung der Levenshtein-Distanz