392003 Theoretische Informatik (V) (SoSe 2001)

Um ein gegebenes Problem mit dem Computer lösen zu können, sind zwei Schritte notwendig: (a) das "Erfinden" eines Berechnungsverfahrens und (b) die sprachliche Realisierung als Programm.

Die Vorlesung behandelt die dazu erforderlichen theoretischen Grundlagen, die eine zentrale Stellung innerhalb der theoretischen Informatik haben. In 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). In Teil III folgen
Einführungen in die Berechenbarkeitstheorie, die sich mit grundsätzlichen Möglichkeiten und Grenzen der Algorithmisierbarkeit befaßt, und in die Komplexitätstheorie, die untersucht, mit welchem Aufwand an Berechnungsressourcen (Rechenzeit, Speicherplatz) algorithmische Aufgaben gelöst werden können. In Teil IV werden Grundzüge der Logik vermittelt. Auf diesen Grundlagen bauen im Hauptstudium Vorlesungen zur Logik und Rekursionstheorie, Logik-Programmierung, zum Übersetzerbau und zur Künstlichen Intelligenz auf.

Vorausgesetzt werden neben mathematischem Grundlagenwissen auch Kenntnisse in der Programmierung.

Literatur:

• Schöning, U.: Theoretische Informatik kurz gefaßt. (2. Auflage) Mannheim: BI Wissenschaftsverlag, 1995
• Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Reading, Mass.: Addison-Wesley, 1979; dt.: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Bonn: Addison-Wesley, 1988 (zur Vertiefung)
• Lewis, H.R., Papadimitriou, C.H.: Elements of the theory of computation. Englewood Cliffs, N.J.: Prentice Hall, 1981 (zur Vertiefung)
• Schöning, U.: Logik für Informatiker (4. Aufl.). Mannheim: BI Wissenschaftsverlag, 1989 (in Auszügen)

Externe Kommentarseite

http://www.techfak.uni-bielefeld.de/techfak/ags/ni/lehre/S01.html#392003