1
Theoretical Computer Science
Emil VinuETH Zürich
Hi, I'm Emil, TA-ing TCS in HS26.
I aim to keep this website exhaustive, i.e. containing literally everything you will need to prepare for midterm, endterm or Sessionsprüfung.
In case you have any questions, feel free to hit me up!
- When
- Wednesdays, 16:15 – 18:00
- Where
- HG D 3.1
- Replacement
- Tuesday 29 Sept, 14:00 – 16:00
- Where
- LFW B 2
Sessions
2
3
4
5
6
Midterm-Vorbereitung
Aufgaben aus alten Prüfungen, typische Fehler, offene Fragen.
7
Kolmogorov-Komplexität
Kolmogorov-Komplexität, obere Schranken für K(x), zufällige Wörter.
8
Reduktionen
EE- und R-Reduktionen zwischen Halte-, Universal- und Diagonalsprache.
9
Zeit- und Platzkomplexität
Zeit- und platzkonstruierbare Funktionen, Komplexitätsmasse.
10
Satz von Rice und NP-Vollständigkeit
Satz von Rice, seine Grenzen, NP-Vollständigkeit ausgehend von SAT.
11
Polynomzeit-Reduktionen
Polynomzeit-Reduktionen auf Vertex-Cover, Set-Cover und E3SAT.
12
Grammatiken und Chomsky-Hierarchie
Reguläre und allgemeine Grammatiken, erzeugte Sprache, Chomsky-Hierarchie.
13
Kontextfreie Sprachen und Kellerautomaten
Pumping-Lemma für kontextfreie Sprachen, Kellerautomaten.