Theoretische Informatik

1 Einleitung.- 2 Turingmaschinen, Churchsche These und Entscheidbarkeit.- 2.1 Registermaschinen und deterministische Turingmaschinen.- 2.2 Techniken zur Programmierung von Turingmaschinen.- 2.3 Simulationen zwischen Turingmaschinen und Registermaschinen.- 2.4 Universelle Turingmaschinen.- 2.5 Die Churchsche These.- 2.6 Die Unentscheidbarkeit des Halteproblems.- 2.7 Eigenschaften rekursiver und rekursiv aufzählbarer Sprachen.- 2.8 Die Unentscheidbarkeit des Postschen Korrespondenzproblems.- Übungen.- 3 Die NP-Vollständigkeitstheorie.- 3.1 Die Klasse P.- 3.2 Nichtdeterministische Turingmaschinen und die Klasse NP.- 3.3 NP-Vollständigkeit.- 3.4 Die NP-Vollständigkeit wichtiger Probleme.- 3.5 Pseudopolynomielle Algorithmen und starke NP-Vollständigkeit.- 3.6 Turing-Reduzierbarkeit, NP-harte, NP-leichte und NP-äquivalente Probleme.- 3.7 Eine Komplexitätstheorie für Approximationsalgorithmen.- 3.8 Eine Komplexitätstheorie für probabilistische Algorithmen.- 3.9 Die Struktur von NP und die polynomielle Hierarchie.- Übungen.- 4 Endliche Automaten.- 4.1 Schaltwerke und endliche Automaten.- 4.2 Die Minimierung endlicher Automaten.- 4.3 Das Pumping-Lemma für endliche Automaten.- 4.4 Nichtdeterministische endliche Automaten.- 4.5 Zwei-Wege Automaten.- 4.6 Effiziente Algorithmen für die Konstruktion endlicher Automaten und die Entscheidung von Eigenschaften regulärer Sprachen.- Übungen.- 5 Grammatiken, die Chomsky-Hierarchie und das Wortproblem.- 5.1 Grammatiken und die Chomsky-Hierarchie.- 5.2 Chomsky-O-Grammatiken und rekursiv aufzählbare Sprachen.- 5.3 Chomsky-3-Grammatiken, reguläre Sprachen und Ausdrücke, lexikalische Analyse.- 5.4 Kontextsensitive Grammatiken und Sprachen.- Übungen.- 6 Kontextfreie Grammatiken und Sprachen.- 6.1 Beispiele kontextfreierSprachen und Syntaxbäume.- 6.2 Die Chomsky-Normalform für kontextfreie Grammatiken.- 6.3 Der Cocke-Younger-Kasami Algorithmus.- 6.4 Das Pumping-Lemma und Ogden's Lemma für kontextfreie Sprachen.- 6.5 Effiziente Algorithmen für die Konstruktion kontextfreier Grammatiken und die Entscheidung von Eigenschaften kontextfreier Sprachen.- 6.6 Unentscheidbare Probleme.- 6.7 Eine inhärent mehrdeutige kontextfreie Sprache.- Übungen.- 7 Kellerautomaten und kontextfreie Sprachen.- 7.1 Die Greibach-Normalform für kontextfreie Grammatiken.- 7.2 Kellerautomaten.- 7.3 Kellerautomaten und kontextfreie Sprachen.- 7.4 Weitere effiziente Algorithmen im Zusammenhang mit kontextfreien Sprachen.- Übungen.- 8 Deterministisch kontextfreie Sprachen.- 8.1 Deterministische Kellerautomaten.- 8.2 Bottom-up Syntaxanalysealgorithmen.- 8.3 Eine weitere Charakterisierung von LR(k)-Grammatiken.- 8.4 Die Konstruktion eines LR(k)-Parsers.- 8.5 Deterministische Kellerautomaten und LR(k)-Grammatiken.- Übungen.- 9 Zusammenfassung und Testfragen.- 9.1 Zusammenfassung.- 9.2 Testfragen.- Schriftenverzeichnis.