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
- 搁别蝉辞濒耻迟颈辞苍蝉办补濒办眉濒
- Berman-Hartmanis-Vermutung und sparse Mengen
- Expander, Superkonzentratoren und der Heiratssatz
- Anwendungen der 碍辞濒尘辞驳辞谤辞惫-碍辞尘辫濒别虫颈迟盲迟
- 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