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/
20: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 16.01.2019
20 | 0:00:00 Start 0:00:15 Überblick 0:01:58 2x2 Matrizenmultiplikation 0:06:47 Die Idee von Volker Strassen 0:09:23 Aufwandsabschätzung für den Algorithmus von Strassen 0:13:22 Matrizenmultiplikation- geht es noch schneller? / Teile und herrsche(divide and conquer) 0:16:56 Laufzeit von Teile-und-Herrsche-Algorithmen 0:20:54 Mastertheorem-bescheidener hätte auch gereicht 0:32:48 Rechenzeiten 0:38:58 Zusammenfassung 0:41:51 Endliche Automaten 0:43:33 Ein primitiver Getränkeautomat 0:44:51 Getränkeautomat: Zustände 0:46:39 Getränkeautomat: Eingaben 0:47:40 Getränkeautomat: Zustandsübergänge 0:54:04 Getränkeautomat: Ausgaben 0:58:08 Mealy-Automaten 0:59:45 Verallgemeinerte Zustandsübergangsfunktionen 1:08:34 Was ist wichtig Lernziele: 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. Lehrinhalt: 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