Home Page Institute
of Computer Science
Vorlesung Automaten und Berechenbarkeit
Übersicht
Inhalt der Vorlesung
In dieser Vorlesung zur Theoretischen Informatik werden Fragen wie die
folgenden untersucht:
- Wie kann man Algorithmen finden und auf ihre Leistung untersuchen?
- Kann der algorithmische Aufwand zur Lösung eines Problems
minimiert werden?
- Gibt es Probleme, die sich nicht algorithmisch lösen lassen?
- Welchen prinzipiellen Anforderungen sollen Programmiersprachen genügen?
- Welche Sprachklassen lassen sich durch welche Automatentypen erkennen?
1. Endliche Automaten
- Nichtdeterministische Automaten
- Deterministische Automaten, Determinisierung
nichtdeterministischer Automaten
- Minimierung endlicher Automaten, Nerode-Rechtskongruenz
- Reguläre Sprachen, Satz von Kleene
- Automaten mit Ausgabe, sequentielle Wortfunktionen
2. Formale Sprachen
- Sprachen und Grammatiken, kontextfreie Grammatiken
- Chomsky-Normalform kontextfreier Grammatiken, CYK-Algorithmus
- Ableitungsbäume, Pumping-Lemma
- Pushdown-Automaten (Kellerautomaten), Äquivalenzsatz
- Deterministisch kontextfreie Sprachen
- Chomsky-Hierarchie formaler Sprachen
3. Berechenbarkeitstheorie
- Turingmaschinen, Determinismus und Nichtdeterminismus
- Rekursive Funktionen
- Entscheidbarkeit und Unentscheidbarkeit
4. Komplexität von Berechnungen
- Zeit- und Raumkomplexität bei Turingmaschinen
- Bandkompression und lineare Beschleunigung
- Polynomialzeitberechenbarkeit
- NP-Vollständigkeit, P = NP?-Problem
Zur Vorlesung gibt es kein Skript, lediglich die Folien.
Literatur
Literatur zur Vorlesung finden Sie z.B. im OPAC unter
Automatentheorie
Formale Sprachen Komplexitätstheorie.
In unserer Bibliothek (Heide-Süd) sind die folgenden Bücher
mehrfach vorhanden:
- K. W. Wagner. Lehrbuch der Theoretischen Informatik. Springer-Verlag
Berlin 1994, 2003
- I. Wegener. Theoretische Informatik. B.G.Teubner Stuttgart 1993
- I. Wegener. Kompendium Theoretische Informatik. B.G.Teubner
Stuttgart 1996
- J. E. Hopcroft, J. D. Ullman. Einführung in die Automatentheorie,
Formale Sprachen und Komplexitätstheorie. Addison-Wesley
bzw. Oldenbourg 1988-2000
- J. E. Hopcroft, J. D. Ullman, Motwani. Einführung in die
Automatentheorie, Formale Sprachen und Komplexitätstheorie
(bzw. Berechenbarkeit). Pearson 2001-2011 (auch in Englisch:
Introduction to automata theory, languages, and computation)
- G. Goos, W. Zimmmermann: Vorlesungen über Informatik.
Bd. 3: Berechenbarkeit, formale Sprachen, Spezifikationen. Springer
1997
- D. Wätjen. Theoretische Informatik. Oldenbourg 1994
- U. Schöning. Theoretische Informatik kurz gefasst. Spektrum 1992-2001
L. Staiger, R. Winter,
10.04.2012