| 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 |
|
|