392003 Theoretische Informatik (V) (SoSe 2002)

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 befaßt, und in die Komplexitätstheorie, die untersucht, mit welchem Aufwand an Berechnungsressourcen (Rechenzeit, Speicherplatz) algorithmische Aufgaben gelöst werden können. Im abschliessenden 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

(genauere Angaben in der Vorlesung):

• 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)

External comments page

http://www.techfak.uni-bielefeld.de/techfak/ags/wbski/lehre/S02.html#392003