Theoretische Informatik
Crypto RUB » Lehre (German) » Wintersemester 2016/2017

Theoretische Informatik

(BSc Mod 9b: BSc Modul 9b, BSc Modul 9b; BSc NF 1: BSc NF
Modul 1, BSc NF Modul 1 (9 CP)

Vorlesung
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
Übungen
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.