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.
| Erste Einführung | 00:56:26 | |
|---|---|---|
| Was ist Komplexitätstheorie | 00:17:45 | |
| Grundrichtungen in der Komplexitätstheorie | 00:02:20 | |
| Hauptaufgabe der Komplexitätstheorie | 00:07:03 | |
| Welche Ergebnisse bringt die Komplexitätstheorie? | 00:12:05 | |
| Fahrplan für die Vorlesungen zur Komplexitätstheorie | 00:12:48 | |
| Leistungsnachweis | 00:04:25 |
| Probleme und Algorithmen | 01:13:56 | |
|---|---|---|
| Einführung | 00:03:59 | |
| Reachability - Grapherreichbarkeit | 00:08:10 | |
| Entscheidungsprobleme | 00:04:23 | |
| Algorithmus für Grapherreichbarkeit | 00:11:45 | |
| O-Notation | 00:08:10 | |
| Polynomialzeit-Algorithmen | 00:02:45 | |
| Speicherplatzbedarf | 00:02:20 | |
| MAX Flow - Flüsse im Netzwerken | 00:12:41 | |
| Reduktionstechniken | 00:08:56 | |
| TSP - Rundreiseproblem | 00:10:47 |
| Turing Maschinen | 01:28:50 | |
|---|---|---|
| Einführung | 00:02:39 | |
| Erweiterte Church´sche These | 00:08:23 | |
| Turing Maschine - Grundidee | 00:06:01 | |
| Zeitkomplexität | 00:06:33 | |
| Leistungsvergleich von K-Band und 1-Band TM | 00:22:11 | |
| K-Band Turing Maschine (TM) | 00:43:03 |
| Lineares Beschleunigen | 00:44:07 | |
|---|---|---|
| Wiederholung | 00:04:35 | |
| Speedup Theorem | 00:06:05 | |
| Speedup Theorem-Beweisidee | 00:26:47 | |
| Diskussion des Speedup Theorem | 00:03:33 | |
| Definition der Komplexitätsklasse P | 00:03:07 |
| Raumkomplexität und Platzsparen | 01:00:42 | |
|---|---|---|
| Wiederholung | 00:04:00 | |
| Begriffsbestimmung | 00:11:57 | |
| Beispiel | 00:10:23 | |
| TM mit Ein- und Ausgabe | 00:12:44 | |
| Raumkomplexität | 00:05:41 | |
| Raumkomplexitätsklassen | 00:08:36 | |
| Platzsparen | 00:07:21 |
| Nichtdeterministische Turing Maschinen | 01:30:59 | |
|---|---|---|
| Einführung | 00:24:36 | |
| Nichtdeterministische Berechnungen | 00:08:31 | |
| Nichtdeterministische Komplexität | 00:11:06 | |
| Rundreiseproblem - TSP (D) | 00:15:26 | |
| Nichtdeterministische und probabilistische TM | 00:07:08 | |
| Nichtdeterministische und deterministische TM | 00:24:12 |
| Komplexitätsklassen | 00:54:23 | |
|---|---|---|
| Einführung | 00:07:43 | |
| Schrankenfunktionen | 00:14:50 | |
| Präzise Turing Maschinen | 00:11:18 | |
| Wichtige Komplexitätsklassen | 00:04:07 | |
| Komplementäre Komplexitätsklassen | 00:16:25 |
| Hierarchie-Theoreme | 00:44:39 | |
|---|---|---|
| Zeit-Hierarchie-Theorem 1-5 | 00:20:13 | |
| Zeit-Hierarchie-Theorem 6-10 | 00:21:17 | |
| Raum-Hierarchie-Theorem | 00:03:09 |
| Erreichbarkeitsmethode 1/2 | 01:05:49 | |
|---|---|---|
| Determinismus vs. Nichtdeterminismus | 00:04:45 | |
| Einführung | 00:01:33 | |
| NTIME vs. SPACE | 00:10:06 | |
| NSPACE vs. TIME | 00:17:18 | |
| Zwischenbilanz | 00:08:59 | |
| Satz von Sawitch | 00:23:09 |
| Erreichbarkeitsmethode 2/2 | 00:45:21 | |
|---|---|---|
| Wiederholung | 00:07:57 | |
| Satz von Immerman Szelepcseny | 00:08:53 | |
| Beweis des Satzes | 00:13:02 | |
| Analyse des Satzes | 00:05:43 | |
| NSPACE vs coNSPACE | 00:09:46 |
| Reduktion und Vollständigkeit 1/3 | 00:54:06 | |
|---|---|---|
| Einführung | 00:10:19 | |
| Grundidee der Reduktion | 00:03:11 | |
| Logspace-Reduktion | 00:10:10 | |
| Hammilton Path 1-5 | 00:16:45 | |
| Hammilton Path 6-10 | 00:13:41 |
| Reduktion und Vollständigkeit 2/3 | 01:00:29 | |
|---|---|---|
| Einführung | 00:01:50 | |
| Grundlagen der Reduktion | 00:10:48 | |
| Reachability Cirquit Value | 00:19:27 | |
| Reduktion durch Verallgemeinerung | 00:13:47 | |
| Komposition von Reduktionen | 00:14:37 |
| Reduktion und Vollständigkeit 3/3 | 01:05:20 | |
|---|---|---|
| Einführung | 00:04:25 | |
| K-Vollständigkeit | 00:14:24 | |
| Berechnungstabellen Methode | 00:15:05 | |
| P-Vollständigkeit von CIRCUIT VALUE 1 | 00:09:55 | |
| P-Vollständigkeit von CIRCUIT VALUE 5 | 00:21:31 |
| NP-Vollständigkeit | 00:36:46 | |
|---|---|---|
| Erinnerung | 00:14:29 | |
| Cook's Theorem 1 bis 3 | 00:09:21 | |
| Cook's Theorem 4 bis 6 | 00:12:56 |
| Weitere Characterisierungen von NP | 00:27:22 | |
|---|---|---|
| Überleitung | 00:01:13 | |
| Polynomial entscheidbare Relation | 00:04:33 | |
| Charakterisierung von NP mittels Relationen | 00:14:20 | |
| Polynomiale Zeugnisse | 00:07:16 |
| Weitere NP-vollständige Probleme 1/4 | 00:57:58 | |
|---|---|---|
| Erinnerung | 00:10:36 | |
| NP-vollständige SAT-Varianten | 00:11:29 | |
| 2-SAT gehört zu P | 00:18:01 | |
| 2-SAT gehört zu NL | 00:02:01 | |
| MAX-2-SAT ist NP-vollständig | 00:15:51 |
| Weitere NP-vollständige Probleme 2/4 | 00:57:13 | |
|---|---|---|
| Erinnerung | 00:08:27 | |
| Independent Set Problem | 00:19:37 | |
| Clique und Note Cover | 00:05:07 | |
| Schnittprobleme 1 | 00:13:10 | |
| Schnittprobleme 2 | 00:10:53 |
| Weitere NP-vollständige Probleme 3/4 | 01:09:41 | |
|---|---|---|
| Erinnerung | 00:07:45 | |
| Wege-Probleme | 00:12:33 | |
| Färbungsprobleme | 00:17:14 | |
| Matching | 00:16:34 | |
| Matching | 00:15:35 |
| Weitere NP-vollständige Probleme 4/4 | 01:12:17 | |
|---|---|---|
| Erinnerung | 00:08:52 | |
| Set-Cover | 00:09:51 | |
| Integer Programming | 00:16:38 | |
| Knapsack | 00:17:24 | |
| Bin-Packing | 00:19:33 |
| NP and co-NP | 01:00:28 | |
|---|---|---|
| Einführung | 00:08:53 | |
| coNP -vollständige Probleme | 00:05:35 | |
| NP = coNP ? | 00:15:36 | |
| Pratt's Theorem | 00:19:10 | |
| PRIMES gehört zu P | 00:11:14 |
| Randomisierte Berechnungen 1/2 | 01:11:19 | |
|---|---|---|
| Einführung | 00:02:42 | |
| Symbolische Determinante | 00:13:58 | |
| Gauss'sche Elimination | 00:24:54 | |
| Randomisierter Algorithmus | 00:09:10 | |
| Random Walks | 00:05:48 | |
| Fermat Test | 00:14:48 |
| Randomisierte Berechnungen 2/2 | 00:49:27 | |
|---|---|---|
| Wiederholung | 00:04:47 | |
| Fehlersituation | 00:13:07 | |
| Die Komplexitätsklasse PP | 00:10:17 | |
| Die Komplexitätsklasse BPP | 00:07:23 | |
| Die Komplexitätsklasse RP | 00:07:08 | |
| Die Komplexitätsklasse ZPP | 00:04:22 | |
| Probabilistische Komplexitätsklassen | 00:02:24 |
| Polynomialzeithierarchie 1/2 | 00:59:19 | |
|---|---|---|
| Einführung | 00:03:58 | |
| Orakel Tuning Maschinen OTM | 00:07:21 | |
| Einige Relativierungen | 00:19:10 | |
| Aufbau der Polynomialzeithierarchie | 00:05:55 | |
| Polynomial balancierte Relationen | 00:20:18 | |
| Logische Charakterisierung | 00:02:37 |
| Polynomialzeithierarchie 2/2 | 00:54:16 | |
|---|---|---|
| Wiederholung | 00:14:44 | |
| Kolabiert Polynomialzeithierarchie? | 00:13:00 | |
| Minimum Circuit | 00:05:42 | |
| Vollständige Probleme | 00:12:56 | |
| PH und PSPACE | 00:07:54 |
| Approximation | 00:54:37 | |
|---|---|---|
| Einführung | 00:07:25 | |
| e-Approximation | 00:13:13 | |
| Maximum Satisfiability | 00:12:39 | |
| Traveling Salesman Problem | 00:08:57 | |
| Knapsack | 00:01:50 | |
| Polynomiale Approximationsschemata | 00:10:33 |
| Polynomiale Schaltkreise | 01:28:01 | |
|---|---|---|
| Einführung | 00:05:38 | |
| Schaltkreise als Berechnungsmodell | 00:20:54 | |
| Typische Schaltkreisgröße | 00:10:08 | |
| Polynomiale Schaltkreisfamilien | 00:24:33 | |
| Uniforme Schaltkreisfamilien | 00:10:57 | |
| Polynomiale Schaltkreise für BPP | 00:15:51 |
| P versus NP | 00:49:04 | |
|---|---|---|
| Einführung | 00:05:32 | |
| Graph Isomorphie | 00:04:05 | |
| Landkarte von NP | 00:22:42 | |
| NP-vollständige unäre Sprachen | 00:01:38 | |
| Dünnbesetzte Sprachen | 00:04:49 | |
| Abschließende Bemerkungen | 00:10:18 |
