PODCAST

Theoretische Grundlagen der Informatik, Vorlesung, WS18/19

Karlsruher Institut für Technologie (KIT)

education higher education

All Episodes

00:59:02

18: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/02/12

18 | 0:00:00 Start 0:00:26 Werbung 0:01:14 Vorlesung ,,Algorithmen für planare Graphen"" 0:02:53 Proseminar ,,Algorithmen für NP-schwere Probleme"" 0:05:28 ICPC Praktikum 0:07:38 Kodierung zum Schutz gegen Übertragungsfehler 0:12:34 Paritätscodes - Einfach binär 0:18:38 Kreuzsicherung 0:25:26 Paritätscodes 0:28:05 Beweis 0:30:29 Paritätscodes gegen Vertauschungsfehler 0:36:17 Bsp:ISBN-10 0:40:51 Block-Codes 0:41:50 Hamming-Distanz und Fehlerkorrektur 0:46:58

01:25:03

17: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/01/31

17 | 0:00:00 Start 0:00:05 Thema dieses Kapitels 0:05:25 Material für Informationstheorie 0:06:28 Information 0:08:45 Beispiel 0:16:13 Wiederholung: Rechenregeln Logarithmus 0:17:53 Beispiel 2 0:20:11 Entropie 0:25:08 Bemerkung zur Entropie 0:29:31 (Platzsparende) kodierungen 0:33:25 Präfix-Codes 0:35:00 Codierungsbäume 0:41:32 Quellenkodierungstheorem 0:43:27 Beispiel: Schanon-Fano Kodierung 0:51:21 Beispiel: Huffman-Kodierung 0:56:30 Vorbereitendes Lemma 1:05:38 Beweis

01:28:41

16: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/01/29

16 | 0:00:00 Start 0:00:32 Letzte Vorlesung 0:02:51 Wdh.: Greibach-Normalform, Kellerautomat 0:06:32 Beispiel - Greibach-Normalform 0:12:41 Beispiel - Kellerautomat 0:17:47 Beweis: Greibach-Normalform -NPDA 0:26:14 Übersicht 0:27:41 Beweis:NPDA - kontextfreie Grammatik 0:51:16 Exkurs 0:55:11 Zwischenfazit zu kontextfreien Grammatiken 0:57:12 Unentschedbare Probleme für kontextfreie Grammatiken 1:00:05 Das Post'sche Korrespondenzproblem 1:01:10 Beweis 1:06:43 Eindeutigkeit von kontextfreien

01:26:59

15: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/01/24

15 | 0:00:00 Start 0:02:19 weitere Eigenschaften kontextfreier Sprachen 0:12:03 Ein maschinellmodell für Chomsky-2 0:18:04 Greibach-Normalform 0:21:01 Beweis - Ersetzung 0:29:08 Beweis - Definitionen 0:30:57 Beweis - Invarianten 0:36:26 Beweis - Verfahren Schritt 1 0:45:30 Beweis - Verfahren Schritt 2 0:50:05 Beweis - Verfahren Schritt 3 0:53:21 Kellerautomaten 0:59:08 Kellerautomaten - Arbeitsweise 1:15:30 Ein Maschinenmodell für Chomsky-2

01:13:02

14: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/01/18

14 | 0:00:00 Start 0:06:36 Das Pumping-Lemma für kontextfreie Sprachen 0:10:42 Ogden´s Lemma für kontextfreie Sprachen 0:14:06 Beweis von Odgen´s Lemma 0:29:34 Bemerkung 0:30:52 Echtheit der Chomsky-Hierarchie 0:32:47 Beweis - Teil 1 0:33:46 Beweis - Teil 2 0:48:59 Beweis - Teil 3 0:55:39 Eigenschaften kontextfreier Sprachen 0:58:31 Nutzlose Variablen 1:00:00 Schritt 1 1:07:39 Schritt 2

01:12:48

13: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/01/10

13 | 0:00:00 Start 0:00:09 Letzte Vorlesung 0:08:30 heutige Themen 0:09:05 Syntaxbäume 0:13:44 Eindeutigkeit 0:19:08 Chomsky-Normalform 0:52:24 CYK-Algorithmus

01:28:59

12: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2018/12/21

