392003 Grundlagen der Theoretischen Informatik (V) (WiSe 2014/2015)

Zentrale Gegenstände der Informatik sind Algorithmen und ihre sprachlichen Realisierungen als Programme sowie Problemlösungen durch Berechnungsverfahren. Die Vorlesung behandelt Grundlagen der theoretischen Informatik, mit denen zunächst eine Fundierung von Programmiersprachen gelegt werden soll. Im Teil I geht es um formale Sprachen und Grammatiken bis hin zu einer Typisierung von Sprachklassen nach ihrer Leistungsfähigkeit (Chomsky-Hierarchie). Unter dem Gesichtspunkt der Spracherkennung betrachtet der Teil II formale Sprachen und Automaten (deterministische und nichtdeterministische endliche Automaten, Kellerautomaten, Turing-Maschinen und RAM-Maschinen). Im Teil III folgen Einführungen in die Berechenbarkeitstheorie, die sich mit grundsätzlichen Möglichkeiten und Grenzen der Algorithmisierbarkeit befasst, und in die Komplexitätstheorie, die untersucht, mit welchem Aufwand an Berechnungsressourcen (Rechenzeit, Speicherplatz) algorithmische Aufgaben gelöst werden können.

Requirements for participation, required level

Kenntnisse A und D waeren wuenschenswert

Bibliography

Es wird ein Skript im ekVV zur Verfuegung gestellt.

(Zur Vertiefung gedacht):
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley, 2002 (zur Vertiefung)
Kelly, J.: Logik im Klartext, Pearson Studium, 2003 (viele Beispiele!)
Lewis, H.R., Papadimitriou, C.H.: Elements of the theory of computation. Englewood Cliffs, N.J.: Prentice Hall, 1981 (zur Vertiefung)
Schöning, U.: Theoretische Informatik kurz gefaßt. (2. Auflage) Heidelberg: Spektrum Akademische Verlag, 1995
Schöning, U.: Logik für Informatiker (4. Aufl.). Heidelberg: Spektrum Akdademischer Verlag, 1995 (in Auszügen)
Sipser, M.: Introduction to the theory of computation. PWS Publishing Company, 1996 (wird wegen guter Didaktik gelobt)
Wegener, I.: Kompendium Theoretische Informatik - eine Ideensammlung. Stuttgart: Teubner, 1996 (zur Ergänzung)