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

Basierend auf den Erfahrungen aus ihren Lehrveranstaltungen zur Theoretischen Informatik vermitteln Baier und Asteroth die klassischen Inhalte einer Einfhrungsvorlesung fr Studenten im Haupt- und Nebenfach. Auch fr Studierende mit geringen mathematischen Vorkenntnissen nachvollziehbar 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