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/
04: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 26.10.2018
04 | 0:00:00 Starten 0:00:03 Kapitel 5: Aussagenlogik 0:02:21 Alphabet der Aussagenlogik 0:04:29 Konstruktionsabbildungen 0:07:24 Lesearten 0:08:09 Syntax Konstruktion immer größerer Formeln 0:19:33 Boolesche Funktionen 0:29:37 Semantik aussagenlogischer Formeln 0:35:14 Übung 2: Wörter, binäre Operationen und Aussagenlogik 0:35:37 Wörter 0:38:10 Das leere Wort 0:39:25 Mengen von Wörtern 0:42:30 Unterscheidung Symbol / Wort 0:44:26 Konkatenation 0:49:58 Kommutativität 0:52:36 Assoziativität 0:55:21 Wörter ""spiegeln"" 0:58:27 Berechnung von f 1:00:10 Als binäre Operation 1:01:55 Aussagenlogik: Syntax 1:03:58 Aufbau einer Formel 1:08:08 Formale Sprachen