26 | 0:00:00 Starten 0:00:04 Kapitel 21: Relationen 0:00:59 Antisymmetrische Relationen 0:03:57 Halbordnungen 0:05:52 eine Halbordnung auf Wörtern - darauf bauen wir später noch auf 0:07:28 Wenn man weiß, dass es eine Halbordnung ist, enthält der gesamte Graph Redundantes 0:08:51 Wenn man weiß, dass es eine Halbordnung ist, genügt das Hassediagramm 0:10:31 Das Hassediagramm enthält > 0:11:32 Minimale und maximale Elemente 0:12:56 Beispiele minimaler und maximaler Elemente 0:13:22 Kleinste...

27 | 0:00:00 Starten 0:00:04 Aufgabe 6.1 0:04:44 Aufgabe 6.2 0:11:12 Aufgabe 6.3 0:16:19 Aufgabe 6.4 0:22:26 Aufgabe 7.1 0:28:13 Aufgabe 7.2 0:36:24 Aufgabe 7.3 0:39:42 Aufgabe 7.4

25 | 0:00:00 Starten 0:00:04 Kapitel 20: Turingmaschinen 0:00:25 Wo sind wir? 0:01:45 Codierungen von Turingmaschinen 0:04:54 Beispielcodierung 0:09:44 Eigenschaften dieser und ähnlicher Codierungen 0:11:50 Das Halteproblem ist unentscheidbar 0:18:37 Diagonalisierung 0:24:07 Das Halteproblem 0:24:22 Beweis der Unentscheidbarkeit des Halteproblems 0:28:37 Weitere unentscheidbare Probleme 0:36:10 Erinnerung: BB3 0:37:03 Bibermaschinen 0:38:26 Busy-Beaver-Funktion 0:42:51 Was ist...

24 | 0:00:00 Starten 0:00:59 Algorithmusbegriss informell 0:03:47 Erinnerung: partielle Funktion von A nach B 0:05:39 Turingmaschinen: Ursprung 0:08:33 Eine Turingmaschine im Bild 0:13:48 Turingmaschine formalisiert 0:15:28 Turingmaschine: graphische Darstellung 0:19:23 Turingmaschine: tabellarische Darstellung 0:20:26 Beispielberechnung 0:23:01 Turingmaschine: Konfigurationen 0:25:48 Turingmaschine: "" überschaubare"" Bandbeschriftungen 0:27:48 Ein Schritt einer Turingmaschine 0:30:31...

23 | 0:00:00 Starten 0:00:05 Beispiel einer nicht erkennbaren Sprache 0:03:01 Beispiel einer nicht erkennbaren Sprache (2) 0:06:44 Beispiel einer nicht erkennbaren Sprache (3) 0:12:49 Was ist wichtig 0:14:26 Zusammenfassung 0:15:48 Was können endliche Akzeptoren 0:16:20 Überblick 0:18:46 Der Begriff regulärer Ausdruck hat heute verschiedene Bedeutungen 0:19:49 Definition regulärer Ausdrücke (1) 0:22:58 Beispiele 0:23:44 Klammereinsparungsregeln 0:25:01 Beispiele für...

22 | 0:00:00 Starten 0:00:04 Einheit 17: Quantitative Aspekte von Algorithmen 0:01:45 Rechenzeiten 0:13:35 Was ist wichtig 0:14:07 Zusammenfassung 0:14:55 Kapitel 18: Endliche Automaten 0:15:46 Ein primitiver Getränkeautomat 0:16:47 Getränkeautomat: Zustände 0:19:27 Getränkeautomat: Eingaben 0:21:18 Getränkeautomat: Zustandsübergänge 0:29:52 Getränkeautomat: Aufgaben 0:35:07 Maely-Automaten 0:37:33 Verallgemeinerte Zustandsübergangsfunktionen 0:45:08 Verallgemeinerte Ausgabenfunktion 0:49:09...

21 | 0:00:00 Starten 0:00:05 Aufgabe 5.1 0:06:10 Aufgabe 5.2 0:10:56 Aufgabe 5.3 0:16:29 Aufgabe 5.5 0:21:42 Aufgabe 5.4 0:24:40 Aufgabe 5.6 0:31:26 Aufgabe 5.7 0:32:52 Catalan-Zahl 0:33:38 Eigenschaften 0:41:01 Aufgabe 5.8 0:49:49 Aufgabe 5.1 0:55:42 Aufgabe 5.7

15 | 0:00:00 Starten 0:01:12 Aufgabe 3.6 0:23:38 Aufgabe 3.5 0:45:35 Aufgabe 3.3 1:14:43 Aufgabe 3.2 - 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...

