Theoretische Grundlagen der Informatik, Vorlesung, WS18/19
Karlsruher Institut für Technologie (KIT)
18 episodes
5 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, WS18/19 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
06: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 15.11.2018
Theoretische Grundlagen der Informatik, Vorlesung, WS18/19
1 hour 25 minutes 32 seconds
6 years ago
06: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 15.11.2018
06 |
0:00:00 Start
0:00:09 Letzte Vorlesung
0:03:24 Die Universelle Sprache
0:14:02 Satz von Rice – Motivation
0:17:55 Bemerkungen zum Satz von Rice
0:22:13 Das Post'sche Korrespondenzproblem
0:31:13 Eigenschaften von (semi-)entscheidbaren Sprachen
0:32:25 Komplexitätstheorie
0:34:36 Wie sieht ein Problem aus?
0:37:46 Definition: Problem
0:40:37 Definition:Kodierungsschema
0:46:51 Äquivalenz von Kodierungsschemata
0:48:35 Entscheidungsprobleme
0:50:57 Korrespondenz von Entscheidungsproblemen und Sprachen
0:52:43 Entscheidungsprobleme und Turing-Maschinen
0:54:34 Zeitkomplexität
0:57:38 Die Klasse P
1:01:00 Schwierigkeit von Entscheidungs- und Optimierungsproblem
1:04:53 Algorithmus OPT-TOUR (als Beweis)
1:10:08 Bemerkungen zum Algorithmus
1:13:17 Zwischenstand Komplexitätstheorie
1:17:01 Die Nichtdeterministische Turing-Maschine
1:23:02 Übertragung auf Entscheidungsprobleme II
Theoretische Grundlagen der Informatik, Vorlesung, WS18/19
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
