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/
05: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 31.10.2018
05 | 0:00:00 Start 0:10:20 Auswertung von Formeln - ein Beispiel 0:12:41 Auswertung einer Formel für alle Interpretation 0:15:46 Äquivalente Formeln 0:18:59 kleine Randbemerkung - Auffassung einer Formel als Abbildung 0:21:34 Modelle 0:25:59 Wichtige Spezialfälle aussagenlogischer Formeln 0:30:25 Tautologien - viele Beispiele auf ein Mal 0:32:18 Zwei Äquivalenz ,,Begriffe'' die zusammenpassen 0:33:51 Tautologien - konkreten Beispiele 0:34:22 Tautologien anderer Bauart 0:35:29 Beweisbarkeit 0:36:39 Kalkül 0:39:13 Aussagenkalkül 0:41:50 Ableitungen 0:46:40 Beweis 0:53:27 Modus Ponens ,,erhält Allgemeingültigkeit'' 0:55:56 Alle Theoreme des Aussagenkalküls sind Tautologien 0:57:24 Die umgekehrte Richtung gilt auch 0:59:40 Ein Beispiel für die Nützlichkeit des Kalküls 1:02:07 Fortsetzung des Beweises 1:02:59 Was ist wichtig 1:08:31 Vollständige Induktion 1:08:45 Eine Erinnerung 1:10:12 Das Lemma über Wortlängen