Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 03.02.2017, 25 Grundbegriffe der Informatik, Vorlesung, WS16/17

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 wichtig
0:43:53 Steam-Powered Turing Machine
0:47:48 Zusammenfassung
0:51:51 Kapitel 21: Relationen
0:52:28 Überblick
0:52:51 Äquivalenzrelationen
0:53:41 Identität
0:54:18 Kongruenz ganzer Zahlen modulo n
0:55:12 Beispiel: asymptotisch gleiches Wachstum
0:55:24 Urbilder von Funktionswerten
0:57:50 Bild einer Äquivalenzrelation
0:59:27 Äquivalenzklassen und Faktormengen
1:00:40 Beispiel: Äquivalenzklassen und Kogruenz modulo 2
1:02:21 Was ist wichtig
1:02:49 Äquivalenzrelationen auf Mengen mit ""Struktur""
1:03:27 Verträglichkeit von Äquivalenzrelationen mit Abbildungen
1:05:49 Kongruenzrelation
1:06:28 Eine Operation für Äquivalenzklassen modulo n?
1:08:20 Verträglichkeit erlaubt die Übertragung einer Abbildung auf der Faktormenge
1:09:14 eine Operation für Äquivalenzklassen modulo n?
1:10:10 Was ist wichtig
1:10:54 Wo sind wir?
1:11:02 Motivation
1:13:02 Äquivalenzrelationen von Nerode einer Sprache
1:14:30 Beispiel
1:18:35 Die Nerode-Relation is immer eine Äquivalenzrelationen
1:19:09 Verträglichkeit: Beisoiel Nerode-Äquivalenzen
1:20:44 Eine Abbildung für Nerode-Äquivalenzklassen
1:21:22 Nerode-Äquivalenzen: Ausblick