Theoretische Informatik
(BSc Mod 9b: BSc Modul 9b, BSc Modul 9b; BSc NF 1: BSc NF
Modul 1, BSc NF Modul 1 (9 CP)
| Dozent | Zeit | Raum | Erstmals am |
|---|---|---|---|
| Prof. Eike Kiltz | montags, 10:15-11:45 Uhr | HZO 90 | 17.10.2016 |
| Prof. Eike Kiltz | mittwochs 10:15-11:45 Uhr | HNC 20 | 19.10.2016 |
| Dozent | Zeit | Raum | Erstmals am |
|---|---|---|---|
| Christoph Ries | dienstags, 14:15-15:45 Uhr | NB 5/99 | 25.10.2016 |
| Benedikt Auerbach (Teil I) und Felix Heuer (Teil II) | mittwochs, 08:30-10:00 Uhr | NA 3/99 | 26.10.2016 |
| Christoph Ries | mittwochs, 14:15-15:45 Uhr | NA 2/24 | 26.10.2016 |
Voraussetzungen
Nützlich (aber nicht zwingend erforderlich) sind elementare Grundkenntnisse in Informatik und Diskreter Mathematik sowie Vertrautheit mit mindestens einer Programmiersprache.
Kommentar
Die Vorlesung richtet sich an Studierende der Mathematik, der Angewandten Informatik und (als Wahlpflichtfach) an Studierende der IT-Sicherheit. Sie liefert eine Einführung in die Theorie der Grammatiken (insbesondere kontextfreie Grammatiken) und Automaten (endlicher Automat, Kellerautomat, Turing-Maschine). Sie gibt ferner einen Einblick in die Berechenbarkeits- und NP-Vollständigkeitstheorie, wo es um die Frage geht, welche Rechenprobleme (überhaupt bzw. mit vertretbarem Aufwand) gelöst werden können. Es wird sich zeigen, dass es inhärent schwere Probleme gibt, die von Rechnern nicht zufriedenstellend gelöst werden können.
In der Vorlesung ergeben sich fundamentale Einsichten zum Verhältnis zwischen Automaten und Grammatiken und zum Verhältnis von Determinismus und Nicht-Determinismus. Durch Einüben von Techniken wie wechselseitige Simulation oder (polynomiell) berechenbare Reduktionen soll die Einsicht reifen, dass an der Oberfläche verschieden aussehende Konzepte im Kern identisch sein können. Ziel ist zudem ein tieferes Verständnis von Komplexität. Auf
den unteren Ebenen der sogenannten Chomsky-Hierarchie finden sich effizient lösbare Anwendungsprobleme der Textmanipulation und der Textanalyse. Auf den oberen Ebenen trifft man hingegen auf das Phänomen der inhärenten Härte (oder gar Unentscheidbarkeit) eines Problems.
Literatur
Die Vorlesung orientiert sich an dem Buch "Theoretische Informatik - kurzgefasst" von Uwe Schöning (Spektrum, 5. Auflage, 2009). Weitere Literaturvorschläge erfolgen in der ersten Vorlesungsstunde.
Moodle Link
Link zum Moodle. Dass Passwort wird in der Vorlesung bekannt gegeben.