Inhaltsverzeichnis

I

Einleitung

V

1. Begriffsbildung

1

1.1. Algorithmus

1

1.2. Komplexität

4

1.3. Verbrauch und Komplexität

5

2. Gleichwertige Lösungen

8

2.1. Maximale Teilsumme

8

2.1.1. Summen und Teilsummen

8

2.1.2. Aufgabenstellung

9

2.1.3. Intuitive Lösung

9

2.1.4. Zeitkomplexität der Lösung

10

2.1.5. Zeit für Raum

12

2.1.6. Teile und herrsche

14

2.1.7. Die optimale Lösung

17

2.1.8. Messergebnisse

18

2.1.9. Gleichwertigkeit von Algorithmen

20

2.2. Komplexitätsformel

21

2.3. Datenstrukturen

22

2.3.1. Reihungen

23

2.3.2. Verkettete Listen

24

2.3.3. Gleichwertigkeit von Datenstrukturen

27

3. Rekursion und Wiederholung

30

3.1. Rekursive Algorithmen

30

3.1.1. Fakultät

30

3.1.2. Die Fibonacci-Zahlen

31

3.1.3. Die Ackermann-Funktion

34

3.1.4. Die mathematische Induktion

34

3.1.5. Permutationen

37

3.2. Abarbeitung von Datenstrukturen

38

3.2.1. Iterative Abarbeitung von rekursiven Datenstrukturen

38

3.2.2. Rekursive Abarbeitung von rekursiven Datenstrukturen

39

3.2.3. Rekursive Abarbeitung von Reihungen

40

3.3. Rekursive Kurven

42

3.3.1. Schneeflockenkurve

43

3.3.2. Die Pfeilspitzenkurve

45

3.3.3. Die Hilbert-Kurve

47

3.3.4. Ersetzen der Rekursion durch Wiederholung

50

3.4. Zurückverfolgung

53

3.4.1. Labyrinth

53

3.4.2. Der Weg des Springers

54

3.4.3. Die acht Damen

56

3.5. Spracherkennung

60

3.5.1. Sprachen und Grammatiken

60

3.5.2. Reguläre Ausdrücke

61

3.5.3. Reguläre Grammatiken

63

3.5.4. R-Grammatiken

64

3.5.5. Endliche Automaten

66

3.5.6. Kellerautomaten

70

3.5.7. Endlichkeit und Unendlichkeit

71

4. Suchen

73

4.1. Textsuche

73

4.2. Suchen in Sammlungen

77

4.3. Suchen in einer Reihung

78

4.3.1. Suchen in einer unsortierten Reihung

78

4.3.2. Lineares Suchen in einer sortierten Reihung

80

4.3.3. Binäres Suchen

81

4.4. Hash-Tabellen

82

4.5. Suchen in einer verketteten Liste

87

4.5.1. Lineares Suchen in einer unsortierten Liste

88

4.5.2. Lineares Suchen in einer sortierten Liste

89

4.6. Zeitkomplexitäten beim Suchen

89

5. Sortierverfahren

92

5.1. Die Problemstellung

92

5.1.1. Präzisierung des Problems und Grundbegriffe

93

5.1.2. Zeitbedarf und Zeitkomplexität

95

5.2. Quadratische Sortierverfahren

96

5.2.1. Sortieren durch Vertauschen benachbarten Elemente

96

5.2.2. Sortieren durch Einfügen

98

5.2.3. Sortieren durch Auswählen

100

5.3. Unterquadratische Verfahren

101

5.4. Rekursive Verfahren

103

5.5. Logarithmische Verfahren

106

5.5.1. Halde

106

5.5.2. Die Haldenbedingung

107

5.5.3. Senken

108

5.5.4. Zwei Phasen des Heap Sorts

109

5.5.5. Sortieren auf der Halde

110

5.6. Externe Sortierverfahren

112

5.6.1. Mischen

113

5.6.2. Sortierkanal

115

5.6.3. Mischkanal

116

5.6.4. Fibonacci-Mischen

117

6. Baumstrukturen

120

6.1. Binärbaum

120

6.1.1. Definition

120

6.1.2. Suchen im sortierten Binärbaum

124

6.1.3. Darstellung von Binärbäumen

124

6.2. Sortieren mit Binärbäumen

127

6.2.1. Binärbaum als Halde

127

6.2.2. Senken im Binärbaum

128

6.2.3. Baumsort

130

6.2.4. Durchwandern eines Binärbaums

132

6.3. Operationen für Binärbäume

135

6.3.1. Binärbaum aus Knoten

135

6.3.2. Eintragen in einen sortierten Binärbaum

135

6.3.3. Löschen in Binärbäumen

137

6.4. Ausgeglichene Bäume

140

6.4.1. Eintragen in ausgeglichene Bäume

141

6.4.2. Löschen in ausgeglichenen Bäumen

145

6.5. 2-3-4-Bäume

147

6.5.1. Definition

147

6.5.2. Spalten

148

6.5.3. Einfügen

150

6.6. Rot-Schwarz-Bäume

152

6.7. B-Bäume

158

7. Klassen von Algorithmen

162

7.1. Was ist ein algorithmisches Problem?

162

7.2. Theoretische Lösbarkeit von Problemen

167

7.2.1. Definitionen

167

7.2.2. Beispiele

168

7.2.3. Das Halteproblem

171

7.2.4. Das Kachelproblem

172

7.2.5. Das Paligrammproblem

174

7.2.6. Gleichwertigkeit von Grammatiken

176

7.3. Praktische Lösbarkeit von Problemen

177

7.3.1. Das zweite Kachelproblem

178

7.3.2. Das Rucksackproblem

179

7.3.3. Das Aufteilungsproblem

179

7.3.4. Das Problem des Handelsreisenden

180

7.3.5. Hamiltonsche Wege durch einen Graphen

180

7.3.6. Das Erfüllbarkeitsproblem

181

7.4. Die Klassen P und NP

182

7.5. Ist P = NP?

184

7.6. Übersicht über Problemklassen

185

Literaturverzeichnis

187

Empfehlungen

188

Programmverzeichnis

190

Abbildung- und Tabellenverzeichnis

192

Sachwortverzeichnis

195