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

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

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

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

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

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

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

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

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

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*