Theoretische Informatik: Eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen

Cover......Page 1
Inhaltsverzeichnis......Page 8
Vorwort......Page 12
Teil I: Berechenbarkeit......Page 14
Kapitel 1: Abstrakte Rechnermodelle......Page 18
1.1 Registermaschinen......Page 19
1.2.1 Deterministische Turingmaschinen......Page 37
1.2.2 Turing-Berechenbarkeit......Page 45
1.2.3 Mehrband-Turingmaschinen......Page 50
1.2.4 Kostenmaße für DTMs......Page 57
1.2.5 Turingmaschinen mit linksseitig beschränktem Band......Page 59
1.2.6 »Programmierung« von DTMs......Page 61
1.3 Äquivalenz der Berechenbarkeitsbegriffe......Page 64
1.3.1 Simulation von Registermaschinen durch Turingmaschinen......Page 65
1.3.2 Simulation von Turingmaschinen durch Registermaschinen......Page 69
1.3.3 Churchsche These......Page 76
1.4 Übungen......Page 78
Kapitel 2: Entscheidungsprobleme......Page 86
2.1 Entscheidbarbeit und Semientscheidbarkeit......Page 89
2.2 Das Halteproblem......Page 100
2.3 Nichtdeterminismus......Page 117
2.4 Übungen......Page 127
Teil II: Komplexität......Page 132
3.1 Zeitkomplexität......Page 138
3.2 Platzkomplexität......Page 146
3.3 Übungen......Page 150
4.1 NP-Vollständigkeit......Page 152
4.2.1 Die NP-Vollständigkeit von SAT......Page 156
4.3 Weitere NP-vollständige Probleme......Page 163
4.3.1 3SAT......Page 165
4.3.2 Das Cliquenproblem......Page 168
4.3.3 Das Rucksackproblem......Page 171
4.3.4 0/1 Integer Linear Programming......Page 176
4.4 Die Klasse coNP......Page 179
4.5 PSPACE-Vollständigkeit......Page 183
4.6 Übungen......Page 188
Teil III: Formale Sprachen......Page 194
Kapitel 5: Grammatiken......Page 196
5.1 Die Chomsky-Hierarchie......Page 197
5.2 Sprachen vom Typ 0......Page 211
5.3 Kontextsensitive Sprachen......Page 212
5.4 Das Wortproblem für Sprachen vom Typ 0 und vom Typ 1......Page 216
5.5 Übungen......Page 219
6.1 Endliche Automaten......Page 222
6.1.1 Deterministische endliche Automaten......Page 223
6.1.2 Nichtdeterministische endliche Automaten......Page 228
6.2.1 Konstruktion endlicher Automaten......Page 237
6.2.2 Algorithmen für den Nachweis von Eigenschaften regulärer Sprachen......Page 247
6.2.3 Das Pumping Lemma für reguläre Sprachen......Page 250
6.3 Reguläre Ausdrücke......Page 253
6.4.1 Der Satz von Myhill & Nerode......Page 261
6.4.2 Der Minimierungsalgorithmus......Page 268
6.5 Übungen......Page 273
7.1 Grundbegriffe......Page 278
7.2 Die Chomsky-Normalform......Page 284
7.3 Der Cocke-Younger-Kasami-Algorithmus......Page 290
7.4.1 Das Pumping Lemma für kontextfreie Sprachen......Page 293
7.4.2 Abschlusseigenschaften kontextfreier Sprachen......Page 296
7.5 Die Greibach-Normalform......Page 297
7.6 Kellerautomaten......Page 300
7.7 Übungen......Page 313
Kapitel 8: Deterministisch kontextfreie Sprachen......Page 318
8.1 Deterministische Kellerautomaten......Page 319
8.2 LR(0)-Grammatiken......Page 325
8.2.1 Die LR(0)-Bedingung......Page 326
8.2.2 Ein nichtdeterministischer LR(0)-Parser......Page 337
8.2.3 LR(0)-Items......Page 341
8.2.4 Berechnung der Itemmengen......Page 350
8.2.5 DKAs für LR(0)-Grammatiken......Page 360
8.3.1 Die LR(k)-Bedingung......Page 368
8.3.2 LR(k)-Items......Page 371
8.3.3 Die Parsetabellen......Page 375
8.3.4 Der LR(k)-Parser......Page 379
8.4 Übungen......Page 381
Kapitel 9: Entscheidungsprobleme für formale Sprachen......Page 382
9.1 Das Postsche Korrespondenzproblem......Page 383
9.2 Unentscheidungsergebnisse für formale Sprachen......Page 393
9.2.1 Unentscheidbarkeitsergebnisse für deterministisch kontextfreie Sprachen......Page 394
9.2.2 Unentscheidbarkeitsergebnisse für kontextfreie Sprachen......Page 398
9.2.3 Unentscheidbarkeitsergebnisse für kontextsensitive Sprachen......Page 400
9.3 »Schwierige« Probleme für reguläre Sprachen......Page 401
9.4 Übungen......Page 404
Kapitel 10: Zusammenfassung......Page 406
Anhang A: Die Güte von Algorithmen......Page 408
Anhang B: Aussagenlogik......Page 410
Anhang C: Formale Sprachen......Page 414
Literaturverzeichnis......Page 416
Register......Page 420