Modul Theoretische Informatik 1, Informatik (Bachelor) (SPO 5)
Die Studierenden erlernen die prinzipiellen Beschränkungen heutiger Computer bei der Lösung von wichtigen Problemen. Auf der Basis mathematisch exakter Beweise erfassen sie hierfür wichtige Gebiete der Theoretischen Informatik. Sie klassifizieren formale Sprachen mit Hilfe der sog. Chomsky-Hierarchie und erkennen dadurch ihre algorithmische Komplexität. Weiterhin erfassen die Studierenden die Berechnungskraft gängiger Rechnermodelle durch endliche Automaten und können mit exakten logischen Argumenten deren Grenzen aufzeigen. Diverse Probleme erkennen sie von vorneherein als durch Computer unlösbare Aufgabenstellungen. Die vorgestellten Ergebnisse können die Studierenden durch den sicheren Umgang mit verschiedenen Beweistechniken belegen.
Die Lehrveranstaltung führt in die Theorie der formalen Sprachen ein. Das Ziel ist die Vermittlung der Chomsky-Hierarchie als ein Stufenmodell unterschiedlich komplexer Sprachen. Weiterhin werden endliche Automaten als Repräsentanten heutiger Computer vorgestellt und ihre Beschränkungen aufgezeigt. Ein weiteres Lernziel ist die sichere Anwendung verschiedener Beweistechniken.
Die Lehrveranstaltung umfasst unter anderem die folgenden Gebiete der theoretischen Informatik: Aussagenlogik, formale Sprachen, Beweistechniken, das O-Kalkül, endliche Automaten, reguläre Sprachen und Ausdrücke, die Chomsky-Hierarchie, das Pumping-Lemma für reguläre und kontextfreie Sprachen sowie die Minimierung endlicher Automaten nach dem Satz von Myhill-Nerode. Weiterhin werden Kellerautomaten, der CYK-Algorithmus sowie Abgeschlossenheitseigenschaften von kontextfreien Sprachen besprochen.
- Tafelanschrieb
- Skript
- Musterlösungen für alle Übungsaufgaben
- D. W. Hoffmann: Theoretische Informatik, 3. Auflage. Hanser, 2015.
- D. Sipser: Introduction to the Theory of Computation, 3rd edition. Cengage Learning, Inc., 2012.
Die Lehrveranstaltung findet als reine Vorlesung statt. Zahlreiche Übungsaufgaben vertiefen die vermittelten Gebiete und werden in evtl. zusätzlich angebotenen Tutorien diskutiert.