Theoretische Grundlagen der Informatik, Vorlesung, WS19/20
Karlsruher Institut für Technologie (KIT)
18 episodes
9 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, WS19/20 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
10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 28.11.2019
Theoretische Grundlagen der Informatik, Vorlesung, WS19/20
1 hour 22 minutes 2 seconds
5 years ago
10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 28.11.2019
10 |
0:00:00 Start
0:00:27 Letzte/Diese Vorlesung
0:04:04 Das Problem SUBSET SUM
0:05:37 NP-Vollständigkeit von SUBSET SUM
0:21:39 Das Problem PARTITION
0:22:29 Beweis: NP-Vollständigkeit von PARTITION
0:28:40 Das Problem KNAPSACK
0:31:18 Beweis: NP-Vollständigkeit von KNAPSACK
0:33:39 Auswirkung auf die Frage P= NP
0:40:15 Zusammenfassung
0:45:01 Die Klassen NPC und NPI
0:46:23 Die Klassen co-P und co-NP
0:51:28 Das TSP-Komplement-Problem
0:54:27 NP-vollständig vs. co-NP
0:58:19 Das Problem Subgraphisomorphie
1:00:17 Das Problem Graphisomorphie
1:02:06 Die Polynomielle Hierarchie
1:12:34 Suchprobleme
1:13:13 Beispiel: TSP-Suchproblem
1:14:53 Beispiel: Hamilton-Kreis Suchproblem
1:16:18 NP-Schwere bei Suchproblemen
1:20:15 Beispiel: Hamilton-Kreis Aufzählungsproblem
Theoretische Grundlagen der Informatik, Vorlesung, WS19/20
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
