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 Master-Studenten der Studiengänge IT Systems Engineering, Informatik und Mathematik wendet, bietet eine fundierte Einführung in die Komplexitätstheorie. Schwerpunktmäßig wird die Bedeutung komplexitätstheoretischer Aussagen für den Algorithmenentwurf herausgearbeitet.
| Einführung und Inhalt | 00:51:59 | |
|---|---|---|
| Was ist Komplexitätstheorie? | 00:21:26 | |
| Grundrichtungen in der Komplexitätstheorie | 00:02:18 | |
| Hauptaufgabe der Komplexitätstheorie | 00:06:58 | |
| Welche Ergebnisse beingt die Komplexitätstheorie? | 00:05:06 | |
| Zentrale Herausforderung für Komplexitätstheorie | 00:10:53 | |
| Leistungserfassung und Übung | 00:05:18 |
| Probleme und Algorithmen | 01:16:55 | |
|---|---|---|
| REACHABILITY Grapherreichbarkeit | 00:14:16 | |
| Algorithmus für Grapherreichbarkeit | 00:12:01 | |
| O-Notation | 00:13:39 | |
| Polynomialzeit-Algorithmen | 00:06:40 | |
| MAX FLOW - Flüsse in Netzwerken | 00:11:29 | |
| Reduktionstechniken | 00:07:00 | |
| TSP - Rundreiseproblem | 00:11:50 |
| Turing Maschinen | 01:33:51 | |
|---|---|---|
| Einführung | 00:03:28 | |
| Erweiterte Church'sche These | 00:09:19 | |
| Turing Maschinen - Grundidee | 00:06:45 | |
| K-Band Turing Maschine | 00:20:11 | |
| Konfiguration einer K-Band TM | 00:18:20 | |
| Zeitkomplexität | 00:08:14 | |
| Leistungsvergleich von Turing Maschinen | 00:11:17 | |
| Simulation der Startkonfiguration | 00:16:17 |
| Lineares Beschleunigen | 00:51:32 | |
|---|---|---|
| Wiederholung | 00:05:12 | |
| Speedup Theorem | 00:05:20 | |
| Speedup Theorem - Beweisidee | 00:16:37 | |
| Arbeit mit m-Symbolen | 00:16:43 | |
| Diskussion des Speedup Theorems | 00:07:40 |
| Raumkomplexität und Platzsparen | 00:57:14 | |
|---|---|---|
| Einführung | 00:02:59 | |
| Begriffsbestimmung | 00:12:03 | |
| Beispiel: Raumbedarf für Palindrome | 00:11:24 | |
| Turingmaschinen mit Ein- und Ausgabe | 00:13:41 | |
| Raumkomplexität | 00:11:11 | |
| Platzsparen | 00:05:56 |
| Nichtdeterministische Turing Maschinen | 01:08:46 | |
|---|---|---|
| Einführung | 00:05:07 | |
| NTM - Definitionen | 00:14:44 | |
| Nichtdeterministische Berechnungen | 00:07:59 | |
| Nichtdeterministische Komplexität | 00:07:55 | |
| Rundreiseproblem - TSP(D) | 00:13:31 | |
| Nichtdeterministische und probabilistische Turing Maschinen | 00:04:49 | |
| Nichtdeterministische und deterministische Turing Maschinen | 00:14:41 |
| Komplexitätsklassen | 00:41:52 | |
|---|---|---|
| Einführung | 00:05:10 | |
| Schrankenfunktionen | 00:12:36 | |
| Präzise Turing Maschinen | 00:08:32 | |
| Wichtige Komplexitätsklassen | 00:15:34 |
| Hierarchie-Theoreme | 00:33:29 | |
|---|---|---|
| Zeit-Hierarchie-Theorem | 00:12:24 | |
| Beweis durch Diagonalisierung | 00:17:46 | |
| Bemerkung | 00:03:19 |
| Erreichbarkeitsmethode 1/2 | 00:56:39 | |
|---|---|---|
| NTIME vs. SPACE | 00:12:51 | |
| NSPACE vs. TIME | 00:14:24 | |
| Zwischenbilanz | 00:06:39 | |
| Satz von Savitch | 00:22:45 |
| Erreichbarkeitsmethode 2/2 | 00:50:58 | |
|---|---|---|
| Wiederholung Erreichbarkeitsmethode | 00:06:35 | |
| Satz von Immerman Szelepcsenyi | 00:09:22 | |
| Beweis des Satzes | 00:18:45 | |
| Analyse des Satzes | 00:06:22 | |
| NSPACE vs. coNSPACE | 00:09:54 |
| Reduktion und Vollständigkeit (1) | 01:07:03 | |
|---|---|---|
| Einführung | 00:12:15 | |
| Grundidee der Reduktion | 00:03:41 | |
| Logspace-Reduktion | 00:07:17 | |
| HAMILTON PATH und SAT | 00:20:00 | |
| Beweis | 00:23:50 |
| Reduktion und Vollständigkeit (2) | 00:55:20 | |
|---|---|---|
| Grundidee der Reduktion | 00:04:13 | |
| Logspace-Reduktion | 00:23:06 | |
| Reduktion durch Verallgemeinerung | 00:14:12 | |
| Komposition von Reduktionen | 00:13:49 |
| Reduktion und Vollständigkeit (3) | 00:57:57 | |
|---|---|---|
| Einführung | 00:03:25 | |
| K-Vollständigkeit | 00:11:14 | |
| Berechnungstabellen-Methode | 00:13:40 | |
| P-Vollständigkeit von CIRCUIT VALUE | 00:13:54 | |
| Beweisen | 00:11:38 | |
| P-Vollständigkeit von MONTONE CICUIT VALUE | 00:04:06 |
| NP-Vollständigkeit | 00:35:02 | |
|---|---|---|
| Erinnerung | 00:14:14 | |
| Cook's Theorem | 00:20:48 |
| Weitere Charakterisierungen von NP | 00:19:30 | |
|---|---|---|
| Polynomial balancierte Relation | 00:04:49 | |
| Charakteriesierung von NP mittels Relation | 00:09:13 | |
| Polynomiale Zeugnisse | 00:05:28 |
| Weitere NP vollständige Probleme (1) | 00:58:00 | |
|---|---|---|
| Erinnerung | 00:09:47 | |
| NP-vollständig SAT-Varianten | 00:11:26 | |
| 2-SAT gehört zu P | 00:21:00 | |
| NAE-SAT ist NP-vollständig | 00:02:48 | |
| MAX-2-SAT ist NP-vollständig | 00:11:09 |
| Weitere NP-vollständige Probleme (2) | 00:54:32 | |
|---|---|---|
| Erinnerung | 00:08:38 | |
| INDEPENDENT SET Problem | 00:18:17 | |
| CLIQUE und NODE COVER | 00:05:09 | |
| Schnitt-Probleme | 00:14:34 | |
| MIN CUT | 00:07:54 |
| Weitere NP-vollständige Probleme (3) | 01:08:55 | |
|---|---|---|
| Erinnerung | 00:06:53 | |
| Wege-Probleme | 00:10:17 | |
| Färbungsprobleme | 00:17:17 | |
| Matching | 00:19:59 | |
| Errreichen des Matchings | 00:14:29 |
| Weitere NP-vollständige Probleme (4) | 01:26:03 | |
|---|---|---|
| Erinnerung | 00:12:38 | |
| SET COVER | 00:10:29 | |
| INTEGER PROGRAMMING | 00:18:02 | |
| KNAPSACK | 00:21:44 | |
| BIN PACKING | 00:14:43 | |
| Behauptung | 00:08:27 |
| NP und coNP | 01:01:17 | |
|---|---|---|
| Einführung | 00:09:51 | |
| coNP-vollständige Probleme | 00:06:27 | |
| NP = coNP ? | 00:15:46 | |
| Pratt's Theorem | 00:19:15 | |
| PRIMES gehört zu P | 00:09:58 |
| Randomisierte Berechnungen (1) | 01:06:40 | |
|---|---|---|
| Einführung | 00:02:23 | |
| Symbolische Determinante | 00:19:11 | |
| Determinanze = 0 ? | 00:04:47 | |
| Abschätzung der Zahl der Nullstellen | 00:12:49 | |
| Randomisierter Algorithmus für PERFECT MATCHING | 00:09:24 | |
| Random Walks | 00:04:24 | |
| Fermat Test | 00:13:42 |
| Randomisierte Berechnungen (2) | 00:40:55 | |
|---|---|---|
| Wiederholung Randomisierte Berechnungen | 00:07:11 | |
| Probabilistische Turing Maschinen | 00:07:03 | |
| Die Komplexitätsklasse PP | 00:08:39 | |
| Die Komplexitätsklasse BPP | 00:04:44 | |
| Die Komplexitätsklasse RP | 00:06:38 | |
| Die Komplexitätsklasse ZPP | 00:03:12 | |
| Landkarte der probabilistischen Kömplexitätsklassen | 00:03:28 |
| Polynomialzeithierarchie (1) | 00:56:47 | |
|---|---|---|
| Einführung | 00:03:41 | |
| Orakel Turing Maschinen | 00:07:07 | |
| Einige Relativierungen | 00:18:29 | |
| Aufbau der Polynomialzeithierarchie | 00:06:04 | |
| Polynomial balancierte Relationen | 00:16:45 | |
| Logische Charakterisierung | 00:04:41 |
| Polynomialzeithierarchie (2) | 00:56:50 | |
|---|---|---|
| Wiederholung | 00:14:38 | |
| Kolabiert Polynomialzeithierarchie? | 00:12:05 | |
| MINIMUM CIRCUIT | 00:05:14 | |
| Vollständige Probleme | 00:13:49 | |
| PH und PSPACE | 00:03:32 | |
| PH und Probabilistische Komplexitätsklassen | 00:04:26 | |
| Landkarte der Polynomialzeithierarchie | 00:03:06 |
| Approximation | 00:53:16 | |
|---|---|---|
| Einführung | 00:04:51 | |
| Epsilon-Approximation | 00:06:51 | |
| NODE COVER | 00:05:22 | |
| MAXIMUM SATISFIABILITY | 00:10:52 | |
| TRAVELING SALESMAN PROBLEM | 00:08:14 | |
| KNAPSACK | 00:12:27 | |
| Approximationskomplexitätsklassen | 00:04:39 |
| Polynomiale Schaltkreise | 01:07:05 | |
|---|---|---|
| Einführung | 00:03:05 | |
| Schaltkreise als Berechnungsmodell | 00:07:12 | |
| Schaltkreiskomplexität | 00:08:47 | |
| Typische Schaltkreisgröße | 00:05:49 | |
| Polynomiale Schaltkreisprobleme | 00:19:11 | |
| Uniforme Schaltkreisfamilien | 00:08:57 | |
| Polynomiale Schaltkreise für BPP | 00:14:04 |
| P versus NP | 00:50:06 | |
|---|---|---|
| Einführung | 00:03:48 | |
| Graph Isomorphie | 00:04:52 | |
| Landkarte von NP | 00:26:56 | |
| NP-vollständige unäre Sprache | 00:06:15 | |
| Abschließende Bemerkungen | 00:08:15 |
