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:37:42 | |
|---|---|---|
| Was ist Komplexitätstheorie | 00:25:32 | |
| Hauptaufgabe der Komplexitätstheorie | 00:04:50 | |
| Welche Ergebnisse bringt die Komplexitätstheorie? | 00:07:20 |
| Probleme und Algorithmen | 01:38:17 | |
|---|---|---|
| Einführung | 00:15:09 | |
| Entscheidungsprobleme | 00:20:12 | |
| O-Notation | 00:19:41 | |
| Polynomialzeit-Algorithmen | 00:09:32 | |
| MAX FLOW - Flüsse in Netzwerken | 00:16:57 | |
| Reduktionstechniken | 00:16:46 |
| Turing Maschinen | 01:39:11 | |
|---|---|---|
| Einführung | 00:16:42 | |
| Turing Maschinen - Grundidee | 00:07:39 | |
| K-Band Turing Maschine | 00:20:45 | |
| Konfiguration einer k-Band TM | 00:16:00 | |
| Arbeitsweise einer k-Band TM | 00:13:48 | |
| Zeitkomplexität | 00:05:18 | |
| Leistungsvergleich von k-Band und 1-Band Turing Maschinen | 00:18:59 |
| Lineares Beschleunigen | 01:00:26 | |
|---|---|---|
| Wiederholung | 00:05:23 | |
| Speedup Theorem | 00:07:06 | |
| Beweisidee | 00:23:41 | |
| Simulation der Arbeitsschritte von M durch M' | 00:20:11 | |
| Definition der Komplexitätsklasse P | 00:04:05 |
| Raumkomplexität und Platzsparen | 01:19:03 | |
|---|---|---|
| Einführung | 00:06:47 | |
| Begriffsbestimmung | 00:14:53 | |
| Beispiel | 00:12:47 | |
| Turingmaschinen mit Ein- und Asgabe | 00:19:00 | |
| Rauumkomplexität | 00:17:17 | |
| Platzsparen | 00:08:19 |
| Nichtdeterministische Turing Maschinen | 01:30:25 | |
|---|---|---|
| Einführung | 00:06:46 | |
| NTM - Definition | 00:17:57 | |
| Nichtdeterministische Berechnungen | 00:19:35 | |
| Rundreiseproblem - TSP (D) | 00:18:06 | |
| Probabilistische Turing Maschinen | 00:12:26 | |
| Probabilistische Turing Maschinen (3) | 00:15:35 |
| Komplexitätsklassen | 00:48:16 | |
|---|---|---|
| Einleitung | 00:06:02 | |
| Schrankenfunktionen | 00:16:01 | |
| Präzise Turing Maschinen | 00:08:10 | |
| Wichtige Komplexitätsklassen | 00:04:21 | |
| Komplementäre Komplexitätrsklassen | 00:13:42 |
| Hierarchie-Theoreme | 00:42:20 | |
|---|---|---|
| Zeit-Hierarchie-Theorem | 00:13:28 | |
| Beweis durch Diagonalisierung | 00:25:57 | |
| Raum-Hierarchie-Theorem | 00:02:55 |
| Erreichbarkeitsmethode 1/2 | 01:00:00 | |
|---|---|---|
| Einführung | 00:06:31 | |
| NTIME vs. SPACE | 00:09:02 | |
| NSPACE vs. TIME | 00:18:59 | |
| Zwischenbilanz | 00:06:07 | |
| Satz von Savitch | 00:14:47 | |
| Beweisen | 00:11:22 |
| Erreichbarkeitsmethode 2/2 | 01:07:26 | |
|---|---|---|
| Wiederholung | 00:13:28 | |
| Satz von Immerman-Szelepcsenyi | 00:13:08 | |
| Beweis des Satzes | 00:23:12 | |
| Analyse des Satzes | 00:07:55 | |
| NSPACE vs. coNSPACE | 00:09:43 |
| Reduktion und Vollständigkeit 1/3 | 01:06:23 | |
|---|---|---|
| Einführung | 00:11:43 | |
| Grundidee der Reduktion | 00:15:14 | |
| Hamilton Path < SAT | 00:19:49 | |
| Beweis | 00:19:37 |
| Reduktion und Vollständigkeit 2/3 | 00:54:06 | |
|---|---|---|
| Grundidee der Reduktion | 00:04:21 | |
| Longspace-Reduktion | 00:03:07 | |
| Reachability < Circuit Value | 00:19:57 | |
| Reduktion durch Verallgemeinerung | 00:15:49 | |
| Kompositionen von Reduktionen | 00:10:52 |
| Reduktion und Vollständigkeit 3/3 | 01:15:30 | |
|---|---|---|
| Einführung | 00:03:08 | |
| K-Vollständigkeit | 00:13:54 | |
| Berechnungstabellen-Methode | 00:19:42 | |
| P-Vollständigkeit von CIRQUIT VALUE | 00:27:24 | |
| Behauptung | 00:11:22 |
| NP-Vollständigkeit | 00:35:25 | |
|---|---|---|
| Erinnerung | 00:11:45 | |
| Theorem nach Cook | 00:09:07 | |
| Annahme | 00:14:33 |
| Weitere Charakterisierungen von NP | 00:32:50 | |
|---|---|---|
| Polynomial entscheidbare Relation | 00:10:07 | |
| Charakterisierung von NP mittels Relationen | 00:16:54 | |
| Polynomiale Zeugnisse | 00:05:49 |
| Weitere NP-vollständige Probleme 1/4 | 01:02:48 | |
|---|---|---|
| Erinnerung | 00:10:40 | |
| NP-vollständige SAT-Varianten | 00:12:57 | |
| 2-SAT gehört zu P | 00:15:07 | |
| Beweis | 00:07:37 | |
| MAX-2-SAT ist NP-vollständig | 00:16:27 |
| Weitere NP-vollständige Probleme 2/4 | 01:09:51 | |
|---|---|---|
| Einführung | 00:06:15 | |
| INDEPENDENT SET Problem | 00:25:40 | |
| CLIQUE und NODE COVER | 00:06:23 | |
| Schnittprobleme | 00:11:25 | |
| Behauptung | 00:10:19 | |
| MIN CUT | 00:09:49 |
| Weitere NP-vollständige Probleme 3/4 | 01:13:06 | |
|---|---|---|
| Erinnerung | 00:07:01 | |
| Wege-Probleme | 00:10:37 | |
| Färbungsprobleme | 00:17:33 | |
| Matching | 00:09:59 | |
| Beispiel | 00:17:57 | |
| Behauptung | 00:09:59 |
| Weitere NP-vollständige Probleme 4/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:12:17 | |
|---|---|---|
| Einführung | 00:18:29 | |
| NP = coNP? | 00:13:28 | |
| Durchschnitt von NP und coNP | 00:06:44 | |
| Pratt's Theorem | 00:22:46 | |
| PRIMES gehört zu P | 00:10:50 |
| Randomisierte Berechnungen 1/2 | 01:10:39 | |
|---|---|---|
| Einführung | 00:03:47 | |
| Symolische Determinante | 00:15:41 | |
| Gaußsche Ellimination | 00:11:25 | |
| Abschätzung der Zshl der Nullstellen | 00:17:20 | |
| Randomisierter Algorithmus | 00:06:56 | |
| Random Walks | 00:05:24 | |
| Fermat Test | 00:10:06 |
| Randomisierte Berechnungen 2/2 | 00:51:49 | |
|---|---|---|
| Wiederholung | 00:02:37 | |
| Fehlersituation | 00:03:41 | |
| Probabilistische Turing Maschinen | 00:09:55 | |
| Die Klasse PP | 00:12:07 | |
| Die Klasse BPP | 00:07:37 | |
| Die Klasse RP | 00:08:31 | |
| Die Klasse 2 PP | 00:07:21 |
| Polynomialzeithierarchie 1/2 | 01:00:07 | |
|---|---|---|
| Einführung | 00:03:54 | |
| Orakel Turing Maschinen | 00:07:45 | |
| Einige Relativierungen | 00:20:57 | |
| Aufbau der Polynomialzeithirarchie | 00:05:23 | |
| Polynomial balancierte Relationen | 00:22:08 |
| Polynomialzeithierarchie 2/2 | 00:58:27 | |
|---|---|---|
| Wiederholung | 00:16:52 | |
| Kollabiert Polynomialzeithirarchie | 00:11:59 | |
| MINIMUM CIRQUIT | 00:05:55 | |
| Vollständige Probleme | 00:12:39 | |
| PH und PSPACE | 00:11:02 |
| Approximation | 01:02:22 | |
|---|---|---|
| Einfürung | 00:05:22 | |
| Epsilon-Approximation | 00:08:49 | |
| NOTE COVER | 00:09:39 | |
| MAXIMUM SATISFIABILITY | 00:15:56 | |
| TRAVELING SALESMAN PROBLEM | 00:07:36 | |
| KNAPSACK | 00:01:42 | |
| Polynomiale Approximationsschemata | 00:13:18 |
| Polynomiale Schaltkreise | 01:23:39 | |
|---|---|---|
| Einführung | 00:04:55 | |
| Schaltkreise als Berechnungsmodell | 00:05:51 | |
| Schaltkreiskomplexität | 00:10:20 | |
| Typische Schaltkreisgröße | 00:09:32 | |
| Polynomiale Schaltkreisverbindungen | 00:24:54 | |
| Polynomiale uniforme Schaltkreisfamilien | 00:11:24 | |
| Polynomiale Schaltkreise für BPP | 00:16:43 |
| P versus NP | 00:50:06 | |
|---|---|---|
| Einführung | 00:03:48 | |
| Graph Isomorphie | 00:04:52 | |
| Landkarte von NP | 00:26:45 | |
| NP-vollständige unäre Sprache | 00:06:26 | |
| Abschließende Bemerkungen | 00:08:15 |
