Inhalt der Vorlesung: - Algorithmen informell, Grundlagen des Nachweises ihrer Korrektheit, Berechnungskomplexität, 'schwere' Probleme, O-Notation, Mastertheorem - Alphabete, Wörter, formale Sprachen, endliche Akzeptoren, kontextfreie Grammatiken - induktive/rekursive Definitionen, vollständige und strukturelle Induktion, Hüllenbildung - Relationen und Funktionen - Graphen - Syntax und Semantik für Aussagenlogik Weiterführende Literatur - Goos: Vorlesungen über Informatik, Band 1, Springer, 2005 - Abeck: Kursbuch Informatik I, Universitätsverlag Karlsruhe, 2005 Ziel: Der/die Studierende soll - grundlegende Definitionsmethoden erlernen und in die Lage versetzt werden, entsprechende Definitionen zu lesen und zu verstehen. - den Unterschied zwischen Syntax und Semantik kennen. - die grundlegenden Begriffe aus diskreter Mathematik und Informatik kennen und die Fähigkeit haben, sie im Zusammenhang mit der Beschreibung von Problemen und Beweisen anzuwenden. Vorlesungsaufzeichnung: http://webcast.kit.edu
http://www.kit.edu/
14: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 30.11.2018
14 | 0:00:00 Start 0:00:05 Ableitungsbaum 0:00:42 Wohlgeformte/ korrekte Klammerausdrücke 0:01:46 Arithmetische Ausdrücke 0:01:49 Ableitungsbaum 0:04:14 Wohlgeformte/ korrekte Klammerausdrücke 0:05:23 Arithmetische Ausdrücke 0:07:13 Syntax aussagenlogischer Formeln 0:08:55 Was ist wichtig 0:10:24 Wo sind wir? 0:11:37 Produkt von Relationen 0:17:45 Reflexiv-transitive Hülle einer Relation 0:22:01 Eigenschaften der reflexiv-transitiven Hülle 0:31:35 Was ist wichtig 0:32:22 Wo sind wir? 0:33:12 Eine Grenze kontextfreier Grammatiken 0:42:53 Übung 7: kontextfreie Grammatiken 0:43:23 Kontextfreie Grammatiken 0:47:49 Ableitungen 0:50:26 Ableitungsbaum 0:54:28 Warum ""kontextfrei""? 0:57:57 Palindrome – anna, otto und der reliefpfeiler 1:01:36 Nicht-Palindrome – abb, aabba, baabbab 1:04:14 Kontextfreie Sprachen 1:05:59 Vereinigung kontextfreier Sprachen 1:11:18 Schnitt kontextfreier Sprachen 1:14:09 Produkt von Relationen 1:20:18 Reflexiv, transitiv 1:22:38 Reflexiv-transitive Hülle