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/
15: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 05.12.2018
15 | 0:00:00 Start 0:01:42 Kapitel 13: Prädikatenlogik erster Stufe 0:02:09 Eine Grenze kontextfreier Grammatiken 0:03:50 Lvv - Beispielwörter 0:04:22 Lvv ist nicht kontextfrei 0:29:01 Überblick 0:30:15 Prädikatenlogische Formeln 0:32:10 Prädikatenlogische Formeln - der Aufwand lohnt sich 0:33:10 Terme - benötigte Alphabete 0:35:22 Terme - Syntax 0:37:41 Terme - Beispiel 0:42:11 Atomare Formeln - Syntax 0:45:53 Atomare Forlmeln - Beispiele 0:48:31 Prädikatenlogische Formeln - Syntax 0:50:51 Prädikatenlogische Formeln - Beispiele 0:51:56 Was ist wichtig 0:52:48 Interpretetaion 0:58:02 val - ein Wert für jeden Term und ein Wahrheitswert für jede Formel 0:59:15 val - ein Wert in D für jeden Term 1:03:22 val - ein Wahrheitswert für jede atomare Formel 1:05:31 val - Bespiel für atomare Formeln 1:09:28 val - Wahrheitswert für quantifizierte Formeln 1:11:08 val - Beispiel für quantifizierte Formeln 1:14:01 Allgemeingültige Formeln 1:15:51 Allgemeingültige Formeln - aber keine Tautologien 1:18:38 Modelle 1:20:32 Modelle - Beispiel 1:22:55 Was ist wichtig