Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 08.02.2017, 26

Grundbegriffe der Informatik, Vorlesung, WS16/17

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 und größte Elemente 0:14:14 Beispiele kleinster und größter Elemente 0:15:22 Das kleinste und das größte Element sind eindeutig 0:16:02 Untere und obere Schranken von T - unter Umständen auch außerhalb von T 0:16:52 Untere und obere Schranken: Beispiele 0:17:27 Untere und obere Schranken müssen nicht existieren 0:18:43 Supremum und Infimum 0:19:45 Supremum und Infimum: Beispiele 0:21:47 Aufsteigende Ketten 0:23:08 Vollständige Halbordnungen 0:24:34 Vollständige Halbordnungen: weitere (Nicht-)Beispiele 0:27:09 Monotone Abbildungen 0:28:20 Stetige Abbildungen 0:29:14 Stetige Abbildungen: Beispiel 1 0:31:15 Stetige Abbildungen: Beispiel 2 0:32:10 Fixpunktsatz 0:33:58 Fixpunktsatz: Beweis 0:37:13 Was ist wichtig 0:38:25 Totale Ordnung - keine unvergleichbaren Elemente 0:40:27 Totale Ordnungen auf A* 0:42:16 Lexikographische Ordnung (Wörterbuch) 0:45:37 Lexikographische Ordnung <> - die im Wörterbuch 0:46:07 Lexikographische Ordnung 0:48:12 Lexikographische Ordnung <> 0:49:31 Die lexikographischen Ordnungen sind total 0:51:00 Was ist wichtig (2) 0:51:42 Kapital 22: MIMA-X 0:51:55 MIMA-X - eine Erweiterung der MIMA 0:53:20 Erinnerung: die Ackermann-Funktion A 0:54:00 Ackermann-Funktion Beispielberechnung für A(2,2) 0:54:18 Ackermann-Funktion A(2,2) kompakt notiert 0:56:27 Stapel oder Keller - Zugriff nur auf das oberste Element 0:58:04 Stapel - eine mögliche ""Implementierung"" 0:58:27 Stapel - bequeme Verallgemeinerung 0:58:54 Berechnung der Ackermann-Funktion mit einem Stapel 1:00:25 Jede k-stellige Operation auf V ist auf Stapel mit mindestens k Einträgen übertragbar 1:02:01 Stapel - Implementierung in einem Rechner 1:03:36 Mimax- drei zusätzliche Register für Adressen 1:05:53 Register RA speichert eine Rückkehradresse 1:06:42 CALL und RET - Wiederverwendung von Codestücken durch primitiven Unterprogrammaufruf 1:08:12 SP und FP 1:08:59 Speicherzugriffe mittels SP 1:09:49 Veränderungen des SP-Registers 1:10:34 Realisierung von push, top und pop 1:11:30 push und pop von RA - für ineinander geschachtelte CALL 1:13:09 Wir halten fest