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/
08: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 09.11.2018
08 | 0:00:00 Start 0:00:56 Themen dieses Kapitels 0:01:05 Binärdarstellung von Zahlen 0:01:59 Hexadezimaldarstellung 0:02:55 Operationen div und mod 0:03:38 k-äre Darstellung von Zahlen 0:09:04 Zahldarstellung mit beschränkter fester Länge 0:11:10 Negative Zahlen 0:15:59 Darstellung auch negativer Zahlen 0:18:35 Zweierkomplement-Darstellung 0:27:25 Menge aller Funktionen von A nach B 0:29:06 Komposition von Funktionen 0:31:35 Identität 0:32:58 Umkehrfunktion 0:35:57 Links- und Rechtsinverse 0:38:02 Von Hexadezimal- zu Binärdarstellung 0:40:37 Übersetzungen 0:43:46 Übung 4: Formale Sprachen und Zahlendarstellung 0:44:23 Konkatenation formaler Sprachen 0:51:33 Konkatenationsabschluss 0:56:43 Konkatenationsabschluss vom Konkatenationsabschluss 1:02:38 Beschreibung formaler Sprachen 1:08:52 Zahlendarstellung 1:12:31 Binärdarstellung einer Zahl 1:13:58 Zahlendarstellung 1:20:54 Zahlendarstellung und formale Sprachen