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/
16: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 29.01.2019
16 | 0:00:00 Start 0:00:32 Letzte Vorlesung 0:02:51 Wdh.: Greibach-Normalform, Kellerautomat 0:06:32 Beispiel - Greibach-Normalform 0:12:41 Beispiel - Kellerautomat 0:17:47 Beweis: Greibach-Normalform -NPDA 0:26:14 Übersicht 0:27:41 Beweis:NPDA - kontextfreie Grammatik 0:51:16 Exkurs 0:55:11 Zwischenfazit zu kontextfreien Grammatiken 0:57:12 Unentschedbare Probleme für kontextfreie Grammatiken 1:00:05 Das Post'sche Korrespondenzproblem 1:01:10 Beweis 1:06:43 Eindeutigkeit von kontextfreien Grammatiken 1:09:01 Sprache der korrekten Rechenwege 1:27:34 Zusammenfassung Chomsky-Hierarchie