0 Einführung |
 |  | 00:53:34 hours | play > |
1 Konzepte der Komplexitätstheorie1 Probleme und Algorithmen |
 | | (1) Einführung
(2) Reachability
(3) Einscheidungsprobleme
(4) Algorithmus für Grapherreichbarkeit
(5) O-Notation
(6) Polynomialzeit - Alg.
(7) Speicherplatzbedarf
(8) Max Flow
(9) Reduktionstechnik
(10) TSP 01:29:36 hours | play > |
2 Turing Maschinen |
 | | (1) Einführung
(2) Erweiterte Church'sche These
(3) Grundidee
(4) Def. einer k-Band TM
(5) Arbeitsweise einer k-Band TM
(6) Laufzeit einer k-Band TM
(7) Zeitkomplexität
(8) Vergleich k-Band und 1-Band TM 01:16:47 hours | play > |
3 Lineares Beschleunigen |
 | | (1) Vergleich k-Band und 1-Band TM
(2) Speed Up Theorem
(3) Beweisidee des Speed-Up Theorems
(4) Diskussion des Speed-Up Theorem
(5) Definition von P 01:18:36 hours | play > |
4 Raumkomplexität und Platzsparen |
 | | (1) Einführung
(2) Begriffsbestimmung
(3) Beispiel
(4) TM mit Ein- und Ausgabe
(5) Raumkomplexität
(6) Raumkomplexitätsklassen
(7) Platzsparen 01:15:42 hours | play > |
5 Nichtdeterministische Turing Maschinen |
 |  | (1) Einführung
(2) Definition
(3) Nichtdeterministische Berechungen
(4) Rundreiseproblem
(5) NTM und probabilistische TM
(6) NTM und deterministische TM 01:34:48 hours | play > |
6 Komplexitätsklassen |
 | | (1) Einführung
(2) Schrankenfunktionen
(3) Präzise Turing Maschinen
(4) Wichtige Komplexitätsklassen
(5) Komplementäre Komplexitätsklassen 00:55:36 hours | play > |
7 Hierarchie-Theoreme |
| | (6) Hierarchie-Theoreme 00:34:22 hours | play > |
8 Erreichbarkeitsmethode |
 | | (1) Einführung
(2) Determinismus vs. Nichtdeterminismus
(3) NTIME vs. SPACE
(4) NSPACE vs. TIME
(5) Erreichbarkeitsmethode
(6) Zwischenbilanz
(7) Satz von Savitch 01:17:47 hours | play > |
8 Erreichbarkeitsmethode (2) |
| | (1) Wiederholung
(2) Satz von Immerman-Szelepcsenyi
(3) Beweis des Immerman-Szelepcsenyi Theorems
(4) Analyse des Algorithmus
(5) NSPACE vs. coNSPACE 01:02:46 hours | play > |
9 Reduktion und Vollständigkeit |
| | (1) Einführung
(2) Grundidee
(3) Logspace Reduktion
(4) HAMILTON PATH <= SAT 01:08:19 hours | play > |
9 Reduktion und Vollständigkeit (2) |
| | (1) Grundidee
(2) Logspace Reduktion
(3) Reachability
(4) Reduktion durch Verallgemeinerung
(5) Circuit SAT
(6) Komposition von Reduktionen 01:21:48 hours | play > |
9 Reduktion und Vollständigkeit (3) |
 | | (1) Einführung
(2) K-Vollständigkeit
(3) Berechnungstabellen-Methode
(4) P-Vollständigkeit von CIRCUIT VALUE
(5) P-Vollständigkeit von MONOTONE CIRCUIT VALUE 01:20:41 hours | play > |
2 Die Klassen P und NP1 NP - Vollständigkeit |
| | (1) Erinnerung
(2) Cook'sches Theorem 00:47:42 hours | play > |
2 Weitere Charakterisierungen von NP |
| | (1) Polynomial entscheidbare Relation
(2) Polynomial balancierte Relation
(3) Charakterisierung von NP mittels Relationen
(4) Polynomiale Zeugnisse 00:35:17 hours | play > |
3 Weitere NP-vollständige Probleme |
 | | (1) Einführung