20 | 0:00:00 Starten 0:09:28 Warum keine exakten Angaben? 0:11:05 Wie ungenau wollen wir über Funktionen reden? 0:12:15 Zu Notation und Redeweise 0:15:53 Erläuterungen zur Definition von f=g 0:20:14 Beispiel 0:25:02 Nichtbeispiele 0:28:58 Äquivalenzrelation 0:29:18 Relation ist refleixiv und symmetrisch 0:30:57 Relation ist transitiv 0:32:42 Groß 0:33:41 einfache Rechenregel 0:34:39 Obere und untere Schranken 0:38:05 Beispiel 0:45:45 Einfache Beobachtungen 0:46:47 Für die Lektüre leider...

19 | 0:00:00 Starten 0:00:04 Überblick - Einheit 16 0:00:11 Adjazenzmatrix eines gerichteten Graphen 0:00:54 Wegematrix eines Graphen 0:02:44 Matrizenmultiplikation 0:02:56 Algorithmus für Matrizenmultiplikation 0:03:10 Quadrierte Adjazenzmatrix 0:03:33 Matrizenaddition 0:03:59 Berechnung von E* - die naheliegende Idee 0:06:13 Beseitigung der unendlichen Vereinigung 0:10:27 Potenzen der Adjazenzmatrix haben eine Bedeutung 0:11:27 Signum-Funktion 0:13:10 Matrizendarstellung für E^k - sgn(A^k)...

18 | 0:00:00 Starten 0:00:04 Aufgabe 4.1 0:13:31 Aufgabe 4.2 0:30:12 Aufgabe 4.3

17 | 0:00:00 Starten 0:00:04 Kapitel 15: Graphen 0:00:16 Wo sind wir? Ungerichtete Graphen 0:12:44 Ungerichtete Bäume 0:17:24 Knotengrad in ungerichteten Graphen 0:19:28 Symmetrische Relationen 0:21:14 Äquivalenzrelationen 0:23:40 Beschriftete Graphen 0:28:51 Färbungen von Graphen 0:30:54 Gewichtete Graphen 0:40:09 Erste Algorithmen in Graphen 0:42:24 Repräsentation von Graphen im Rechner 0:42:43 Objekte im Rechner 0:47:51 Adjazenzlisten 0:48:35 Inzidenzisten 0:49:12 Variante von...

16 | 0:00:00 Starten 0:00:52 Logisch äquivalente Formeln 0:07:01 Weitere allgemeingültige Formeln 0:10:02 Deduktionstheorem 0:13:22 Skizze eines Beispiels 0:24:55 Großzügige Benutzung von Prädikatenlogik 0:27:04 Zusammenfassung 0:27:58 Kapitel 14 0:29:57 Eine Zeitreise...wohin?... 0:30:29 ...da wären wir... 0:32:35 Zwei wichtige Schriften von al-Kharizmi 0:40:00 Algorithmusbegriff informell 0:48:49 Korrektheit eines Algorithmus 0:50:02 Beweis von al_Khwarizmi 0:53:51 Beweis durch...

14 | 0:00:00 Starten 0:04:48 Neutrale Elemente 0:14:29 Prädikatenlogische Formeln – Beispiele 0:17:15 Interpretationen 0:23:47 val (D,I,ß) - ein Wert für jeden Term und ein Wahrheitswert für jede Formel 0:40:58 Allgemeingültige Formeln 0:46:57 Modelle 0:52:34 Was ist wichtig 0:54:45 Vorkommen von Variablensymbolen in Formeln 1:02:17 Substitutionen 1:14:20 Weitere allgemeingültige Formeln 1:15:42 Kalküle 1:17:43 Axiome 1:21:12 Schlussregeln 1:22:30 Ableitungen – formal gefasst 1:24:49 Beweis...

13 | 0:00:00 Starten 0:00:05 Kapitel 12: kontextfreie Grammatiken 0:00:58 Kontextfreie Grammatik 0:01:41 Ableitungsbaum 0:02:24 Arithmetische Ausdrücke 0:08:35 Syntax aussagenlogischer Formeln 0:10:57 Was ist wichtig 0:11:30 Wo sind wir?: Relationen (Teil 2) 0:12:20 Produkt von Relationen 0:15:56 Reflexiv-transitive Hülle einer Relation - Vereinigung aller Potenzen 0:17:05 Reflexiv-transitive Hülle einer Relation - ein Beispiel 0:19:11 Eigenschaften der reflexiv-transitiven Hülle 0:19:57...

12 | 0:00:00 Starten 0:00:04 Wo sind wir? 0:01:15 Auszug aus der DTD für Tabellen in XHTML 0:03:04 Interpretation der DTD für Tabellen in XHTML 0:05:15 Beispiel für Tabelle in XHTML 0:06:56 Latex (1) 0:11:44 Latex (2) 0:13:30 Grobstruktur von Latex-Dokumenten 0:15:21 Listen mit Latex 0:16:56 Formale Sprachen kommen ins Spiel 0:20:29 Eine Grenze unserer bisherigen Vorgehensweise 0:23:59 Was ist wichtig (1) 0:25:07 Kapitel 12: kontextfreie Grammatiken 0:26:08 Spezifikation von formalen...

