Grundbegriffe der Informatik, Vorlesung, WS18/19

Grundbegriffe der Informatik, Vorlesung, WS18/19 episodes:

• 02.07.2019

  26: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 06.02.2019

  26 | 0:00:00 Start 0:00:30 Halbordnungen 0:09:59 Minimale und maximale Elemente/ Beispiel 0:18:32 Untere und obere Schranken/-Beispiel 0:23:29 Supremum und Infimum/-Beispiele 0:36:03 Monotone Abbildungen 0:38:54 Stetige Abbildungen/-Beispiele 0:43:57 Fixpunktsatz/-Beweis 0:52:57 Was ist wichtig ? 0:54:44 Ordungen 0:55:28 Totale Ordung 1:00:06 Totale Ordung auf A* 1:02:30 Milchstraße-Milch-Milchreis-- Beispiel 1:04:08 Lexikographische Ordung (Wörterbuch) 1:14:07 Was ist...

  
• 02.04.2019

  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...

  
• 01.31.2019

  24: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 30.01.2019

  24 | 0:00:00 Start 0:00:39 Wiederholung(Turingmaschinen) 0:02:42 Endliche Automaten 0:03:56 Reguläre Ausdrücke 0:07:50 Klammereinsparungsregeln 0:12:41 Durch R Beschriebene formale Sprachen / Beispiel 0:14:49 Beispiele für R 0:27:56 Charakterisierungen regulärer Sprachen 0:34:39 Rechtslineare Grammatiken (Typ 3) 0:39:02 Rechtslineare Grammatiken: Beispiele 0:44:42 Sprechweisen 0:47:29 Vorteile rechtslinearer Grammatiken 0:49:49 Kantorowitsch-Bäume und strukturelle Induktion 0:52:31 Mit...

  
• 01.29.2019

  23: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 25.01.2019

  23 | 0:00:00 Start 0:00:05 Turingmaschinen 0:04:32 Unentscheidbare Probleme 0:04:59 Beispielcodierung 0:16:51 Das Halteproblem 0:19:24 Beweis mit Diagonalisierung 0:30:28 Weitere unentscheidbare Probleme 0:34:48 Erinnerung: BB3 0:36:22 Fleißige Biber und die Busy-Beaver-Funktion 0:43:20 Steam-Powered Turing Machine ;-) 0:44:04 Zusammenfassung 0:44:25 Beginn der Übung 0:44:56 Endlicher Akzeptor 0:48:28 Beispiele regulärer Sprachen 0:52:19 Akzeptoren: Komplement 0:54:53 Akzeptoren: Schnitt 0:59:54...

  
• 01.24.2019

  22: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 23.01.2019

  22 | 0:00:00 Start 0:00:40 Endliche Automaten 0:02:22 Beispiel einer nicht erkennbaren Sprache 0:13:53 Zusammenfassung / Was ist wichtig ? 0:16:19 Turingmaschinen 0:19:33 Eine Turingmaschine im Bild 0:25:27 Turingmaschine: graphische Darstellung/ tabellarische Darstellung 0:28:42 Beispielberechnung 0:35:53 Längere Beispielberechnung von BB3 0:37:56 Berechnung und Endkonfigurationen 0:48:04 Beispiel: Palindromerkennung 0:56:10 Entscheidbare und aufzählbare...

  
• 01.21.2019

  21: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 18.01.2019

  21 | 0:00:00 Start 0:00:30 mMealy-Automaten 0:04:21 Verallgemeinerte Zusatndsübergangsfunktionen 0:06:09 Verallgemeinerte Ausgabefunktionen 0:07:47 Was ist wichtig 0:10:21 Moore-Automat 0:12:43 Verallgemeinerte Zusatndsübergangsfunktionen 0:13:44 Verallgemeinerte Ausgabefunktionen 0:20:06 Endliche Akzeptoren 0:22:59 Akzeptierte und abgelehnte Wörter 0:25:13 Erkannte formale Sprache 0:43:00 Übung 12: asymptotische Analyse und endliche Automaten 0:43:57 Operationen auf Abbildungen 0:50:56 Noch etwas O-Kalkül: unvergleichbare...

  
• 01.17.2019

  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...

  
• 01.10.2019

  19: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 09.01.2019

  19 | 0:00:00 Start 0:00:25 Groß-O-Notation 0:15:24 Groß-O-Notation: Notation für obere und untere Schranken des Wachstums 0:25:37 Groß-O-Notation: Eine grauenhafte Schreibweise 0:35:40 Groß-O-Notation: Was ist wichtig 0:37:41 Matrizenmultiplikation: 2x2 Matrizen 0:40:07 nxn Matrizen 0:42:04 Übung 0:43:09 Erinnerung: Matrixmultiplikation 0:46:06 Adjazenzmatrizen 0:48:50 Erreichbarkeitsmatrizen 0:53:02 Wegematrix 0:55:02 Adjazenz- und Wegematrix: Eindeutigkeit 0:57:54 Zusammenhang Matrizen und...

  
