Ziel der Komplexitätstheorie ist die Quantifizierung von Computerressourcen (Rechenzeit, Speicherplatz, Hardwareaufwand, Kommunikationsaufwand, ...), die zur algorithmischen Lösung konkreter Probleme bzw. von Problemklassen benötigt werden. Die Vorlesung, die sich an Studenten des Informatik- bzw. Mathematikhauptstudiums wendet und Kernvorlesung für den Bereich theoretischen Informatik ist, bietet eine fundierte Einführung in die Komplexitätstheorie. Schwerpunktmäßig wird die Bedeutung komplexitätstheoretischer Aussagen für den Algorithmenentwurf herausgearbeitet.
| Einführung | 00:53:34 |
|---|
| Probleme und Algorithmen | 01:29:36 |
|---|
| Turing Maschinen | 01:16:47 |
|---|
| Lineares Beschleunigen | 01:18:36 |
|---|
| Raumkomplexität und Platzsparen | 01:15:42 |
|---|
| Komplexitätsklassen | 00:55:36 |
|---|
| Hierarchie-Theoreme | 00:34:22 |
|---|
| Erreichbarkeitsmethode | 01:17:47 |
|---|
| Erreichbarkeitsmethode (2) | 01:02:46 |
|---|
| Reduktion und Vollständigkeit | 01:08:19 |
|---|
| Reduktion und Vollständigkeit (2) | 01:21:48 |
|---|
| Reduktion und Vollständigkeit (3) | 01:20:41 |
|---|
| NP - Vollständigkeit | 00:47:42 |
|---|
| Weitere Charakterisierungen von NP | 00:35:17 |
|---|
| Weitere NP-vollständige Probleme | 01:27:25 |
|---|
| Weitere NP-vollständige Probleme (2) | 01:10:46 |
|---|
| Weitere NP-vollständige Probleme (3) | 01:14:07 |
|---|
| Weitere NP-vollständige Probleme (4) | 01:35:26 |
|---|
| NP und coNP | 01:21:10 |
|---|
| Randomisierte Berechnungen | 01:23:13 |
|---|
| Polynomialzeithierarchie | 01:21:06 |
|---|
| Polynomialzeithierarchie (2) | 01:15:07 |
|---|
| Approximation | 01:21:32 |
|---|
| Polynomiale Schaltkreise | 01:24:24 |
|---|
| P versus NP | 01:13:33 |
|---|
| Randomisierte Berechnungen (2) | 01:16:38 |
|---|
