Theoretische Grundlagen der Informatik, Vorlesung, WS16/17
Karlsruher Institut für Technologie (KIT)
18 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.
Dozentin: Prof. Dr. Dorothea Wagner | Karlsruher Institut für Karlsruher Technologie (KIT), Institut für Theoretische Informatik
Vorlesungsaufzeichnung: http://webcast.kit.edu
All content for Theoretische Grundlagen der Informatik, Vorlesung, WS16/17 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.
Dozentin: Prof. Dr. Dorothea Wagner | Karlsruher Institut für Karlsruher Technologie (KIT), Institut für Theoretische Informatik
Vorlesungsaufzeichnung: http://webcast.kit.edu
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 01.12.2016, 08
Theoretische Grundlagen der Informatik, Vorlesung, WS16/17
1 hour 27 minutes 34 seconds
8 years ago
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 01.12.2016, 08
08 |
0:00:00 Starten
0:00:37 Wiederholung: NP-Vollständigkeit
0:06:10 Wiederholung: Transitivität der poly. Transformation
0:06:40 Wiederholung: Korollar
0:07:37 Wiederholung: Das Problem SAT (satisfiability)
0:12:17 Das Problem 3-SAT
0:13:13 Beweis: NP-Vollständigkeit von 3-SAT
0:30:07 Das Problem 2SAT
0:34:40 Das Problem MAX2SAT
0:38:02 Das Problem CLIQUE
0:39:32 Beweis: NP-Vollständigkeit von CLIQUE
0:51:19 Das Problem COLOR
0:54:56 Beweis: NP-Vollständigkeit von 3COLOR
0:57:29 Konstruktion von 3COLOR-Instanz G
1:01:05 Beispielgraph zur Reduktion
1:04:20 Polynomialität der Reduktion
1:04:56 Instanz I erfüllbar => Instanz G erfüllbar
1:07:12 Instanz I erfüllbar <= Instanz G erfüllbar
1:08:02 Das Problem EXACT COVER
1:13:06 Beweis: NP-Vollständigkeit von EXACT COVER
1:14:28 Konstruktion von (X,S)
1:24:05 G dreifärbbar => (X,S) hat exakte Überdeckung
1:25:47 G dreifärbbar <= (X,S) hat exakte Überdeckung
Theoretische Grundlagen der Informatik, Vorlesung, WS16/17
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen.
Dozentin: Prof. Dr. Dorothea Wagner | Karlsruher Institut für Karlsruher Technologie (KIT), Institut für Theoretische Informatik
Vorlesungsaufzeichnung: http://webcast.kit.edu
