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/
06: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 02.11.2018
06 | 0:00:00 Start 0:00:17 Vollständige Induktion 0:10:03 Varianten der vollständigen Induktion 0:16:24 Verallgemeinerung 0:25:47 Induktive Definitionen 0:28:28 Ackermann-Funktion 0:37:33 Was ist wichtig? 0:41:28 Anfang der Übung 0:41:56 Boolesche Funktion 0:43:50 Interpretation 0:46:59 Unterscheidung Syntax/Semantik 0:48:50 Gleichheit von Formeln 0:51:20 Wahrheitstabelle 0:54:01 Modelle 0:55:55 Allgemeingültigkeit und Äquivalenz 0:58:07 Beweisen mit Äquivalenz 1:01:06 Vollständige Induktion 1:03:40 Beispiel 1:05:28 Beliebte Fehler 1:09:51 induktive Definitionen 1:13:58 Starke Induktion