Beleg-Nr.: 39 20 03
Veranstalter: Wachsmuth
Arbeitsgruppe: Wissensbasierte Systeme (Künstliche Intelligenz)
SWS: 4
Termin: Di 10-12, Do 10-12
Raum: H10
Beginn: 16.04.96
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 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.
Vorausgesetzt werden Kenntnisse der Programmierung, der naiven Mengenlehre,
einfacher Logikkalküle und elementarer Beweistechniken wie des Beweisens
durch Widerspruch und durch vollständige Induktion.
Literatur (genauere Angaben in der Vorlesung):