12 | 0:00:00 Start 0:00:31 Grammatiken, Beispiele 0:09:52 Grammatiken, Bemerkungen 0:16:13 Die Chomsky Hierarchie 0:29:17 Chomsky-0 Grammatiken und Semientscheidbarkeit 0:36:03 Beweis - Beschreibung der Grammatik G 0:42:30 Beweis - Zusammenfassung 0:49:13 Chromsky-3 Grammatiken und reguläre Sprachen 1:02:28 Chromsky-1 Grammatiken bzw. kontextsensitive Sprachen 1:09:49 Wiederholung: Das Problem CLIQUE 1:20:25 Typ-2 / Kontextfreie Grammatiken

01:17:57

11: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2018/12/14

11 | 0:00:00 Start 0:00:15 Letzte Vorlesung 0:03:09 Definition 0:09:54 Metrisches TSP 0:20:53 Bemerkungen zur Approximierbarkeit 0:23:46 Approximationsschemata 0:29:50 Ein FPTAS für max-KNAPSACK 0:53:01 min-VERTEX-COLOR und min-EDGE-COLOR 0:54:39 Nicht-Existenz eines FPTAS 1:04:07 Approximierbarkeit von COLOR 1:14:46 Ein allgemeines Resutat

01:12:26

10: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2018/12/13

10 | 0:00:00 Start 0:01:01 Verallgemeinerte NP-Schwere 0:03:38 Das Problem INTEGER PROGRAMMING 0:07:18 INTEGER PROGRAMMING ist NP-schwer 0:15:12 Bemerkungen 0:23:00 Pseudopolynomiale Algorithmen 0:33:54 Starke NP-Vollständigkeit 0:40:34 Absolute Approximationsalgorithmen 0:44:01 Das allgemeine KNAPSACK-Suchproblem 0:47:08 Negativ-Resultat 0:50:24 (Kontrapositions-)Beweis 0:55:47 Approximation mit relativer Gütegarantie 0:57:13 Genereller Ansatz 1:06:09 Grenzen für den Greedy-Algorithmus

01:22:07

09: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2018/12/06

09 | 0:00:00 Start 0:00:57 Letzte Vorlesung 0:20:50 Diese Vorlesung 0:20:57 Das Problem PARTITION 0:28:58 Das Problem KNAPSACK 0:40:03 Zusammenfasung 0:59:24 Das Problem Subgraphisomorphie 1:00:45 Das Problem Graphisomorphie 1:02:28 Die Polynomielle Hierarchie 1:11:31 Suchprobleme 1:17:35 Aufzählungsprobleme

01:28:26

08: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2018/11/29

08 | 0:00:00 Start 0:00:22 Letzte Vorlesung 0:06:59 Plan für heute 0:09:46 Pas Problem 3SAT 0:11:29 Beweis: NP-Vollständigkeit von 3SAT 0:30:58 Das Problem 2SAT 0:31:54 Das Problem MAX2SAT 0:33:51 Das Problem CLIQUE 0:35:32 Beweis: NP - Vollständigkeit von CLIQUE 0:48:25 Das Problem COLOR 0:50:25 NP-Vollständigkeit von 3COLOR 0:52:26 Konstruktion von 3COLOR-Instanz G 0:55:48 Polynomialität der Reduktion 0:56:35 Instanz/ erfüllbar 1:03:01 Zwischenstand Polynomiale Reduktion 1:13:41 Das

01:08:33

07: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2018/11/23

07 | 0:00:00 Start 0:00:03 NP-Vollständigkeit für Sprachen 0:03:38 NP-Vollständigkeit für Entscheidungsprobleme 0:05:28 Transitivität der poly. Transformation 0:06:59 Beobachtung 0:10:58 Das Problem SAT (satisfiability) 0:16:04 Weitere Beispiele für SAT-Instanzen 0:17:42 Der Satz von Cook (Steven Cook, 1971) 0:22:03 Beweis: das Setup 0:28:37 Beweis: Konstruktion der Variablen 0:32:52 Beweis: Zielsetzung 0:37:44 Beweis: Konstruktion der Klauseln 0:38:03 Klauselgruppe 1: 0:39:46 Klauselgruppe

01:25:32

