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.
| Introduction and content | 01:03:58 | |
|---|---|---|
| Grundrichtungen in der Komplexitätstheorie | 00:09:10 | |
| Was ist Komplexitätstheorie | 00:29:02 | |
| Ergebnisse der Komplexitätstheorie | 00:09:38 | |
| Ablauf der Vorlesungen | 00:16:08 |
| Turing Machines | 01:37:27 | |
|---|---|---|
| Einführung | 00:04:04 | |
| Erweiterte Church'sche These | 00:12:58 | |
| K-Band Turing Maschine | 00:25:22 | |
| Konfiguration einer K-Band TM | 00:22:39 | |
| Zeitkomplexität | 00:09:24 | |
| Leistungsvergleich von Turing Maschinen | 00:23:01 |
| Linear acceleration | 01:00:23 | |
|---|---|---|
| Repetition | 00:05:23 | |
| Speedup proposition | 00:07:06 | |
| Idea of evidence | 00:23:41 | |
| Simulation of workingsteps from M by M' | 00:20:11 | |
| Definition of the complexityclass P | 00:04:02 |
| Raumkomplexität und Platzsparen | 01:10:17 | |
|---|---|---|
| Introduction | 00:04:46 | |
| Begriffsbestimmung | 00:15:19 | |
| Beispiel | 00:13:39 | |
| Turingmaschinen mit Ein- und Ausgabe | 00:15:11 | |
| Raumkomplexität | 00:13:56 | |
| Platzsparen | 00:07:26 |
| Nichtdeterministische Turing Maschinen | 01:30:29 | |
|---|---|---|
| Einführung | 00:05:29 | |
| NTM - Definitionen | 00:18:49 | |
| Nichtdeterministische Berechnungen | 00:11:15 | |
| Nichtdeterministische Komplexität | 00:09:27 | |
| Rundreiseproblem - TSP(D) | 00:24:58 | |
| Nichtdeterministische und deterministische TM | 00:20:31 |
| Komplexitätsklassen | 00:50:45 | |
|---|---|---|
| Einführung | 00:04:24 | |
| Schrankenfunktionen | 00:18:38 | |
| Präzise Turing Maschinen | 00:09:26 | |
| Wichtige Komplexitätsklassen | 00:03:48 | |
| Komplementäre Komplexitätsklassen | 00:14:29 |
| Hierarchie-Theoreme | 00:51:36 | |
|---|---|---|
| Zeit-Hierarchie-Theorem Satz 1 | 00:24:58 | |
| Zeit-Hierarchie-Theorem Satz 2 | 00:24:31 | |
| Raum-Hierarchie-Theorem | 00:02:07 |
| Erreichbarkeitsmethode 1/2 | 01:09:36 | |
|---|---|---|
| Einführung | 00:03:13 | |
| NTIME vs. SPACE | 00:13:34 | |
| NSPACE vs. TIME | 00:17:27 | |
| Zwischenbilanz | 00:08:16 | |
| Satz von Savitch | 00:27:06 |
| Erreichbarkeitsmethode 2/2 | 01:01:12 | |
|---|---|---|
| Wiederholung | 00:09:52 | |
| Satz von Immerman-Szelepcsenyi | 00:13:43 | |
| Beweis des Satzes | 00:19:38 | |
| Analyse des Satzes | 00:07:53 | |
| NSPACE vs. coNSPACE | 00:10:07 |
| Reduktion und Vollständigkeit 1/3 | 00:58:20 | |
|---|---|---|
| Einführung | 00:12:07 | |
| Grundidee der Reduktion | 00:13:58 | |
| HAMILTON PATH < SAT | 00:17:04 | |
| Behauptung und Beweis | 00:15:11 |
| Reduktion und Vollständigkeit 2/3 | 01:16:21 | |
|---|---|---|
| Grundidee der Reduktion | 00:12:12 | |
| Reduktion von REACHABILITY | 00:27:22 | |
| Reduktion durch Verallgemeinerung | 00:04:26 | |
| Reduktion von CIRCUIT SAT | 00:18:25 | |
| Komposition von Reduktionen | 00:13:56 |
| Reduktion und Vollständigkeit 3/3 | 01:10:41 | |
|---|---|---|
| Einführung | 00:03:23 | |
| K-Vollständigkeit | 00:16:49 | |
| Berechnungstabellen-Methode | 00:16:20 | |
| P-Vollständigkeit von CIRCUIT VALUE | 00:29:58 | |
| P-Vollständigkeit von MONTONE CIRCUIT VALUE | 00:04:11 |
| Problems and Algorithms | 01:36:43 | |
|---|---|---|
| Introduction | 00:19:14 | |
| Decision problems | 00:06:04 | |
| Algorithm for graphreachability | 00:15:37 | |
| O-Notation | 00:19:48 | |
| MAX FLOW - flows in networks | 00:14:56 | |
| Reduction-technique | 00:10:18 | |
| TSP-Round-trip-problem | 00:10:46 |
| Weitere Charakterisierungen von NP | 00:20:45 | |
|---|---|---|
| Polynomial entscheidbare Relation | 00:05:04 | |
| Charakterisierung von NP mittels Relationen | 00:10:17 | |
| Polynomiale Zeugnisse | 00:05:24 |
| Weitere NP-vollständige Probleme 1/4 | 01:03:36 | |
|---|---|---|
| Erinnerung | 00:14:35 | |
| NP-vollständige SAT-Varianten | 00:14:00 | |
| 2-SAT gehört zu P | 00:19:55 | |
| 2-SAT gehört zu NL | 00:00:46 | |
| MAX-2-SAT ist NP-vollständig | 00:11:59 | |
| NAE-SAT ist NP-vollständig | 00:02:21 |
| Weitere NP-vollständige Probleme 2/4 | 01:06:06 | |
|---|---|---|
| Erinnerung | 00:10:12 | |
| INDEPENDENT SET Problem | 00:23:23 | |
| CLIQUE und NODE COVER | 00:05:27 | |
| Schnitt-Probleme | 00:17:43 | |
| MIN CUT | 00:09:21 |
| Weitere NP-vollständige Probleme 3/4 | 01:22:15 | |
|---|---|---|
| Erinnerung | 00:10:07 | |
| Wege Probleme | 00:14:07 | |
| Färbungsprobleme | 00:18:51 | |
| Matching (1) | 00:16:58 | |
| Matching (2) | 00:22:12 |
| Weitere NP-vollständige Probleme 4/4 | 01:18:54 | |
|---|---|---|
| Erinnerung | 00:12:28 | |
| SET COVER | 00:08:05 | |
| INTEGER PROGRAMMING | 00:11:58 | |
| KNAPSACK | 00:20:34 | |
| BIN PACKING | 00:25:49 |
| NP und coNP | 01:13:47 | |
|---|---|---|
| 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:11:12 | |
|---|---|---|
| Einführung | 00:02:45 | |
| Symbolische Determinante | 00:13:45 | |
| Gauß'sche Elimination | 00:10:51 | |
| Abschätzen der Zahl der Nullstellen | 00:14:14 | |
| Randomisierter Algorithmus | 00:11:15 | |
| Random Walks | 00:07:09 | |
| Fermat Test | 00:11:13 |
| Randomisierte Berechnungen 2/2 | 00:55:59 | |
|---|---|---|
| Wiederholung | 00:04:12 | |
| Fehlersituation | 00:05:36 | |
| Probabilistische Turing Maschinen | 00:09:40 | |
| Die Klasse PP | 00:11:54 | |
| Die Klasse BPP | 00:08:24 | |
| Die Klasse RP | 00:08:53 | |
| Die Klasse ZPP | 00:07:20 |
| Polynomialzeithierarchie 1/2 | 01:00:11 | |
|---|---|---|
| Einführung | 00:03:57 | |
| Orakel Turing Maschinen | 00:07:45 | |
| Einige Relativierungen | 00:20:57 | |
| Aufbau der Polynomialzeithirarchie | 00:05:23 | |
| Polynomial balancierte Relationen | 00:22:09 |
| Polynomialzeithierarchie 2/2 | 00:58:27 | |
|---|---|---|
| Wiederholung | 00:16:52 | |
| Kollabiert Polynomialzeithierarchie? | 00:11:59 | |
| MINIMUM CIRQUIT | 00:05:55 | |
| Vollständige Probleme | 00:12:39 | |
| PH und PSPACE | 00:11:02 |
| Approximation | 00:58:51 | |
|---|---|---|
| Einführung | 00:05:21 | |
| e-Approximation | 00:08:59 | |
| NODE COVER | 00:09:09 | |
| MAXIMUM SATISFIABILITY | 00:12:28 | |
| TRAVELING SALESMAN PROBLEM | 00:09:59 | |
| Polynomiale Approximationsschemata | 00:12:58 |
| Polynomiale Schaltkreise | 01:23:39 | |
|---|---|---|
| Einführung | 00:04:55 | |
| Schaltkreise als Berechnungsmodell | 00:05:51 | |
| Schaltkreiskomplexität | 00:10:19 | |
| Typische Schaltkreisgröße | 00:09:32 | |
| Polynomiale Schaltkreisverbindungen | 00:24:54 | |
| Polynomiale uniforme Schaltkreisfamilien | 00:11:25 | |
| 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:44 | |
| NP-vollständige unäre Sprache | 00:06:26 | |
| Abschließende Bemerkungen | 00:08:16 |
| NP-Vollständigkeit | 00:32:30 | |
|---|---|---|
| Erinnerung | 00:11:04 | |
| Cook's Theorem | 00:21:26 |
