PODCAST

Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

Karlsruher Institut für Technologie (KIT)

education higher education

All Episodes

00:27:38

18: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2020/02/06

18 | 0:00:00 Start 0:00:11 Kodierung zum Schutz gegen Übertragungsfehler 0:01:42 Paritätscodes - Einfach binär 0:04:45 Kreuzsicherung 0:10:05 Paritätscodes 0:16:27 Block-Codes 0:17:03 Hamming-Distanz und Fehlerkorrektur 0:21:23 Beispiel

01:13:08

17: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2020/01/30

17 | 0:00:00 Start 0:03:24 Material für Informationstheorie 0:03:57 Information 0:12:08 Wiederholung: Rechenregeln Logarithmus 0:17:45 Entropie 0:24:46 Entropie zu einer Münze 0:26:09 (Platzsparende) Kodierungen 0:28:48 Präfix-Codes 0:31:13 Kodierungsbäume 0:36:18 Beispiel: Morse-Alphabet 0:37:38 Quellenkodierungstheorem 0:39:41 Beispiel: Shannon-Fano-Kodierung 0:44:44 Kodierungsbaum Shannon-Fano 0:45:44 Beispiel: Huffman-Kodierung 0:49:25 Vorbereitendes Lemma 0:55:09 Beweis -

01:30:51

16: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2020/01/24

16 | 0:00:00 Start 0:00:21 Letzte Vorlesung 0:07:22 Wdh.: Greibach-Normalform, Kellerautomat 0:11:54 Kellerautomaten 0:15:10 Beispiel - Greibach-Normalform 0:18:13 Beipiel - Kellerautomat 0:21:23 Beweis: Greibach-Normalform -> NPDA 0:27:20 Beweis: NPDA -> Kontextfreie Grammatik 0:52:53 Zwischenfazit zu kontextfreien Grammatiken 0:59:24 Das Post´sche Korrespondenzproblem 1:06:53 Eindeutigkeit von kontextfreien Grammatiken 1:10:13 Sprache der Korrekten Rechenwege

01:27:06

15: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2020/01/14

15 | 0:00:00 Start 0:00:19 Letzte Vorlesung 0:01:21 Heutige Vorlesung 0:03:24 Weiere Eigenschaften kontextfreier Sprachen 0:17:59 Ein Maschinenmodell für Chomsky-2 0:23:18 Greibach-Normalform 0:26:01 Beweis 0:53:04 Kellerautomaten

01:11:19

14: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2020/01/10

14 | 0:00:00 Start 0:00:31 Übersicht 0:04:47 Das Pumping-Lemma für kontextfreie Sprachen 0:13:52 Ogden´s Lemma für kontextfreie Sprachen 0:15:48 Beweis von Ogden´s Lemma 0:28:07 Echtheit der Chomsky-Hierarchie 0:30:18 Beweis 0:44:49 Eigenschaften kontextfreier Sprachen 0:48:12 Nutzlose Variablen 0:51:27 Schritt 1 1:01:10 Schritt 2 1:05:22 Endliche kontextfreie Sprachen 1:08:51 Beispielgraph

01:14:31

13: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/12/17

13 | 0:00:00 Start 0:01:20 Beispiele 0:04:40 Grammatiken 0:06:42 Bemerkungen 0:11:29 Die Chomsky-Hierarchie 0:24:56 Chomsky-0-Grammatiken und Semientscheidbarkeit 0:30:11 Beweis – Beschreibung der Grammatik G 0:40:28 Chomsky-3-Grammatiken und reguläre Sprachen 0:42:26 Beweis 0:53:06 Chomsky-1-Grammatiken bzw. kontextsensitive Sprachen 0:57:03 Satz

01:27:22

12: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/12/12

12 | 0:00:00 Start 0:00:42 Wiederholung letzte Vorlesung 0:08:12 Definition 0:14:31 Metrisches TSP 0:16:07 Approximation von min-METRIC-TSP 0:27:08 Bemerkungen zur Approximierbarkeit 0:31:25 Approximationsschemata 0:37:51 Ein FPTAS für max-KNAPSACK 0:42:18 Pseudopolynomialer. optimaler Algorithmus für max-KNAPSACK 0:52:46 Maximierungsprobleme 1:01:47 Optimierungsprobleme 1:10:58 Approximierbarkeit von min-Vertex-Color 1:23:39 Abschluss des Kapitels zur Komplexitätstheorie

01:18:51

11: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/12/06

11 | 0:00:00 Start 0:01:57 Verallgemeinerte NP-Schwere 0:04:05 Das Problem INTEGER PROGRAMMING 0:07:55 INTEGER PROGRAMMING ist NP-schwer 0:16:21 Bemerkungen 0:21:18 Kapitel 0:24:34 Pseudopolynomiale Algorithmen 0:28:14 Beispiel: Problem KNAPSACK 0:37:52 Starke NP-Vollständigkeit 0:44:41 Kapitel 0:47:54 Absolute Approximationsalgorithmen 0:49:27 Das allgemeine KNAPSACK-Suchproblem 0:51:56 Negativ-Resultat 0:53:52 (Kontrapositions-)Beweis 0:59:35 Approximation mit relativer Gütegarantie 1:01:11

01:22:02

10: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/11/28

10 | 0:00:00 Start 0:00:27 Letzte/Diese Vorlesung 0:04:04 Das Problem SUBSET SUM 0:05:37 NP-Vollständigkeit von SUBSET SUM 0:21:39 Das Problem PARTITION 0:22:29 Beweis: NP-Vollständigkeit von PARTITION 0:28:40 Das Problem KNAPSACK 0:31:18 Beweis: NP-Vollständigkeit von KNAPSACK 0:33:39 Auswirkung auf die Frage P= NP 0:40:15 Zusammenfassung 0:45:01 Die Klassen NPC und NPI 0:46:23 Die Klassen co-P und co-NP 0:51:28 Das TSP-Komplement-Problem 0:54:27 NP-vollständig vs. co-NP 0:58:19 Das Problem

01:26:46

09: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/11/26

09 | 0:00:00 Start 0:00:08 Letzte Vorlesung 0:08:16 Plan für heute 0:10:46 Das Problem 3SAT 0:12:53 Beweis: NP-Vollständigkeit von 3SAT 0:31:50 Das Problem 2SAT 0:34:00 Das Problem MAX2SAT 0:36:49 Das Problem CLIQUE 0:39:07 Beweis: NP-Voillständigkeit von CLIQUE 0:54:25 Das Problem COLOR 0:55:33 Beweis: NP-Vollständigkeit von 3COLOR 0:57:09 Konstruktion von 3COLOR-Instanz G 1:02:30 Polynomialität der Reduktion 1:03:12 Instanz G 3-färbbar 1:08:08 Zwischenstand Polynomiale Reduktion 1:10:27 Das

01:15:57

08: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/11/21

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

01:28:13

07: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/11/14

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

01:27:08

06: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/11/07

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

01:24:34

05: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/10/31

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

01:05:23

04: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/10/29

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

01:23:18

03: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/10/24

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

01:19:24

02: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/10/21

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

01:06:54

01: Theoretische Grundlagen der Informatik,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2019/10/17

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

18 results

Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

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