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/
12: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 20.12.2018
12 | 0:00:00 Start 0:00:31 Grammatiken, Beispiele 0:09:52 Grammatiken, Bemerkungen 0:16:13 Die Chomsky Hierarchie 0:29:17 Chomsky-0 Grammatiken und Semientscheidbarkeit 0:36:03 Beweis - Beschreibung der Grammatik G 0:42:30 Beweis - Zusammenfassung 0:49:13 Chromsky-3 Grammatiken und reguläre Sprachen 1:02:28 Chromsky-1 Grammatiken bzw. kontextsensitive Sprachen 1:09:49 Wiederholung: Das Problem CLIQUE 1:20:25 Typ-2 / Kontextfreie Grammatiken