Podcasts by Theoretische Grundlagen der Informatik, Vorlesung, WS17/18
Theoretische Grundlagen der Informatik, Vorlesung, WS17/18
Further podcasts by Karlsruher Institut für Technologie (KIT)
Podcast on the topic Kurse
All episodes
01: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 17.10.2017 from 2021-01-31T22:10:42.023393
01 | 0:00:00 Starten 0:01:06 Ziel der Vorlesung TGI 0:07:08 Wiederholung aus Grundbegriffe der Informatik 0:09:11 Wörter 0:13:56 Formale Sprachen 0:25:28 Reguläre Sprachen 0:32:09 Reguläre Ausdrüc...
Listen02: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 19.10.2017 from 2021-01-31T22:10:42.023393
02 | 0:00:00 Starten 0:00:38 Endliche Automaten und Reguläre Sprachen 0:16:02 Nichtdeterministische endliche Automaten 0:22:10 Beispiele für NEA's 0:27:11 Äquivalenz von NEA's und DEA's 0:28:54 Be...
Listen03: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 24.10.2017 from 2021-01-31T22:10:42.023393
03 | 0:00:00 Starten 0:00:05 letzte Vorlesung... 0:05:42 Entfernen von Epsilon-Übergängen 0:16:09 EA-Regularität 0:37:53 Beispiel 0:52:18 Frage: Was können endliche Automaten nicht? 0:55:53 Pumpin...
Listen04: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 02.11.2017 from 2021-01-31T22:10:42.023393
04 | 0:00:00 Starten 0:01:20 Pumping-Lemma für reguläre Sprachen 0:08:08 Verallgemeintertes PL für reguläre Sprachen 0:23:36 Beispiel 0:31:37 Äquivalenz 0:34:26 Der Äquivalenzklassenautomat 0:44:2...
Listen05: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 07.11.2017 from 2021-01-31T22:10:42.023393
05 | 0:00:00 Starten 0:00:21 Frage 0:04:24 Wiederholung Äquivalenzklassenautomat 0:09:44 Definitionen: Rechtsinvarianz und Index 0:17:24 Nerode- Relation 0:22:12 Satz von Nerode 0:25:40 Beweis zu ...
Listen06: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 14.11.2017 from 2021-01-31T22:10:42.023393
06 | 0:00:00 Starten 0:01:54 Formale Definition der Tuting-Maschine 0:04:18 Definition zur TM 0:07:42 Motation: Konfiguration 0:10:03 Beispiel: Konfiguration 0:20:09 Definition: berechenbar/ total...
Listen07: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 16.11.2017 from 2021-01-31T22:10:42.023393
07 | 0:00:00 Starten 0:00:06 Definitionen zur TM 0:01:15 Unentscheidbarkeit der Diagonalsprache 0:02:42 Die Universelle Sprache 0:09:51 Satz von Rice - Motivation 0:17:10 Das Post'sche Korresponde...
Listen08: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 21.11.2017 from 2021-01-31T22:10:42.023393
08 | 0:00:00 Starten 0:00:17 Gliederung 0:01:30 Turingmaschinen 0:19:04 Erweiterung von Turingmaschinen 0:19:18 Mehrere Spuren 0:23:26 Mehrere Bänder 0:25:01 Erweiterte Turingmaschinen 0:31:56 Ent...
Listen09: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 28.11.2017 from 2021-01-31T22:10:42.023393
09 | 0:00:00 Starten 0:00:39 NP-Vollständigkeit 0:02:03 Transitivität der poly. Transformation 0:02:31 Korollar 0:03:49 Das Problem 3-SAT 0:05:37 Beweis: NP-Vollständigkeit von 3-SAT 0:20:16 Das P...
Listen10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 05.12.2017 from 2021-01-31T22:10:42.023393
10 | 0:00:00 Starten 0:03:27 Das Problem SUBSET SUM 0:04:50 NP-Vollständigkeit von SUBSET SUM 0:18:59 Das Problem Partition 0:25:38 Das Problem KNAPSACK 0:28:21 Beweis: NP-Vollständigkeit von KNAP...
Listen11: Theoretische Grundlagen der Informatik, Übung, WS 2017/18, 12.12.2017 from 2021-01-31T22:10:42.023393
11 | 0:00:00 Starten 0:00:57 Nichtdeterministische Turingmaschine(n) 0:06:41 Die Klassen NP und ANP 0:11:10 A-NTMs sind nicht mächtiger als NTMs 0:23:31 Polynomiale Transformation 0:25:23 Polynomi...
Listen12: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 14.12.2017 from 2021-01-31T22:10:42.023393
12 | 0:00:00 Starten 0:02:26 Approximation mit relativer Gütegarantie 0:03:38 Beispiel: Greedy-Algorithmus für KNAPSACK 0:04:51 Definition 0:06:07 Approximierbarkeit von COLOR 0:20:05 Approximierb...
Listen13: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 19.12.2017 from 2021-01-31T22:10:42.023393
13 | 0:00:00 Starten 0:01:15 Grammatiken 0:06:22 Bemerkungen 0:09:12 Die Chomsky Hierarchie 0:19:54 Chomsky-0 Grammatiken und Semientscheidbarkeit 0:22:25 Beweis- Beschreibung der Grammatik G 0:28...
Listen14: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 09.01.2018 from 2021-01-31T22:10:42.023393
14 | 0:00:00 Starten 0:00:22 Die Chomsky Hierarchie 0:08:09 Typ-2/Kontextfrwiw Grammatiken 0:08:51 Typ-2/ Grammatiken: Beispiel 1 0:09:25 Typ-2/ Grammatiken: Beispiel 2 0:11:56 Syntacbäume 0:13:34 ...
Listen15: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 11.01.2018 from 2021-01-31T22:10:42.023393
15 | 0:00:00 Starten 0:00:19 Kontextfreie Sprachen, Kontextfreie Grammatiken 0:06:01 Pumping-Lemma für kontextfreie Sprachen 0:08:05 Ogden's Lemma für kontextfreie Sprachen 0:23:12 Satz 0:37:41 Nut...
Listen16: Theoretische Grundlagen der Informatik, Übung, WS 2017/18, 16.01.2018 from 2021-01-31T22:10:42.023393
16 | 0:00:00 Starten 0:01:12 Chomsky Hierarchie 0:15:28 Chomsky-0-Grammatiken und DTM's 0:28:42 Konstruktion von Grammatiken 0:46:58 Sprache der korrekten Klammerausdrücke 0:57:09 Chomsky-Normalfor...
Listen17: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 23.01.2018 from 2021-01-31T22:10:42.023393
17 | 0:00:00 Starten 0:00:24 Übersicht Chomsky-2 0:03:13 WDh.: Greibach-Normalform, Kellerautomat 0:09:07 Beweis 0:47:57 Korollar 0:48:46 Exkurs 0:50:37 Zwischenfazit zu kontextfreien Grammatiken 0...
Listen18: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 30.01.2018 from 2021-01-31T22:10:42.023393
18 | 0:00:00 Starten 0:03:53 Information 0:12:40 Entropie 0:18:49 (Platzsparende) Codierung 0:20:33 Codierungsbäume 0:25:54 Präfix-Codes 0:28:27 Quellencodierungstheorem 0:29:58 Beispiel: Shannon-F...
Listen19: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 08.02.2018 from 2021-01-31T22:10:42.023393
19 | 0:00:00 Starten 0:01:39 Rückblick: Chomsky Typ 3 0:04:53 Rückblick: Chomsky-3 Verfahren 0:22:29 Rückblick: Chomsky-2 0:35:13 Rückblick: Chomsky-0/1 0:40:32 Entscheidbarkeit 0:47:05 Domino 0:53...
Listen