06: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2018/11/19

06 | 0:00:00 Start 0:00:09 Letzte Vorlesung 0:03:24 Die Universelle Sprache 0:14:02 Satz von Rice – Motivation 0:17:55 Bemerkungen zum Satz von Rice 0:22:13 Das Post'sche Korrespondenzproblem 0:31:13 Eigenschaften von (semi-)entscheidbaren Sprachen 0:32:25 Komplexitätstheorie 0:34:36 Wie sieht ein Problem aus? 0:37:46 Definition: Problem 0:40:37 Definition:Kodierungsschema 0:46:51 Äquivalenz von Kodierungsschemata 0:48:35 Entscheidungsprobleme 0:50:57 Korrespondenz von Entscheidungsproblemen und

01:25:34

05: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2018/11/15

05 | 0:00:00 Start 0:00:10 Letzte Vorlesung 0:09:00 Beispiel - Turing Maschine 0:13:57 Bemerkungen zur TM 0:15:23 Definition zur TM 0:18:43 Notation: Konfiguration 0:19:54 Beispiel: Konfiguration 0:26:21 Definition: berechenbar / totalrekursiv 0:28:10 Beispiel 0:34:10 Entscheidbarkeit und Berechenbarkeit 0:39:01 Korollar 0:40:51 Die Church'sche These 0:44:25 Erweiterung der Turing-Maschine 0:51:23 Die Universelle Turing-Maschine 0:54:51 Die Gödelnummer 0:57:52 Die Gödelnummer - Bemerkungen 1:00:43

01:29:55

04: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2018/11/09

04 | 0:00:00 Start 0:00:03 letzte Vorlesung - alternative Sicht 0:04:48 Alternative Sicht - Beispiel 0:13:20 Heutiges Thema (Frage, Antwort) 0:20:21 Definitionen: Rechtsinvarianz und Index 0:27:56 Nerode-Relation 0:31:10 Satz von Nerode 0:50:10 Korollar 0:52:20 Minimalität des Äquivalenzklassenautomats 0:59:19 Zusammenfassung 1:07:12 Turing-Maschinen und Berechenbarkeit 1:08:42 Die Registermaschine (RAM) 1:14:26 Die Turing-Maschine (TM)

01:23:28

03: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2018/11/02

03 | 0:00:00 Start 0:00:03 Rückblick 0:04:19 Verallgemeinertes PL für reguläre Sprachen 0:16:10 Beispiel (3) - Anwendung Verallgemeinertes PL 0:24:06 Minimierung von Automaten - Äquivalenzklassenautomat 0:27:47 Finden nicht überflüssiger Zustände 0:31:00 Beispiel 0:37:13 Äquivalenz 0:46:38 Der Äquivalenzklassenautomat 1:04:07 Zeugen für Nichtäquivalenz 1:09:26 Vorgehensweise 1:15:59 Zusammenfassung

01:16:52

01: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2018/10/30

01 |0:00:00 Start 0:00:11 Endliche Automaten und Reguläre Sprachen 0:14:38 Nichtdeterministische endliche Automaten 0:21:06 Beispiel für NEA's 0:27:09 Äquivalenz von NEA's und DEA's 0:28:57 Beispiel Potenzmengenkonstruktion 1:11:43 Zusammenfassung

01:22:07

02: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2018/10/26

02 | 0:00:00 Start 0:00:07 Letzte Vorlesung 0:04:01 Entfernen von e-Übergängen 0:15:37 EA - Regularität 0:15:51 Beweis 0:33:04 Beispiel 0:39:16 Satz von Kleene 0:40:27 Frage: Was können endliche Automaten nicht? 0:45:19 Pumping-Lemma für reguläre Sprachen 0:58:23 Verwendung des Pumping-Lemmas 1:05:20 Beispiel zum PL 1:18:10 Zusammenfassung

18 results

Theoretische Grundlagen der Informatik, Vorlesung, WS18/19

All Episodes

Similar Podcasts

Science Talk

Albert Einstein College of Medicine

五分钟心理学

柠檬心理

Daily Facts

Amalia Dupray and Montgomery Jones.

Les dents et dodo

BFMTV

Veterinary Clinical Podcasts

The Royal Veterinary College