Grundbegriffe der Informatik, Vorlesung, WS18/19 Karlsruher Institut für Technologie (KIT)

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

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

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

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

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

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