Kapitel |
Ausgabe |
Update |
Folien |
Organisatorisches |
29.09.2017 |
|
|
1 Einführung und Überblick |
03.10.2017 |
|
|
2 Rekursive Algorithmen |
09.10.2017 |
|
|
3 Zahlen- und Matrizenmultiplikation |
30.10.2017 |
08.11.2017 |
|
4 Greedy-Algorithmen und Matroide |
03.11.2017 |
|
|
5 Deterministische Komplexitätsklassen |
03.11.2017 |
|
|
6 Nichtdeterministische Komplexitätsklassen |
15.11.2017 |
20.11.2017 |
|
7 Die Klasse NP |
22.11.2017 |
28.11.2017 |
|
8 Reduktionen und Vollständigkeit |
05.12.2017 |
|
|
9 Orakel-Turingmaschinen und polynomiale Hierarchie |
18.12.2017 |
19.12.2017 |
|
10 Approximationsalgorithmen |
19.12.2017 |
09.01.2018 |
|
11 Probabilistische Algorithmen und Komplexitätsklassen |
09.01.2018 |
|
|
12 Interaktive Beweissysteme |
16.01.2018 |
23.01.2018 |
|
13 Schaltkreiskomplexität |
24.01.2018 |
30.01.2018 |
|
Anhang: Turing-Maschinen |
03.10.2017 |
|
|