(2) Erinnerung
(3) Cook'sches Theorem
(4) Erinnerung
(5) NP-vollständige SAT-Varianten
(6) 2-SAT gehört zu P
(7) 2-SAT gehört zu NL
(8) MAX-2-SAT ist NP-vollständig
(9) NAE-SAT ist NP-vollständig 01:27:25 hours | play > |
3 Weitere NP-vollständige Probleme (2) |
 | | (1) Erinnerung
(2) Independent Set Problem
(3) Clique und Node Cover
(4) Schnitt-Probleme 01:10:46 hours | play > |
3 Weitere NP-vollständige Probleme (3) |
| | (1) Erinnerung
(2) Pfad Probleme
(3) Färbungsprobleme
(4) Matching 01:14:07 hours | play > |
3 Weitere NP-vollständige Probleme (4) |
| | (1) Erinnerung
(2) SET COVER
(3) INTEGER PROGRAMMING
(4) KNAPSACK
(5) BIN PACKING 01:35:26 hours | play > |
4 NP und coNP |
| | (1) Einführung
(2) coNP-vollständige Probleme
(3) NP = coNP ?
(4) Durchschnitt von NP und coNP
(5) Pratt's Theorem
(6) Sensation 2002: PRIMES gehört zu P 01:21:10 hours | play > |
5 Randomisierte Berechnungen |
| | (1) Erinnerung
(2) Symbolische Determinanten
(3) Gauß'sche Elimination
(4) Determinante gleich 0?
(5) Abschätzung der Zahl der Nullstellen
(6) Randomisierter Algorithmus PERFECT MATCHING
(7) Random Walks
(8) Fermat Test 01:23:13 hours | play > |
5 Randomisierte Berechnungen (2) |
| | (1) Erinnerung
(2) Fehlersituation
(3) Probabilistische Turing Maschinen
(4) Klasse PP
(5) Klasse BPP
(6) Klasse RP
(7) Klasse ZPP
(8) Landkarte der probabilistischen Komplexitätsklasse 01:16:38 hours | play > |
6 Polynomialzeithierarchie |
| | (1) Erinnerung
(2) Orakel Turing Maschinen
(3) Einige Relativierungen
(4) Aufbau der Polynomialzeithierarchie
(5) Charakterisierungen mit polynomial balancierten Relationen
(6) Logische Charakterisierung 01:21:06 hours | play > |
6 Polynomialzeithierarchie (2) |
| | (1) Erinnerung
(2) Kollabiert Polynomialzeithierarchie?
(3) MINIMUM CIRCUIT
(4) Vollständige Probleme
(5) Verhältnis zu PSPACE
(6) Verhältnis zu BPP
(7) Landkarte der Polynomialzeithierarchie 01:15:07 hours | play > |
7 Approximation |
| | (1) Erinnerung
(2) e-Approximation
(3) NODE-COVER
(4) MAXIMUM SATISFIABILITY
(5) Traveling Salesman Problem
(6) Knapsack
(7) Polynomiale Approximation
(8) Approximationskomplextitätsklassen 01:21:32 hours | play > |
8 Polynomiale Schaltkreise |
| | (1) Erinnerung
(2) Definition
(3) Schaltkreiskomplexität
(4) Typische Schaltkreisgröße
(5) Schaltkreisfamilien
(6) Polynomiale Schaltkreisfamilie
(7) Uniforme Polynomiale Schaltkreise
(8) Nichtuniforme Turing Maschinen
(9) Polynomiale Schaltkreise für BPP 01:24:24 hours | play > |
9 P versus NP |
| | (1) Landkarte von NP
(2) NP-vollständige unäre Sprachen
(3) Dünnbesetzte Sprachen
(4) Einige abschließende Bemerkungen 01:13:33 hours | play > |