11 | 0:00:00 Starten 0:00:08 Aufgabe 2.1 0:06:26 Aufgabe 2.2 0:19:43 Aufgabe 2.3 0:21:33 Aufgabe 2.4 0:34:48 Aufgabe 2.5 0:47:37 Aufgabe 2.6 0:55:14 Aufgabe 2.7

10 | 0:00:00 Starten 0:00:06 Kapitel 10: Prozessor 0:00:47 MIMA – die Minimalmaschine ist ein idealisierter Prozessor 0:02:18 Überblick 0:02:55 Drähte verbinden »Erzeuger« und »Verbraucher« 0:06:46 »Erzeuger« für ein Bit 0:09:24 Drähte können mehrere Erzeugerausgänge mit Verbrauchern verbinden 0:11:29 Einfaches »Speicher-Element« für ein Bit 0:12:45 Arbeitsweise des Speicher-Elements 0:13:53 Wo sind wir? Grobstruktur der MIMA 0:14:48 Von-Neumann-Architektur vs. Harvard-Architektur 0:20:01...

09 | 0:00:00 Starten 0:00:05 Einheit 8: Codierungen 0:00:20 Übersetzungen – bedeutungserhaltende Abbildungen 0:00:30 Homomorphismen – mit Konkatenation verträgliche Abbildungen 0:01:15 Homomorphismen lassen das leere Wort unverändert 0:01:37 Homomorphismen – die Bilder einzelner Symbole legen alles fest 0:04:01 Homomorphismen – die Bilder einzelner Symbole legen alles fest (2) 0:07:17 Präfixfreie Codes 0:09:09 Präfixfreie Codes: Decodierung 0:14:23 Präfixfreie Codes: Decodierung (2) 0:15:35...

07 | 0:00:00 Starten 0:00:05 Aufgabe 1.1 0:01:51 Aufgabe 1.2 0:04:44 Aufgabe 1.3 0:09:05 Aufgabe 1.4 0:16:40 Aufgabe 1.5 0:25:32 Aufgabe 1.6 0:58:29 Aufgabe 1.7

08 | 0:00:00 Starten 0:00:24 Wo sind wir? 0:01:27 Noch offene Frage: Ist jede Zahl darstellbar? 0:01:41 k-äre Darstellung von Zahlen (1) 0:05:05 Operationen div und mod 0:06:48 k-äre Darstellung von Zahlen (2) 0:09:27 Die Definition von Repr ist sinnvoll. (1) 0:11:12 Die Definition von Repr ist sinnvoll. (2) 0:15:48 Num ist linksinvers zu Repr (1) 0:18:18 Num ist linksinvers zu Repr (2) 0:22:05 Unübliche Mehode für negative Zahlen – mit der Ziffer ""meins"" 0:25:17 Unübliche Mehode für...

06 | 0:00:00 Starten 0:00:38 Eine Erinnerung 0:01:28 Induktive Definitionen kann man zum Rechnen benutzen 0:02:45 Das Lemma über Wortlängen - einfache Fälle 0:04:45 Vollständige Induktion 0:11:08 Vollständige Induktion: Varianten 0:13:06 Verallgemeinerung vollständiger Induktion - mit Rückgriff auf viele frühere Formeln 0:14:54 Eine Verallgemeinerung vollständiger Induktion 0:17:45 Beispiel - noch mal Potenzen von Wörtern 0:18:57 Ackermann-Funktion 0:21:39 Rechenbeispiel 0:31:34 Erinnerung:...

05 | 0:00:00 Starten 0:00:04 Kapitel 5: Aussagenlogik 0:00:38 Wo sind wir? Semantik aussagenlogischer Formeln 0:01:08 Ziel: Bedeutung einer aussagenlogischen Formel – eine boolesche Funktion 0:03:34 Auswertung von Formeln 0:06:42 Auswertung von Formeln – ein Beispiel 0:07:41 Auswertung einer Formel für alle Interpretationen 0:09:26 Äquivalente Formeln 0:12:25 Kleine Randbemerkung – Auffassung einer Formel als Abbildung 0:19:35 Modelle 0:22:57 Wichtige Spezialfälle aussagenlogischer...

04 | 0:00:00 Starten 0:00:21 Beispiel: Aufbau von E-Mails 0:00:21 RFC 0:00:28 E-Mail, RFC 5322 (1) 0:00:38 E-Mail, RFC 5322 (2) 0:05:04 E-Mail, RFC 5322 (3) 0:05:52 E-Mail, RFC 5322 (4) 0:07:29 Iterierte Konkatenation 0:07:47 Iterierte Konkatenation: Potenzen von Wörtern 0:11:05 Induktive Definitionen kann man zu Rechnen benutzen 0:12:23 Ein einfaches Lemma zu Längen von Wortpotenzen 0:15:37 Das einfach Lemma - einfache Fälle 0:17:08 Vollständige Induktion - kurzer Ausblick 0:19:21 Formale...