Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
Karlsruher Institut für Technologie (KIT)
27 episodes
8 months ago
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu
All content for Theoretische Grundlagen der Informatik, Vorlesung, WS15/16 is the property of Karlsruher Institut für Technologie (KIT) and is served directly from their servers
with no modification, redirects, or rehosting. The podcast is not affiliated with or endorsed by Podjoint in any way.
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu
Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 12.01.2016, Vorlesung - 17
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
1 hour 13 minutes
9 years ago
Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 12.01.2016, Vorlesung - 17
17: Vorlesung|
0:00:00 Starten
0:00:53 Wiederholung Komplexitätstheorie
0:08:54 Polynominale Reduzierbarkeit
0:09:55 Beispiel
0:10:57 NP-harte und Np-Vollständige Probleme
0:13:22 Ein einfacher Weg zu Ruhm und Reichtum ?
0:13:50 SAT: Das Erfüllbarkeitsproblem
0:17:03 Beweis von SAT
0:17:31 Beweis das SAT-NP-hart ist.
0:19:45 Variablen für F
0:24:53 Die Architektir von F=
0:27:08 Beweis w gehört zu der Sprache L, was daraus folgt das F erfüllbar ist
0:31:44 Es kann nur einen geben
0:33:05 Randbedingung
0:37:00 Anfangsbedingung
0:38:46 Übergangsbedingung Ü1, t->t+1
0:42:01 Übergangsbedingung Ü2, t->t+1
0:42:42 Endebedingung E
0:43:56 Gesamtgröße von F
0:48:06 Weitere NP-vollständige Probleme
0:55:04 3SAT (KNF)
0:56:56 Satz: 3SAT ist NP-vollständig
0:58:29 Beweis ""3SAT ist NP-hart""
1:00:12 Negation in die Blätter drücken
1:01:23 Beispiel
1:03:04 Nichtblattknoten -> Neue Variablen
1:05:52 Beispiel
1:06:34 Erfüllbarkeitsäquivalenz von F1
1:07:57 Beispiel
1:10:15 F1 -> 3KNF
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu
