392004 Übungen Theoretische Informatik (Ü) (WiSe 2005/2006)

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. Im abschließenden Teil IV werden Grundzüge der Logik im Hinblick auf ihre Rolle in informatischen Aufgabenstellungen vermittelt. Auf diese Grundvorlesung können im Hauptstudium Vorlesungen zur Logik und Rekursionstheorie, Logik-Programmierung, zum Übersetzerbau und zur Künstlichen Intelligenz aufbauen.

Requirements for participation, required level

Vorausgesetzt werden Kenntnisse der Programmierung, der naiven Mengenlehre, einfacher Logikkalküle und elementarer Beweistechniken wie des Beweisens durch Widerspruch und durch vollständige Induktion.

Bibliography

(Zur Vertiefung gedacht; genauere Angaben in der Vorlesung):

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)