Course Schedule
Lehrveranstaltungen
Theoretische Informatik (Vorlesung)
Dozent/in: Ulrich
Termin:
wöchentlich | Montag | 10:00 - 11:30 | 12.10.2015 - 29.01.2016 | W HS 3
wöchentlich | Donnerstag | 12:15 - 13:45 | 12.10.2015 - 29.01.2016 | C 14.006 Seminarraum
Einzeltermin | Mo, 16.11.2015, 11:45 - Mo, 16.11.2015, 13:15 | W HS 3 | Nachholtermin
Einzeltermin | Mo, 30.11.2015, 12:00 - Mo, 30.11.2015, 13:30 | W HS 3 | Nachholtermin
Inhalt: Das Modul vermittelt Grundkenntnisse aus folgenden Teilgebieten: Grundlagen · Modelle der Berechenbarkeit (Turingmaschinen, Registermaschinen), Churchsche These · Entscheidbarkeit, Aufzählbarkeit und Grenzen der Berechenbarkeit Komplexität von Algorithmen · Zeitkomplexität, Platzkomplexität · Das P-NP-Problem · Theorie der NP-Vollständigkeit · Probabilistische Berechnungmodelle und Komplexitätsklassen, Ausblicke Elemente der Theorie Formaler Sprachen und der Automatentheorie · Chomsky-Hierarchie mit Schwerpunkt auf kontextsensitive, kontextfreie und reguläre Sprachen · Verbindung der Sprachklassen mit speziellen Automatentypen · Entscheidungsprobleme für formale Sprachen Aktuelle Themen der Theoretischen Informatik