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

Grundbegriffe der Informatik, Vorlesung, WS18/19

26: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 06.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 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

25: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 01.02.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 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

24: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 30.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 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

23: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 25.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 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

22: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 23.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 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

21: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 18.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 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

20: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 16.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 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

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

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

18: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 21.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*

17: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 19.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 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

16: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 07.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 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

15: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 05.12.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 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

14: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 30.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

13: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 28.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

hubhopper

Grundbegriffe der Informatik, Vorlesung, WS18/19

hubhopper