Übung zu Komplexitätstheorie
Ankündigungen:
- Die Übung am 23. Mai fällt aus.
- Die erste Übung; findet am 25. April statt.
Allgemeine Informationen:
-
Übungsleitung:
Chris Pinkau -
Zeit und Ort:
Do, 12:15–13:45, Raum 03.11.018 -
Sprechstunde:
Di, 13:00–14:00, Raum 03.09.057, und nach Vereinbarung.
Übungsblätter und Lösungen:
- Übungsblatt 1 – Lösungsblatt 1
- Übungsblatt 2 – Lösungsblatt 2
- Übungsblatt 3 – Lösungsblatt 3
- Übungsblatt 4 – Lösungsblatt 4
- Übungsblatt 5 – Lösungsblatt 5
- Übungsblatt 6 – Lösungsblatt 6
- Übungsblatt 7 – Lösungsblatt 7
- Übungsblatt 8 – Lösungsblatt 8
- Übungsblatt 9 – Lösungsblatt 9
- Übungsblatt 10 – Lösungsblatt 10
- Übungsblatt 11 – Lösungsblatt 11
- Lösungen der Klausur
Sonstiges:
- Der Beweis vom Satz von Baker, Gill, Solovay etwas anders erklärt
- Big picture: Überblick einiger bekannten Komplexitätsklassen (wird fortlaufend aktualisiert)
- Überblick der wichtigsten Reduktionen
- Googles doodle für Alan Turing
- Theoretical Computer Science Cheat Sheet
- The On-Line Encyclopedia of Integer Sequences
- History of Mathematics