Grundbegriffe der Informatik, Vorlesung, WS18/19

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 wichtig 1:15:25 Kapietel 22: MIMA-X 1:17:08 Ackermann-Funktion 1:20:13 Stapel oder Keller

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 Halbordnungen 0:41:49 eine Halbordnung auf Wörtern – darauf bauen wir später noch auf 0:43:37 Übung 0:44:44 Reguläre Ausdrücke 0:49:29 Ein regulärer Ausdruck für epsilon 0:54:44 Distributivgesetz 0:56:14 Kantorowitsch-Bäume 1:01:53 Kantorowitsch-Bäume und reguläre Ausdrücke 1:04:51 Beispiel: Zahlen spezifizieren 1:07:14 Ein Wiederbesuch: Wörter umkehren 1:11:32 Rechtslineare Grammatiken 1:15:16 Charakterisierung regulärer Sprachen 1:18:47 Linkslineare Grammatiken 1:23:40 Äquivalenz RL und LL Grammatiken

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 Kantorowitsch-Bäumen kann man z.B. reguläre Ausdrücke repräsentieren 0:56:25 Regex-Bäume -- etwas genauer 1:00:06 Vollständige Induktion über die Baumhöhe 1:04:44 Skizze des Induktionsschritts 1:12:15 Zusammenfassung 1:14:29 Äquivalenzrelationen 1:15:48 Kongruenz ganzer Zahlen modulo n 1:16:59 Beispiel: asymtptotisches gleiches Wachstum 1:17:33 Urbilder von Fuktionswerten

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 Akzeptoren: Vereinigung 1:03:32 Reguläre Sprachen und kontextfreie Grammatiken 1:07:38 Turing-Maschinen (TMs) 1:17:10 Analyse: Zeit- und Platzbedarf 1:18:56 TM: Akzeptor, Entscheider 1:25:34 TMs und endliche Akzeptoren 1:27:35 Church-Turing-These

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 Sprachen 1:01:54 Zeitkomplexität - der Rechenzeitbedarf einer TM 1:06:30 Raumkomplexität 1:07:49 Zeitkomplexität versus Raumkomplexität 1:09:48 Eine Komplexitätsklasse ist eine Menge von Problemen 1:11:35 P und PSPACE- Zwei wichtige Komplexitätsklassen 1:17:40 Unentscheidbare Probleme 1:19:46 Codierung von Turingmaschinen

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 Abbildungen 0:54:40 Master-Theorem 1:04:22 Über Asymptotik hinaus: Schleifendurchläufe zählen 1:07:55 Endliche Automaten 1:09:54 Mealy-Automaten und Zahlendarstellung 1:12:20 Moore-Automat: Beispiel aus der realen Welt 1:14:20 Zustandsfolge, Ausgabe 1:17:01 Umwandlung von Mealy- in Moore-Automaten

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

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 Relationen in Graphen 1:06:59 O-Kalkül 1:10:53 O-Kalkül: Logarithmen 1:13:13 O-Kalkül: Exponentialfunktionen 1:20:18 O-Kalkül: Fakultät

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: Graphen 0:48:34 Graphen: Darstellung von Relationen 0:52:35 Graphen: Maximale Anzahl Kanten 0:58:43 Pfad 1:03:16 (Streng) zusammenhängend 1:06:43 Zusammenhangskomponenten 1:09:13 Ein Paar (gerichtete) Standard-Graphen 1:13:24 Vollständiger Graph (ungerichtet) 1:17:28 Adjazenzmatrix

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*

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 Formulierungen in Prädikatenlogik 0:57:52 Totalität und Eindeutigkeit 1:00:18 Logische Äquivalenz 1:06:33 Allgemeingültig- und Erfüllbarkeit 1:11:21 Trinker-Paradoxon 1:15:04 Beispiel unerfüllbar 1:17:23 Substitutionen 1:19:58 Kollisionen 1:22:44 Gebundene Umbenennung

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 Prädikatenlogische Formeln - Beispiele 0:51:56 Was ist wichtig 0:52:48 Interpretetaion 0:58:02 val - ein Wert für jeden Term und ein Wahrheitswert für jede Formel 0:59:15 val - ein Wert in D für jeden Term 1:03:22 val - ein Wahrheitswert für jede atomare Formel 1:05:31 val - Bespiel für atomare Formeln 1:09:28 val - Wahrheitswert für quantifizierte Formeln 1:11:08 val - Beispiel für quantifizierte Formeln 1:14:01 Allgemeingültige Formeln 1:15:51 Allgemeingültige Formeln - aber keine Tautologien 1:18:38 Modelle 1:20:32 Modelle - Beispiel 1:22:55 Was ist wichtig

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 Eine Grenze kontextfreier Grammatiken 0:42:53 Übung 7: kontextfreie Grammatiken 0:43:23 Kontextfreie Grammatiken 0:47:49 Ableitungen 0:50:26 Ableitungsbaum 0:54:28 Warum ""kontextfrei""? 0:57:57 Palindrome – anna, otto und der reliefpfeiler 1:01:36 Nicht-Palindrome – abb, aabba, baabbab 1:04:14 Kontextfreie Sprachen 1:05:59 Vereinigung kontextfreier Sprachen 1:11:18 Schnitt kontextfreier Sprachen 1:14:09 Produkt von Relationen 1:20:18 Reflexiv, transitiv 1:22:38 Reflexiv-transitive Hülle

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 | 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 | 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 MIMA-Befehle - für die ALU 0:26:01 Arithmetik - Beispiel 0:30:55 Programmabarbeitung - normalerweise ganz einfach 0:33:44 Sprünge ändern die normale Reihenfolge der Programmabarbeitung 0:36:08 Rückwärtssprünge gehen natürlich auch 0:37:38 Bedingte Sprünge 0:39:33 Bedingter Sprüng - Beispiel 0:41:49 Mikroprogrammsteuerung der MIMA 0:44:21 Arbeitsweise der MIMA - für jeden Maschinenbefehl ein Mikroprogramm 0:46:28 MIMA - die Minimalmaschine ist idealisierter Prozessor 0:47:09 MIMA - Befehlsholphase 0:55:55 MIMA- Befehlsdecodierungsphase 1:00:48 Ein Beispielprogramm 1:01:10 Aufsummieren einer Liste von Zahlen 1:04:45 Aufsummieren - Initialisierungen 1:07:00 Aufsummieren - Iteration über die Elemente 1:16:12 Wir halten fest

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 Erzeugerausgänge mit Verbrauchern verbinden 0:28:36 EInfaches Speicher-Element für ein Bit 0:29:41 Arbeitsweise des Speicher-Elements 0:31:16 Register 0:34:01 John von Neumann 0:35:28 Grundstruktur der MIMA: Von-Neumann-Architektur 0:38:02 Hauptspeicher für die MIMA 0:39:56 Prozessor 0:40:54 Die MIMA 0:42:56 Übung 5: Codierungen 0:44:11 Homomorphismen 0:47:35 Induzierter Homomorphismus 0:51:03 Umrechnung von Zahlensystemen 0:53:10 Zahlendarstellungen und Homomorphismen 0:56:28 Die andere Richtung 0:58:42 Codierungen 1:02:16 Präfixfrei 1:08:23 Komprimierend 1:12:05 Huffman-Codierung 1:16:55 Huffman-Codierung nicht eindeutig 1:18:46 Block-Codierung

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 Dezimale Größenpräfixe

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

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 k-äre Darstellung von Zahlen 1:03:33 Operationen di und mod 1:09:27 Die Definition von Reprk ist sinnvoll 1:14:36 Numk ist linksinvers zu Reprk 1:19:06 Unübliche Methode für negative Zahlen 1:24:16 Rechnen in Zk