Über den Autor 7
Einleitung 17
Was ist theoretische Informatik? 17
Über dieses Buch 18
Wie dieses Buch aufgebaut ist 18
Symbole in diesem Buch 20
Wie Sie dieses Buch lesen sollten 20
Teil I Endliche Automaten 21
Kapitel 1 Deterministische Endliche Automaten (DFAs) 23
Einführung 23
Erste Beispiele 24
Grundlegende Definitionen 27
Symbole und Wörter 27
Die Definition eines DFAs 28
Reguläre Sprachen 30
Die erweiterte Übergangsfunktion 30
Beispiele regulärer Sprachen 31
Das Pumping Lemma 34
Minimalautomaten 38
Der Satz von Myhill und Nerode 45
DFAs mit Ausgabe (Moore- und Mealy-Automaten) 50
Aufgaben zu DFAs 54
Kapitel 2 Nichtdeterministische Endliche Automaten (NFAs) 57
Nichtdeterminismus 57
Definition eines NFA 58
Der Satz von Rabin-Scott 60
NFAs mit ¿-Übergängen 64
Abschlusseigenschaften regulärer Sprachen 67
Reguläre Ausdrücke 70
Stochastische Automaten und Markov-Ketten 75
Hidden Markov Models 80
Aufgaben zu NFAs 80
Kapitel 3 Kellerautomaten (PDAs) 83
Nichtdeterministische Kellerautomaten 83
Deterministische Kellerautomaten 89
Die Grenzen von PDAs 91
Aufgaben zu PDAs 92
Kapitel 4 Turing-Maschinen 93
Deterministische Turing-Maschinen 93
Turing-Berechenbarkeit 102
Mehrband-Turing-Maschinen 105
Registermaschinen 109
Nichtdeterministische Turing-Maschinen 110
Linear beschränkte Turing-Maschinen 112
Universelle Turing-Maschine (UTM) 113
Die Grenzen von Turing-Maschinen 115
Aufgaben zu Turing-Maschinen 120
Teil II Formale Sprachen 123
Kapitel 5 Grammatiken 125
Einführung 125
Ein erstes Beispiel 126
Syntaxbäume 127
Definition einer Grammatik 128
Die von einer Grammatik erzeugte Sprache 128
Wie man ¿-Regeln loswird 129
Das Wortproblem 131
Chomsky-Hierarchie 131
Aufgaben zu Grammatiken 133
Kapitel 6 Reguläre (Typ-3-)Sprachen 135
Beispiele für Typ-3-Sprachen 135
Das Wortproblem für Typ-3-Sprachen 136
Aufgaben zu Typ-3-Sprachen 139
Kapitel 7 Kontextfreie (Typ-2-)Sprachen 141
Erste Beispiele 141
Backus-Naur-Form (BNF) 142
Erweiterte Backus-Naur-Form (EBNF) 142
Chomsky-Normalform 144
Die Grenzen kontextfreier Sprachen 146
Ein äquivalentes Maschinenmodell 150
Deterministisch kontextfreie Sprachen 153
Das Wortproblem für kontextfreie Sprachen 154
Abschlusseigenschaften 156
Aufgaben zu kontextfreien Sprachen 157
Kapitel 8 Kontextsensitive und Phasen-Struktur-Sprachen 159
Ein erstes Beispiel 159
Das Wortproblem für Typ-1-Sprachen 160
Das Wortproblem für Typ-0-Sprachen 161
Äquivalente Maschinenmodelle 162
Typ-0-Sprachen 162
Typ-1-Sprachen 164
Teil III Harte Probleme 167
Kapitel 9 Zeitkomplexität von Algorithmen 169
Einführende Überlegungen 169
Zeit- und Speicherkomplexität von Algorithmen 171
Die O-Notation 175
Komplexitätsklassen von Sprachen 177
Aufgaben zur Komplexität von Algorithmen 179
Kapitel 10 Die Klassen P und NP 181
Die Klasse P 181
Die Klasse NP 182
Zertifikate 182
Das SAT-Problem 185
Reduktion 188
SAT, KNF-SAT und 3-SAT 190
Reduktion und Entscheidbarkeit 196
Aufgaben zu P und NP 197
Kapitel 11 NP-Vollständigkeit 199
Der Satz von Cook 199
Boolesche Schaltkreise und deterministische Turing-Maschinen 200
Boolesche Schaltkreise und nichtdeterministische Turing-Maschinen 206
Reduktion von CIRCUIT-SAT auf 3-SAT 208
Beispiele NP-vollständiger Sprachen 210
SUBSET-SUM-Problem 210
Hamilton-Kreise 213
Das Travelling-Salesman-Problem 219
Das Cliquen-Problem 221
Ist P = NP? 223
Quantencomputer 223
Die Klasse BQP 225
Aufgaben zur NP-Vollständigkeit 227
Teil IV Mathematische Grundlagen 229
Kapitel 12 Logische Grundlagen 231
Boolesche Variablen und boolesche Formeln 231
Aussagen und Beweise 233
Beweistechniken 234
Aufgaben zur Logik 238
Kapitel 13 Mengen und Relationen 239
Grundbegriffe 239
Mengenoperationen 241
Relationen 242
Äquivalenzrelationen 242
Ordnungsrelationen 244
Funktionen 245
Aufgaben zu Mengen und Relationen 247
Kapitel 14 Graphen und Bäume 249
Graphen und ihre Eigenschaften 249
Zusammenhängende Graphen 251
Darstellung von Graphen im Computer 253
Bäume 256
Tourenprobleme 258
Gewichtete Graphen 260
Näherungsweise Lösung des TSP 261
Aufgaben zu Graphen und Bäumen 265
Teil V Top-Ten-Teil 267
Kapitel 15 Top-Ten-Theoretiker 269
Charles Babbage (1791-1871) 269
Ada Lovelace (1815-1852) 270
Alonzo Church (1903-1995) 270
Alan Turing (1912-1954) 271
Claude Shannon (1916-2001) 272
Richard Feynman (1918-1988) 273
Noam Chomsky (geboren 1928) 274
Michael Rabin (geboren 1931) und Dana Scott (geboren 1932) 274
Stephen Cook (geboren 1939) 275
Peter W. Shor (geboren 1959) 275
Kapitel 16 Die Top-Ten-Bücher zum Weiterlesen 277
Teil I: Endliche Automaten 277
Teil II: Formale Sprachen 277
Teil III: Harte Probleme 278
Teil IV: Mathematische Grundlagen 278
Teil V: Top-Ten-Teil 278
Symbolverzeichnis 281
Stichwortverzeichnis 283
