Education
16: Übung und Vorlesung| 0:00:00 Starten 0:00:56 Rückblick: Chomsky-3 0:05:29 Rückblick: Chomsky-3 Verfahren 0:16:18 Rückblick: Chomsky-2 0:19:33 Rückblick: Chomsky-2 Verfahren 0:27:23 Rückblick: Chomsky-0/1 0:30:41 Rückblick: Entscheidbarkeit 0:36:54 Ausblick: Komplexitätstheorie 0:38:54 Video: Game of Life Automat 0:43:27 Video: Variante von Game of Life mit realen Werten 0:45:23 Vorlesung 0:46:03 Kapitel 2: Komplexitätstheorie 0:46:34 Obere Schranken 0:46:54 Untere Schranken 0:47:23 Untere Schranken: Lösungsansätze 0:49:08 Eine Komplexitätsklasse 0:50:00 Komplexitätsklasse P 0:50:31 P für verschiedene Maschinenmodelle 0:52:33 Komplexitätsklasse NP 0:53:29 Beispiel: Rucksackproblem 0:54:05 Alternative Definition von NTIME: Orakel 0:55:26 Äquivalenz von NTIME und OTIME 0:55:47 Die 1 000 000 $ Frage 0:57:09 Eine Komplexitätshierarchie 0:59:59 Polynomiale Reduzierbarkeit 1:02:10 Beispiel 1:09:05 NP-harte und NP-vollständige Probleme 1:15:09 Ein einfacher Weg zu Ruhm und Reichtum? 1:20:16 SAT: Das Erfüllbarkeitsproblem 1:23:34 Beweis von SAT ∈ NP