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/
Gesamtlänge aller Episoden: 1 day 11 hours 35 minutes
recommended podcasts
16: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 07.12.2018
16 | 0:00:00 Start 0:00:05 Allgemeingültige Formeln 0:05:40 Vorkommen von Variablensymbolen in Formeln 0:07:33 freie und gebundene Vorkommen von Variablensymbolen 0:16:46 Substitutionen 0:30:50 Kollisionsfreie Substitutionen für Formeln 0:33:12 Logisch äquivalente Formeln 0:40:29 Weitere allgemeingültige Formeln 0:41:18 Großzügige Benutzung von Prädikatenlogik 0:44:02 Zusammenfassung 0:44:18 Übung 8: Prädikatenlogik 0:45:01 Prädikatenlogik: Syntax 0:48:48 Prädikatenlogik: Semantik 0:53:11...
15: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 05.12.2018
15 | 0:00:00 Start 0:01:42 Kapitel 13: Prädikatenlogik erster Stufe 0:02:09 Eine Grenze kontextfreier Grammatiken 0:03:50 Lvv - Beispielwörter 0:04:22 Lvv ist nicht kontextfrei 0:29:01 Überblick 0:30:15 Prädikatenlogische Formeln 0:32:10 Prädikatenlogische Formeln - der Aufwand lohnt sich 0:33:10 Terme - benötigte Alphabete 0:35:22 Terme - Syntax 0:37:41 Terme - Beispiel 0:42:11 Atomare Formeln - Syntax 0:45:53 Atomare Forlmeln - Beispiele 0:48:31 Prädikatenlogische Formeln - Syntax 0:50:51...
14: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 30.11.2018
14 | 0:00:00 Start 0:00:05 Ableitungsbaum 0:00:42 Wohlgeformte/ korrekte Klammerausdrücke 0:01:46 Arithmetische Ausdrücke 0:01:49 Ableitungsbaum 0:04:14 Wohlgeformte/ korrekte Klammerausdrücke 0:05:23 Arithmetische Ausdrücke 0:07:13 Syntax aussagenlogischer Formeln 0:08:55 Was ist wichtig 0:10:24 Wo sind wir? 0:11:37 Produkt von Relationen 0:17:45 Reflexiv-transitive Hülle einer Relation 0:22:01 Eigenschaften der reflexiv-transitiven Hülle 0:31:35 Was ist wichtig 0:32:22 Wo sind wir? 0:33:12...
13: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 28.11.2018
13 | 0:00:00 Start 0:00:21 Kapitel 12: kontextfreie Grammatiken 0:03:57 Versuch einer formalen Sprache 0:06:27 Lösbarkeit von L 0:09:18 Beweis des Lemmas - Teil 1 0:13:41 Beweis des Lemmas - Teil 2 0:25:01 Was ist wichtig 0:29:05 Kontextfreie Grammatiken 0:49:23 Beispiel 1:02:18 Ableitungsbäume sind übersichtlicher als schrittweise Ableitungen 1:09:49 Arithmetische Ausdrücke 1:19:39 Syntax aussagenlogischer Formeln 1:24:43 Was ist wichtig
12: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 23.11.2018
12 | 0:00:00 Start 0:02:12 Dokumente haben Inhalt, Struktur und Form 0:10:05 Struktur von Dokumenten 0:18:57 Beispiel für Tabelle in XHTML 0:30:27 Formale Sprachen kommen ins Spiel 0:33:23 Eine Grenze unserer bisherigen Vorgehensweise 0:37:25 Was ist wichtig? 0:42:17 Übung 6: Prozessor 0:46:56 Bitweise Operationen 0:52:36 MIMA Befehlssatz 0:58:25 Beispielprogramm 1:04:14 Links rotieren 1:08:09 Kontrollstrukturen 1:10:52 Verzweigung 1:13:42 Indirekte Speicherbefehle
11: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 21.11.2018
11 | 0:00:00 Start 0:00:13 Kapitel 10: Prozessor 0:00:24 Drähte 0:01:06 Register 0:01:59 Grobstruktur 0:05:07 die MIMA - ein idealisierter Prozessor 0:09:01 Vor-Neumann-Architektur vs...
10: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 16.11.2018
10 | 0:00:00 Start 0:00:05 Einheit 9:Speicher 0:00:14 Überblick 0:00:55 Formalisierungen sind Spezifikationen 0:03:14 Gesamtzustand eines Speichers 0:05:10 Formalisierung von Speicher 0:06:59 Lesen aus dem Speicher 0:09:14 Schreiben in den Speicher 0:11:59 Eigenschaften von Speicher 0:16:27 Wozu diese Formalisierungen? 0:17:23 Was ist wichtig 0:18:20 Kapitel 10:Prozessor 0:18:55 MIMA 0:20:00 Drähte verbinden Erzeuger und Verbraucher 0:22:26 Erzeuger für ein Bit 0:24:27 Drähte können mehrere...
09: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 14.11.2018
09 | 0:00:00 Start 0:00:33 Von Hexadezimal- zu Binärdarstellung 0:01:16 Übersetzungen 0:03:18 Wozu Übersetzungen 0:08:28 Codierungen 0:11:32 Homomorphismen 0:23:32 Präfixfreie Codes 0:26:59 Präfixfreie Codes: Decodierung 0:40:50 UTF-8 0:50:32 Huffman-Codierung 0:55:12 Algorithmus für Huffman-Codes 0:57:12 Konstruktion des Huffman-Baumes 1:04:02 Algorithmus für Huffman-Codes 1:08:35 Eigenschaften von Huffman-Codes 1:11:54 Block-Codierungen 1:18:44 Bit und Byte 1:21:09 Kleiner und großer...
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...
07: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 07.11.2018
07 | 0:00:00 Start 0:02:04 Erinnerung: formale Sprache 0:05:28 Produkte formaler Sprachen – Beispiele 0:10:38 Neutrales Element für Produkt formaler Sprachen 0:13:22 Potenzen von Sprachen 0:20:34 Potenzen mehrfach definiert 0:22:39 Konkatenationsabschluss von L 0:35:05 Zwei Warnungen 0:44:49 Dezimaldarstellung von Zahlen 0:50:22 Induktive Definitionen – ""über die Wortlänge"" 0:52:49 Binärdarstellung von Zahlen – Stellensystem zur Basis 2 0:56:50 Ein kleines Problem 1:00:13...