Alle Kapitel aufklappen
Alle Kapitel zuklappen
1.1 Kompetenzen für die theoretische Arbeit
16
1.1.1 Abstraktionsvermögen
16
1.1.2 Präzises Arbeiten
16
1.1.3 Frustrationstoleranz und Kreativität
17
1.1.4 Kommunikationsfähigkeit
17
1.2 Themen der theoretischen Informatik
18
1.2.1 Berechenbarkeitstheorie
18
1.2.3 Komplexitätstheorie
19
1.3 Anleitung fürs Buch
20
2 Mathematische Notation
23
2.1.1 Verknüpfung von logischen Aussagen
24
2.1.4 Umformungsregeln
26
2.2.1 Mengenoperationen
28
2.2.2 Quantoren und Prädikate
29
2.2.3 Mengenbeziehungen
30
2.3 Relationen und Funktionen
32
2.3.1 Binäre Relationen
32
2.3.3 Binäre Operationen über Mengen
36
2.4.2 Pfade, Kreise und Bäume
38
2.4.3 Teilgraphen und Spannbäume
39
2.4.4 Gerichtete Kanten
39
2.4.5 Gewichtete Graphen
39
2.5 Unendlichkeiten und Abzählbarkeit
40
2.5.1 Abzählbar unendliche Mengen
40
2.5.2 Überabzählbar unendliche Mengen
41
2.6.1 Grundprinzipien des Beweisens
42
2.6.3 Fallunterscheidungen
46
2.6.4 Beweis per Kontraposition
48
2.6.5 Indirekter Beweis / Beweis per Widerspruch
49
2.6.6 Vollständige Induktion
50
2.6.7 Konstruktive und nichtkonstruktive Beweise
54
2.6.8 Typische Schwierigkeiten und Fehler beim Beweisen
54
TEIL I Berechenbarkeit und formale Sprachen
65
3 Einführung in die Berechenbarkeitstheorie
67
3.2 Zu viele Funktionen
69
4.1 Formalisierung von Problemen
73
4.2 Funktionen berechnen
75
4.4 Sprachen entscheiden
78
4.5 Problemklassen der Berechenbarkeitstheorie
79
5 Einführung in formale Sprachen
85
5.2 Die Chomsky-Hierarchie
88
6.1 Deterministische endliche Automaten
92
6.1.1 Formale Definition
93
6.1.3 Simultane strukturelle Induktion
98
6.1.4 Automatenentwurf
100
6.2 Nichtdeterministische endliche Automaten
103
6.2.1 Formale Definition
105
6.2.2 Erweiterung: Epsilonübergänge
106
6.2.3 Äquivalenz zu deterministischen Automaten
108
6.3.1 Formale Definition
113
6.3.2 Reguläre Grammatiken
114
6.3.3 Varianten regulärer Grammatiken
115
6.3.4 Äquivalenz zu endlichen Automaten
116
6.4 Reguläre Ausdrücke
120
6.4.1 Formale Definition
120
6.4.2 Äquivalenz zu endlichen Automaten
121
6.5 Abschlusseigenschaften
127
6.5.1 Abgeschlossenheit unter Vereinigung, Konkatenation und kleenescher Hülle
127
6.5.2 Abgeschlossenheit unter Schnitt und Differenz
128
6.5.3 Abgeschlossenheit unter Komplement
129
6.5.4 Abgeschlossenheit unter Spiegelung
130
6.5.5 Abgeschlossenheit unter Homomorphismen
130
6.5.6 Beweise mit Abschlusseigenschaften
131
6.6 Entscheidungsprobleme auf regulären Sprachen
132
6.7 Äquivalenzklassenzerlegung
134
6.7.1 Die Nerode-Relation
135
6.7.2 Minimale Automaten
136
6.7.3 Der Table-Filling-Algorithmus
137
6.8 Nichtreguläre Sprachen
139
6.8.1 Der Satz von Myhill-Nerode
139
6.8.2 Das Pumping-Lemma für reguläre Sprachen
140
6.8.3 Beweise mit Abschlusseigenschaften
143
7 Kontextfreie Sprachen
161
7.1 Kontextfreie Grammatiken
162
7.2 Eindeutige Ableitungsbäume
164
7.3 Chomsky-Normalform
166
7.4 Exkurs: Kellerautomaten
170
7.4.1 Formale Definition
172
7.5 Abschlusseigenschaften
175
7.6 Entscheidungsprobleme auf kontextfreien Sprachen
176
7.6.1 Wortproblem: Der Cocke-Younger-Kasami-Algorithmus (CYK)
176
7.6.2 Leerheitsproblem
180
7.7 Nicht-kontextfreie Sprachen
181
7.7.1 Das Pumping-Lemma für kontextfreie Sprachen
181
7.7.2 Beweise mit Abschlusseigenschaften
183
8 Kontextsensitive Sprachen
193
8.1 Kontextsensitive und monotone Grammatiken
194
8.2 Das Wortproblem auf kontextsensitiven Sprachen
195
9 Aufzählbare Sprachen
197
9.1.1 Berechnungen mit Turingmaschinen
200
9.1.2 Varianten und Ausblick
201
9.2.1 Syntax und Semantik
203
9.2.2 Identität und konstante Funktionen
205
9.2.3 Einfache Arithmetik: Addition
206
9.2.4 Aufrufen von Unterprogrammen
209
9.2.5 Fallunterscheidungen, Logik und Vergleiche
213
9.2.7 Cantorsche Paarungsfunktion
215
9.2.8 Datenstrukturen
217
9.4 Das universelle While-Programm
220
9.5 Das schrittbeschränkte universelle While-Programm
223
9.6 Diagonalisierung und min-Suche
224
9.7 Prädikate für semi-entscheidbare Sprachen
226
9.8 Semi-Entscheidbarkeit vs. Aufzählbarkeit
227
9.9 Das S-m-n-Theorem
228
9.10 Das kleenesche Rekursionstheorem
230
9.11 Weitere Modelle und Charakterisierungen
233
10 Nicht Berechenbares
241
10.2 Der Satz von Rice
244
10.4 RE-Vollständigkeit
250
10.5 Ausblick: Die arithmetische Hierarchie
251
11 Einführung in Algorithmik
261
12 Obere Schranken für Laufzeiten
263
12.1 Das Maschinenmodell
264
12.2 Die Laufzeit eines Algorithmus
267
12.3 Die Größe einer Eingabe
268
12.4 Die Landau-Notation
268
13 Laufzeiten von Datenstrukturen
275
13.3 Verschachtelte Datenstrukturen und Graphen
279
14 Brute-Force-Algorithmen
285
14.2 Backtracking/Tiefensuche
288
15 Greedy-Algorithmen
295
15.1 Beweis mit Austauschargument
296
15.1.1 Farbeimer kaufen
296
15.1.2 Minimale Spannbäume
299
15.2 Greedy stays ahead
302
16 Divide and Conquer
313
16.3 Multiplikation großer Zahlen
321
16.3.2 Laufzeitanalyse
323
16.3.3 Der Algorithmus von Karazuba
324
16.4 Das Mastertheorem
325
17 Dynamische Programmierung
335
17.1 Fibonacci-Zahlen
336
17.3 Der Algorithmus von Dijkstra
341
18 Amortisierte Analyse
351
18.1 Dynamische Arrays
351
TEIL III Komplexitätstheorie
355
19 Einführung in die Komplexitätstheorie
357
19.1 Die Komplexität eines Problems
358
19.2 Bedingte Schranken
358
19.3 Auswege für schwierige Probleme
359
20 Beweistechniken für untere Schranken
361
20.1 Die Ausgabegröße
362
20.2 Das informationstheoretische Argument
363
20.2.1 Analyse der Ablaufpfade
364
20.2.2 Analyse des Informationsgewinns pro Anfrage
366
20.3 Das Adversary-Argument
367
21 P vs. NP: Bedingte untere Schranken
377
21.1 Die Komplexitätsklasse P
378
21.2 Die Komplexitätsklasse NP
380
21.2.1 Ein Praxisbeispiel: Independent Set
381
21.2.2 Die Definition von (Nicht-)Determinismus
383
21.2.3 Nichtdeterministisch berechnen und deterministisch verifizieren
386
21.3 Polynomialzeitreduktionen
388
21.3.2 Beispiel: Independent Set und Vertex Cover
390
21.4 NP-schwere und NP-vollständige Probleme
392
21.4.1 Der Satz von Cook
395
21.4.2 Von CNF-SAT zu 3-SAT
396
21.4.3 Von 3-SAT zu IS
398
21.4.4 Von 3-SAT zu Subset-Sum
401
21.5 Ausblick: Mehr NP-vollständige Probleme
404
22 Ausblick: Parametrisierte Analyse
408