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
http://www.kit.edu/
04: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 06.11.2018
04 | 0:00:00 Start 0:00:03 letzte Vorlesung - alternative Sicht 0:04:48 Alternative Sicht - Beispiel 0:13:20 Heutiges Thema (Frage, Antwort) 0:20:21 Definitionen: Rechtsinvarianz und Index 0:27:56 Nerode-Relation 0:31:10 Satz von Nerode 0:50:10 Korollar 0:52:20 Minimalität des Äquivalenzklassenautomats 0:59:19 Zusammenfassung 1:07:12 Turing-Maschinen und Berechenbarkeit 1:08:42 Die Registermaschine (RAM) 1:14:26 Die Turing-Maschine (TM)