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/
03: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 24.10.2018
03 | 0:00:00 Start 0:17:21 Pünktchen vermeiden 0:18:31 Konkatenation 0:23:57 Umgehen mit Definitionen 0:29:09 Das leere Wort 0:37:11 Eigenschaften der Konkatenation 0:40:16 Beispiel: Aufbau von Emails. 0:40:42 RFC 0:41:59 Emails 0:46:23 Iterative Konkatenation 0:50:02 Induktive Definitionen kann man zu Rechnen benutzen 0:52:04 ein einfaches Lemma zu Längen von Wortpotenzen 0:53:26 Ein einafaches Lemma 0:55:37 Vollständige Induktion 0:56:18 Formale Sprachen 0:56:44 Sprachen 1:05:28 Binäre Operationen 1:08:39 Was ist wichtig 1:11:26 Kapitel 5 1:13:42 Aussagen 1:17:04 Grundlagen der klassischen Aussagenlogik