Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

By Karlsruher Institut für Technologie (KIT)Education

Theoretische Grundlagen der Informatik, Vorlesung, WS19/20 episodes

November 21, 2019 08: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 19.11.2019
08 |
0:00:00 Start
0:07:42 Bemerkungen zur NTM
0:11:20 Zeitkomplexität für NTM
0:14:40 Die Klasse NP
0:18:28 P vs NP
0:24:03 Polynomiale Transformation
0:34:35 Das Problem SAT
0:39:55 Satz von Cook
0:43:37 Setup
0:48:19 Konstruktion der Variablen
1:05:51 Zwischenbilanz
1 hr 16 min
November 14, 2019 07: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 12.11.2019
07 |
0:00:00 Start
0:00:29 Letzte Vorlesung
0:04:12 Halteproblem
0:10:25 Die universelle Sprache
0:16:34 Satz von Rice - Motivation
0:20:52 Bemerkungen zum Satz von Rice
0:22:30 Das Post´sche Korrespondenzproblem
0:34:51 Eigenschaften von (semi-) entscheidbaren Sprachen
0:39:07 Komplexitätstheorie
0:42:09 Wie sieht das Problem aus?
0:47:37 Definition: Problem
0:49:42 Definition: Kodierungsschema
0:55:30 Äquivalenz von kodierungsschemata
0:57:11 Entscheidungsproblem
1:02:21 Zeitkomplexität
1:07:08 Schwierigkeit von Entscheidungs- und Optimierungsproblem
1:11:35 Algorithmus OPT-TOUR (als beweis) 1/2
1:16:27 Laufzeit des Algorithmus
1:18:26 Zwischenstand Komplexitätstheorie
1:21:56 Die Nichtdeterministische turing-Maschine
1:23:25 Die Orakel-Turing-Maschine
1 hr 29 min
November 07, 2019 06: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 07.11.2019
06 |
0:00:00 Start
0:01:05 (deterministische) Turing-Maschine
0:06:34 Beispiel-Turing-Maschine
0:16:35 Definitionen zur TM
0:19:46 Notation: Konfiguration
0:29:18 Definition: berechenbar/ totalrekursiv
0:42:20 Entscheidbarkeit und Berechenbarkeit
0:48:02 Korollar
0:49:57 Die Church´sche These
0:55:21 Erweiterung der Turing-maschine
0:59:49 Die universelle Turing-Maschine
1:03:07 Die Gödelnummer
1:13:24 Die Diagonalsprache
1:18:20 Unentscheidbarkeit der Diagonalsprache
1:21:17 Paradoxien und Selbstbezüglichkeit
1:23:10 Halteproblem
1 hr 28 min
October 31, 2019 05: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 31.10.2019
05 |
0:00:00 Start
0:00:39 Kapitel 2
0:07:31 Alternative Sicht – Beispiel
0:16:52 Wiederholung Äquivalemzklassenautomat
0:19:38 Rechtsinvarianz und Index
0:26:04 Nerode-Relation
0:29:50 Satz von Nerode
0:46:15 Korollar
0:52:35 Minimalität des Äquivalenzklassenautomats
0:55:26 Zusammenfassung
1:01:27 Turing-Maschinen und Berechenbarkeit
1:03:20 Die Registermaschine (RAM)
1:11:08 Formale Definition der Turingmaschine
1:18:14 Beispiel-Turing-Maschine
1 hr 25 min
October 29, 2019 04: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 29.10.2019
04 |
0:00:00 Start
0:00:41 Satz (Pumping-Lemma für reguläre Sprachen)
0:03:23 Satz (Verallgemeinertes Pumping-Lemma)
0:13:22 Beispiel (3) - Anwendung Verallgemeinertes PL
0:21:54 Finden nicht überflüssiger Zustände
0:29:44 Der Äquivalenzklassenautomat
0:49:04 Beispiel zur Vorgehensweise
0:57:27 Zusammenfassung
1:01:50 Testen Sie sich
1 hr 6 min
October 24, 2019 03: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 22.10.2019
03 |
0:00:00 Start
0:00:00 Start
0:00:20 Nichtdeterministische endliche Automaten
0:05:09 Zwischenstand
0:10:45 Entfernen von ɛ-Übergängen
0:21:09 EA -> Regularität
0:41:31 Beispiel
0:47:34 Satz von Kleene
0:48:58 Was können endliche Automaten nicht?
0:53:44 Pumping-Lemma für reguläre Sprachen
1:19:05 Zusammenfassung
1:20:03 Bemerkungen zu 'Testen Sie sich'-Aufgabe
1 hr 24 min
October 21, 2019 02: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 17.10.2019
02 |
0:00:00 Start
0:00:41 Kontextfreie Grammatiken
0:06:34 Kontextfreie Grammatiken - Beispiele
0:14:35 Endliche Automaten und Reguläre Sprachen
0:23:43 Nichtderterministische endliche Automaten
0:28:31 Beispiele für NEAs
0:31:52 Äquivalenz von NEAs und DEAs
0:34:54 Beispiel Potenzmengenkonstruktion
0:41:26 Erweiterung von ẟ
0:58:24 Induktionsanfang
1:13:24 Zusammenfassung
1 hr 20 min
October 17, 2019 01: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 15.10.2019
01 |
0:00:00 Start
0:03:28 Ziele der Vorlesung TGI
0:10:29 Wörter
0:20:06 Formale Sprachen
0:33:42 Reguläre Sprachen
0:38:59 Reguläre Ausdrücke
0:44:55 Reguläre Ausdrücke -Beispiele
0:53:09 Endliche Automaten
1 hr 7 min