Highlights der Theoretischen Informatik
Aktuelles
[05.09.2018]
Vorlesungsbeginn ist am Dienstag, 16.10.2018.
Inhalt
Die folgenden Themen wurden behandelt (die Liste wird wöchentlich ergänzt):
- Perzeptron-Konzergenztheorem
- zehntes Hilbertsches Problem
- Quantorenelimination
- Orakel mit P<>NP und QBF
- Kanalcodiertheorem von Shannon
- PARITY liegt nicht in AC0
- untere Schranke für monotone Schaltkreise
- Resolutionskalkül
- Berman-Hartmanis-Vermutung und sparse Mengen
- Expander, Superkonzentratoren und der Heiratssatz
- Anwendungen der Kolmogorov-Komplexität
- Diskrete Fouriertransformation und FFT
- Pebble Game
- Branching-Programme beschränkter Breite und NC1
- Zippel-Schwartz-Lemma und Branching-Programme
- Diagonalisierung in NP
Literatur
U. Schöning: Perlen der Theoretischen Informatik.
Dozent
Vorlesungszeiten
Dienstag 12:15 - 13:45 in O27/121
Mittwoch 12:15 - 13:45 in O27/2201