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/
25: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 01.02.2019
25 | 0:00:00 Start 0:00:22 Äquivalenzrelationen 0:01:41 Kongruenz ganzer Zahlen modulo n 0:04:05 Bild einer Äquivalnzrelation 0:12:15 Was ist wichtig 0:13:40 Äquivalenzrelationen auf mengen mit Struktur 0:18:23 Kongruenzrelationen 0:20:52 Verträglichkeit erlaubt die Übertragung einer Abbildung auf die Faktormenge 0:24:33 Rückblick auf endliche Akzeptoren 0:28:38 Verträglichkeit: Beispiel Nerode-Äquivalenzen 0:37:32 Antisymmetrische Relationen 0:39:52 Halbordnungen 0:41:49 eine Halbordnung auf Wörtern – darauf bauen wir später noch auf 0:43:37 Übung 0:44:44 Reguläre Ausdrücke 0:49:29 Ein regulärer Ausdruck für epsilon 0:54:44 Distributivgesetz 0:56:14 Kantorowitsch-Bäume 1:01:53 Kantorowitsch-Bäume und reguläre Ausdrücke 1:04:51 Beispiel: Zahlen spezifizieren 1:07:14 Ein Wiederbesuch: Wörter umkehren 1:11:32 Rechtslineare Grammatiken 1:15:16 Charakterisierung regulärer Sprachen 1:18:47 Linkslineare Grammatiken 1:23:40 Äquivalenz RL und LL Grammatiken