course: Theoretische Informatik

number:
500004
teaching methods:
lecture with tutorials
responsible person:
Prof. Dr. Eike Kiltz
lecturer:
Prof. Dr. Eike Kiltz (Mathematik)
language:
german
HWS:
6
CP:
8
offered in:
winter term

goals

Nach dem erfolgreichen Abschluss des Moduls - beherrschen die Studierenden den professionellen Umgang mit Berechnungsmodellen und ihren Beziehungen zu Sprachklassen. Dazu gehört die intellektuelle und methodische Fähigkeit, den Nachweis der Zugehörigkeit bzw. Nichtzugehörigkeit zu einer solchen Klasse zu führen. - Durch Einüben von Beweistechniken wie wechselseitige Simulation oder berechenbare Reduktionen ist die Einsicht gereift, dass an der Oberfläche verschieden aussehende Konzepte im Kern identisch sein können. Zudem erlaubt dies den Studierenden, neue Anwendungsprobleme selbständig zu klassifizieren. - erlernen die Studierenden ein einfach handhabbares Rechnermodell, die Turingmaschine, das ihnen fortan als Abstraktion für alle möglichen Rechner dient. - erlangen die Studierenden fundamentale Einsichten, welche Probleme mit Hilfe von Rechnern effizient entschieden, mit Hilfe effizient entschieden, entschieden, zum Teil entschieden oder prinzipiell nicht entschieden werden können. Dadurch erlangen Sie ein tieferes Verständnis von Komplexität von Berechnungsproblemen.

content

Die Vorlesung gibt einen systematischen Überblick über die folgenden Themengebiete: - Endliche Automaten und reguläre Ausdrücke - Kellerautomaten und kontextfreie Grammatiken - Turing-Maschinen und Entscheidbarkeit - Nichtdeterminismus und NP-Vollständigkeitstheorie