Grundlagen der Theoretischen Informatik

Description

Dieses Lehrbuch liefert eine verständliche, aber dennoch kompakte Einführung in die Theoretische Informatik. Die behandelten Themen bilden das Fundament für weiterführende Themen in der Theoretischen Informatik und sind zudem grundlegend für das formale Arbeiten in der gesamten Informatik. Durch eine Vielzahl von Aufgaben mit Lösungen eignet sich dieses Buch sehr gut zum Selbststudium. Vorwort Literatur Inhaltsverzeichnis Abbildungsverzeichnis 1 Einführung und formale Sprachen 1.1 Codierung von Problemen 1.2 Entscheidungsprobleme 1.3 Operationen auf Wörtern und Sprachen 1.4 Übersicht Berechnungsmodelle 1.5 Grundbegriffe 1.5.1 Mengen 1.5.2 Tupel 1.5.3 Relationen und Funktionen 1.5.4 Rechnen mit Wahrheitswerten 1.5.5 Beweistechniken 1.5.6 Asymptotische Abschätzung 1.5.7 Graphen 1.6 Lösungsvorschläge der Selbsttestaufgaben zum Kapitel 1 1.7 Übungsaufgaben zum Kapitel 1 2 Reguläre Sprachen 2.1 Der deterministische endliche Automat 2.2 Nichtdeterministische endliche Automaten 2.3 Abschlusseigenschaften regulärer Sprachen 2.4 Minimierung von DEAs 2.4.1 Minimierung über den kollabierten Automaten 2.4.2 Minimierung durch den Spiegelautomaten 2.5 Reguläre Ausdrücke 2.6 Nachweis von Nichtregularität 2.7 Bibliografische Anmerkungen 2.8 Lösungsvorschläge der Selbsttestaufgaben zum Kapitel 2 2.9 Übungsaufgaben zum Kapitel 2 2.10 Lösungsvorschläge für die Übungsaufgaben zum Kapitel 2 Literatur 3 Kontextfreie Sprachen 3.1 Kellerautomaten 3.2 Kontextfreie Grammatiken 3.2.1 Definitionen und Konzept 3.2.2 Äquivalenz der Modelle Kellerautomat und kontextfreie Grammatik 3.2.3 Grammatiken für reguläre Sprachen 3.3 Chomsky-Normalform 3.4 Der CYK-Algorithmus 3.5 Das kontextfreie Pumpinglemma 3.6 Abschlusseigenschaften kontextfreier Sprachen 3.7 Deterministische Kellerautomaten 3.8 Der Satz von Chomsky-Schützenberger 3.9 Bibliografische Anmerkungen 3.10 Lösungsvorschläge der Selbsttestaufgaben zum Kapitel3 3.11 Übungsaufgaben zum Kapitel3 3.12 Lösungsvorschläge für die Übungsaufgaben zum Kapitel3 Literatur 4 Entscheidbare und erkennbare Sprachen 4.1 Das Modell Turingmaschine 4.2 Varianten der Turingmaschine 4.2.1 Mehrband-Turingmaschine 4.2.2 Halbband-Turingmaschine und LBA 4.2.3 Nichtdeterministische Turingmaschine 4.2.4 Turingmaschinen für Funktionen 4.3 Die Church-Turing-These 4.4 Aufzählbare Sprachen 4.5 Co-aufzählbare Sprachen 4.6 Die universelle Turingmaschine 4.6.1 Codierung von Turingmaschinen 4.6.2 Simulation von Turingmaschinen 4.7 Wichtige Sprachen mit Bezug zu Berechnungsmodellen 4.8 Abschlusseigenschaften der entscheidbaren und aufzählbarenSprachen 4.9 Bibliografische Anmerkungen 4.10 Lösungsvorschläge der Selbsttestaufgaben zum Kapitel4 4.11 Übungsaufgaben zum Kapitel4 4.12 Lösungsvorschläge für die Übungsaufgaben zum Kapitel4 Literatur 5 Unentscheidbare Sprachen 5.1 Existenz von nichtaufzählbaren Sprachen 5.2 Konstruktion von nichtaufzählbaren Sprachen 5.3 Entscheidbarkeit des universellen Wortproblems 5.4 Das Konzept der Reduktion 5.5 Der Satz von Rice 5.6 Das Äquivalenzproblem für Turingmaschinen 5.7 Reduktionen über Berechnungspfade 5.8 Das postsche Korrespondenzproblem 5.8.1 Problembeschreibung 5.8.2 Nachweis der Unentscheidbarkeit 5.8.3 Anwendungen 5.9 Der Rekursionssatz 5.9.1 Quines 5.9.2 Rekursionssatz 5.9.3 Anwendungen des Rekursionssatzes 5.10 Entscheidbarkeit logischer Theorien 5.10.1 Eine entscheidbare Theorie 5.10.2 Eine unentscheidbare Theorie 5.11 Gödels Unvollständigkeitssätze 5.12 Bibliografische Anmerkungen 5.13 Lösungsvorschläge der Selbsttestaufgaben zum Kapitel 5 5.14 Übungsaufgaben zum Kapitel 5 5.15 Lösungsvorschläge für die Übungsaufgaben zum Kapitel 5 Literatur 6 Komplexitätstheorie 6.1 Definition von Zeitkomplexitätsklassen 6.2 Die Klasse P 6.3 Die Klasse NP 6.3.1 Nichtdeterministische Zeitkomplexitätsklassen 6.3.2 Das P vs. NP-Problem 6.4 Analyse von Algorithmen 6.5 NP-Vollständigkeit 6.5.1 Polynomielle Reduktionen 6.5.2 Definition NP-Vollständigkeit 6.5.3 Das Erfüllbarkeitsproblem 6.5.4 Variationen des Erfüllbarkeitsproblems 6.5.5 NP-vollständige Graphenprobleme 6.5.6 NP-vollständige arithmetische Probleme 6.6 Platzkomplexität 6.6.1 Der Satz von Savitch 6.6.2 Der Satz von Immerman und Szelepcsényi 6.7 Bibliografische Anmerkungen 6.8 Lösungsvorschläge der Selbsttestaufgaben zum Kapitel 6 6.9 Übungsaufgaben zum Kapitel 6 6.10 Lösungsvorschläge für die Übungsaufgaben zum Kapitel 6 Literatur Stichwortverzeichnis