• 12.27.2018

  18: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 21.12.2018

  18 | 0:00:00 Start 0:00:05 Einfachster Algorithmus für die Wegmatrix 0:12:27 Es geht noch besser – erst mehr denken dann weniger rechnen 0:21:11 Algorithmus von Warshall 0:27:56 Quantitative Aspekte von Algorithmen 0:29:38 Ressourcen für Rechnungen 0:37:01 Warum keine exakten Angaben 0:39:46 Zu Notation und Redeweise 0:44:15 Übung 10:...

  
• 12.21.2018

  17: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 19.12.2018

  17 | 0:00:00 Start 0:00:41 Gerichtete Graphen 0:14:08 Ungerichtete Graphen 0:25:12 Ungerichtete Bäume 0:30:42 Symmetrische Relationen 0:32:12 Äquivalenzrelationen 0:36:15 Erste Algorithmen in Graphen 0:41:25 Adjazenzlisten 0:47:18 Repräsentation von Relationen durch Matrizen 0:48:35 Wegematrix eins Graphen 0:55:40 2-Erreichbarkeit an einem Bespiel 0:56:35 Systematische Suche nach Pfaden im Beispiel 1:07:00 Berechnung von E*

  
• 12.10.2018

  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...

  
• 12.06.2018

  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...

  
• 12.03.2018

  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...

  
• 11.29.2018

  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...

  
• 11.26.2018

  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...

  
• 11.22.2018

  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. Harvard-Architektur 0:10:24 Maschinenbefehle 0:11:45 MIMA- Befehle 0:15:54 LAden und Speichern - Beispiel 0:18:59 MIMA-Befehle - Datentransport mit indirekter Adressierung 0:21:17 Laden mit indirekter Adressierung - Beispiel 0:22:36...

  
• 11.19.2018

  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...

  
• 11.15.2018

  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 Speicher 1:23:12...

  
• 11.13.2018

  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...

  
• 11.08.2018

  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...

  
• 11.05.2018

  06: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 02.11.2018

  06 | 0:00:00 Start 0:00:17 Vollständige Induktion 0:10:03 Varianten der vollständigen Induktion 0:16:24 Verallgemeinerung 0:25:47 Induktive Definitionen 0:28:28 Ackermann-Funktion 0:37:33 Was ist wichtig? 0:41:28 Anfang der Übung 0:41:56 Boolesche Funktion 0:43:50 Interpretation 0:46:59 Unterscheidung Syntax/Semantik 0:48:50 Gleichheit von Formeln 0:51:20 Wahrheitstabelle...

  
• 11.02.2018

  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...

  
• 10.30.2018

  04: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 26.10.2018

  04 | 0:00:00 Starten 0:00:03 Kapitel 5: Aussagenlogik 0:02:21 Alphabet der Aussagenlogik 0:04:29 Konstruktionsabbildungen 0:07:24 Lesearten 0:08:09 Syntax Konstruktion immer größerer Formeln 0:19:33 Boolesche Funktionen 0:29:37 Semantik aussagenlogischer Formeln 0:35:14 Übung 2: Wörter, binäre Operationen und Aussagenlogik 0:35:37 Wörter 0:38:10 Das leere Wort 0:39:25 Mengen von Wörtern 0:42:30 Unterscheidung Symbol / Wort 0:44:26...

  
• 10.25.2018

  03: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 24.10.2018

  03 | 0:00:00 Start 0:17:21 Pünktchen vermeiden 0:18:31 Konkatenation 0:23:57 Umgehen mit Definitionen 0:29:09 Das leere Wort 0:37:11 Eigenschaften der Konkatenation 0:40:16 Beispiel: Aufbau von Emails. 0:40:42 RFC 0:41:59 Emails 0:46:23 Iterative Konkatenation 0:50:02 Induktive Definitionen kann man zu Rechnen benutzen 0:52:04 ein einfaches Lemma zu Längen von Wortpotenzen 0:53:26 Ein einafaches...

  
• 10.25.2018

  02: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 19.10.2018

  02 | 0:00:00 Start 0:00:03 Kapitel 3: Mengen, Alphabete, Abbildungen 0:00:23 Themen dieses Kapitels 0:00:31 ASCII-Zeichensatz und Unicode 0:01:01 ASCII-Zeichensatz 0:02:06 Emails 0:04:08 Unicode: Code Points 0:04:50 Paare – anders als Mengen 0:05:55 Kartesisches Produkt zweier Mengen 0:08:02 Kartesische Produkte vieler Mengen 0:14:26 Induktive Definitionen 0:18:22 Relationen 0:21:22 Abbildungen als spezielle...

  
• 10.19.2018

  01: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 17.10.2018

  01 | 0:00:00 Start 0:00:36 Kapitel 1 0:04:33 Ziele der Vorlesung 0:08:14 Kapitel 2 0:09:27 Themen dieses Kapitels 0:09:51 Informatik 0:11:27 Informatik: Aufbau 0:15:01 Kunstwort Informatik 0:15:49 Signal, Inschrift, Nachricht 0:15:54 Was steht hier? 0:17:26 Signal 0:19:44 Übertragung und Speicherung von Mitteilungen 0:21:53 Nachricht 0:23:14 Information 0:27:43 Datum 0:29:25 Was ist wichtig 0:31:30 Kapitel 3 0:32:49 Themen...