PODCAST

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

Karlsruher Institut für Technologie (KIT)

education higher education

All Episodes

00:47:15

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2017/02/16

18 | 0:00:00 Starten 0:00:07 Fortsetzung Informationstheorie 0:01:06 Wiederholung Quellkodierung 0:01:46 Kanalkodierung 0:02:24 Codierung zum Schutz gegen Übertragungsfehler 0:04:17 Paritätscodes - Einfach Binär 0:07:27 Kreuzsicherung 0:12:20 Paritätscodes 0:13:33 Beweis 0:15:09 Paritätscodes gegen Vertauschungsfehler 0:18:42 Bsp: ISBN-10 0:18:56 ISBN 0:19:59 Block-Codes 0:20:31 Hamming-Distanz und Fehlerkorrektur 0:21:58 Maximum-Likelihood-Decoding 0:23:08 Shannon's Theorem 0:23:52

01:07:17

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2017/02/09

17 | 0:00:00 Starten 0:01:45 Thema dieses Kapitels 0:04:52 Material für Informationstheorie 0:05:32 Information 0:12:45 Wiederholung: Rechenregeln Logarithmus 0:13:53 Definition Information 0:14:52 Entropie 0:19:16 Bemerkung zur Entropie 0:19:31 Entropie einer Münze mit Wkt p für Zahl 0:20:44 (Platzsparende) Codierungen 0:22:12 Codierungsbäume 0:26:49 Präfix-Codes 0:29:08 Beispiel: Morse-Alphabet 0:30:15 Quellencodierungstheorem 0:31:47 Beispiel: Shannon-Fano Codierung 0:38:01 Codierungsbaum

01:11:18

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2017/02/03

16 | 0:00:00 Starten 0:00:37 Kellerautomaten 0:03:49 Satz 0:05:15 Satz (2) 0:06:09 Beweis 0:30:19 Korollar 0:30:41 Übersicht Chomsky-2 0:32:46 Exkurs 0:34:16 Zwischenfazit zu kontextfreien Grammatiken 0:36:10 Satz (3) 0:38:18 Das Post'sche Korrespondenzproblem 0:39:47 Beweis (2) 0:43:33 Beweisskizze 0:44:07 Beweis (3) 0:45:50 Sprache der korrekten Rechenwege 0:51:59 Lemma 0:52:28 Beweis (4) 1:01:26 Bemerkung 1:02:03 Lemma (2) 1:02:27 Beweis (5)

00:47:17

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2017/01/30

15 | 0:00:00 Starten 0:00:07 Beweis 0:03:26 Kellerautomaten 0:09:17 Kellerautomaten - Visualisierung 0:10:09 Kellerautomaten - Arbeitsweise 0:18:33 Kellerautomaten - Beispiel 0:27:20 Kellerautomaten - Beispiel 2 0:31:02 Satz (1) 0:35:44 Satz (2) 0:39:19 Satz (3)

01:06:23

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2017/01/20

14 | 0:00:00 Starten 0:00:07 Wiederholung 0:12:03 Ogden´s Lemma für kontextfreie Sprachen 0:14:31 Beweis 0:29:20 Beweis - Teil 1 0:30:23 Beweis - Teil 2 0:39:23 Beweis - Teil 3 0:41:58 Nutzlose Variablen 0:43:38 Schritt 1 0:47:24 Beispiel: Schritt 1 0:51:28 Schritt 2 0:53:16 Beispiel: Schritt 2 0:56:45 Korollar 0:59:27 Beispielgraph

01:23:54

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2017/01/20

13 | 0:00:00 Starten 0:00:31 Wiederholung 0:02:13 Die Chmosky Hierarchie 0:08:16 Syntaxbäume 0:10:28 Syntaxbäume - Beispiel 0:15:54 Links/Rechtsabteilung, Eindeutigkeit 0:17:31 Beispiel 0:19:37 Chomsky-Normalform 0:20:56 Die Chomsky Hierarchie 0:21:21 Chomsky-Normalform 0:31:01 Schritt 1 0:34:21 Schritt 2 0:38:20 Schritt 3 0:49:34 Schritt 4 0:53:36 Abhängigkeitsgraph 0:54:42 Schritt 4 – Phase 1 0:56:47 Schritt 4 – Phase 2 1:02:02 Der CYK-Algorithmus 1:05:15 Beweis - Beschreibung des

01:03:41

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2017/01/12

12 | 0:00:00 Starten 0:00:28 Grammatiken 0:01:26 Beispiele 0:05:33 Grammatiken 0:07:12 Bemerkungen 0:08:32 Beispiel 0:09:22 Die Chomsky Hierarchie 0:20:09 Chomsky-0 Grammatiken und Semientscheidbarkeit 0:24:58 Beweis - Beschreibung der Grammatik G 0:28:28 Beweis - Zusammenfassung 0:29:42 Chomsky-0 Grammatiken und Semientscheidbarkeit 0:32:04 Zwischenfazit 0:34:01 Chomsky-3-Grammatiken und reguläre Sprachen 0:35:27 Beweis 0:42:00 Bemerkung 0:43:05 Chomsky-1-Grammatiken bzw. kontextsensitive

01:00:16

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/12/23

11 | 0:00:00 Starten 0:02:50 Approximation mit relativer Gütegarantie 0:03:31 Definition 0:04:49 Approximierbarkeit von COLOR 0:18:45 Approximierbarkeit von TSP 0:28:12 Approximationsschemata 0:38:45 Ein FPAS für KNAPSACK (1) 0:40:02 Ein pseudopolynomialer, optimaler Algorithmus für KNAPSACK 0:43:49 Ein FPAS für KNAPSACK (2) 0:58:51 Ein allgemeineres Resultat

01:11:07

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/12/23

10 | 0:00:00 Starten 0:03:37 VerallgemeinerteNP-Schwere 0:07:17 Das Problem INTEGER PROGRAMMING 0:26:15 Pseudopolynomiale Algorithmen 0:29:56 Beispiel: Problem KNAPSACK 0:40:20 Starke NP-Vollständigkeit 0:44:14 Absolute Approximationsalgorithmen 0:46:31 Das allgemeine KNAPSACK-Suchproblem 0:57:09 Approximation mit relativer Gütegarantie 0:59:53 Beispiel: Greedy-Algorithmus für KNAPSACK

01:23:35

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/12/13

09 | 0:00:00 Starten 0:06:41 Das Problem SUBSET SUM 0:07:46 NP-Vollständigkeit von SUBSET SUM 0:24:03 Das Problem PARTITION 0:31:06 Das Problem KNAPSACK 0:37:32 Auswirkungen auf die Frage P=NP 0:45:42 Zusammenfassung 0:47:57 Die Klassen NPI, co-P und co-NP 0:54:22 Das TSP-Komplement-Problem 0:57:40 Lemma 1:00:00 Bemerkung 1:01:25 Das Problem Subgraphisomorphie 1:03:14 Das Problem Graphismorphie 1:09:06 Suchprobleme 1:10:21 Beispiel: TSP-Suchproblem 1:11:03 Beispiel: Hamilton–Kreis

01:27:34

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/12/08

08 | 0:00:00 Starten 0:00:37 Wiederholung: NP-Vollständigkeit 0:06:10 Wiederholung: Transitivität der poly. Transformation 0:06:40 Wiederholung: Korollar 0:07:37 Wiederholung: Das Problem SAT (satisfiability) 0:12:17 Das Problem 3-SAT 0:13:13 Beweis: NP-Vollständigkeit von 3-SAT 0:30:07 Das Problem 2SAT 0:34:40 Das Problem MAX2SAT 0:38:02 Das Problem CLIQUE 0:39:32 Beweis: NP-Vollständigkeit von CLIQUE 0:51:19 Das Problem COLOR 0:54:56 Beweis: NP-Vollständigkeit von 3COLOR 0:57:29 Konstruktion von

01:25:14

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/12/01

07 | 0:00:00 Starten 0:01:06 Die Klasse P 0:03:19 Die Klasse NP 0:04:47 Die Nichtdeterministische Turingmaschine 0:05:17 Zeitkomplexität für NTM 0:08:55 Große Frage der Theoretischen Informatik 0:11:38 NP-Vollständigkeit 0:24:35 Transitivität der poly. Transformation 0:25:46 Korollar 0:28:28 Das Problem SAT (satisfiability) 0:31:05 Weitere Beispiele für SAT-Instanzen 0:33:44 Der Satz von Cook (Steven Cook, 1971) 0:36:00 Beweis 0:42:53 Beweis: Konstruktion der Variablen 0:49:48 Beweis 0:53:35

01:31:49

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/12/01

06 | 0:00:00 Starten 0:00:54 Definitionen zur TM 0:05:21 Notation: Konfiguration 0:07:49 Beispiel: Konfiguration 0:20:00 Definition: berechenbar / totalrekursiv 0:22:30 Beispiel 0:26:57 Entscheidbarkeit und Berechenbarkeit 0:30:18 Korollar 0:33:13 Die Church´sche These 0:36:20 Erweiterungen der Turing-Maschine 0:39:17 Die universelle Turing-Maschine 0:45:24 Die Gödelnummer 0:50:45 Die Gödelnummer - Bemerkungen 0:54:43 Die Gödelnummer - Beispiel 0:58:54 Definition 1:00:08 Die Diagonalsprache 1:05:42

01:25:26

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/11/22

05 | 0:00:00 Starten 0:00:54 Definitionen zur TM 0:05:56 Notation: Konfiguration 0:07:50 Beispiel: Konfiguration 0:20:37 Definition: berechenbar / totalrekursiv 0:23:01 Beispiel 0:27:27 Entscheidbarkeit und Berechenbarkeit 0:30:19 Korollar 0:33:21 Die Church´sche These 0:36:38 Ertweiterungen der Turing-Maschine 0:39:39 Die universelle Turing-Maschine 0:44:35 Die Gödelnummer 0:50:58 Die Gödelnummer - Bemerkungen 0:53:35 Die Gödelnummer - Beispiel 0:59:14 Definition 1:01:05 Die

01:21:16

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/11/21

04 | 0:00:00 Starten 0:00:12 Endliche Automaten, reguläre Sprachen 0:00:57 Frage 0:01:40 Äquivalenz 0:04:24 Der Äquivalenzklassenautomat 0:06:29 Vorgehensweise 0:08:44 Frage 0:10:29 Antwort 0:13:49 Definitionen: Rechtsinvarianz und Index 0:17:08 Nerode-Relation 0:20:55 Satz von Nerode 0:24:06 Beweis zu Satz von Nerode: (1) – (2) 0:28:54 Beweis zu Satz von Nerode: (2) – (3) 0:31:43 Beweis zu Satz von Nerode: (3) – (1) 0:37:00 Satz von Nerode 0:37:38 Korollar 0:40:52 Minimalität des

01:23:01

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/11/10

02 | 0:00:00 Starten 0:00:24 Letzte Vorlesung 0:09:53 Entfernen von e-Übergängen 0:20:42 EA – Regulärität 0:22:44 Beweis: EA – Regulärität 0:44:02 Beispiel 0:54:15 Satz von Kleene 0:55:54 Frage: Was können endliche Automaten nicht? 0:59:14 Pumping-Lemma für reguläre Sprachen 1:10:10 Bemerkung 1:11:49 Beispiel (1) zum PL 1:14:18 Beispiel (2) zum PL 1:18:31 Beispiel (3) zum PL

01:08:20

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/11/08

03 | 0:00:00 Starten 0:00:25 Verallgemeinertes PL für reguläre Sprachen 0:17:18 Kapitel Minimierung von Automaten und Äquivalenzklassenautomat 0:20:14 Frage: Kann man konstruktiv die Anzahl der Zustände eines deterministischen endlichen Automatens erheblich verringern? 0:22:04 Beispiel 0:34:34 Äquivalenz 0:37:22 Der Äquivalenzklassenautomat 0:48:03 Frage: Wie berechnet man alle Äquivalenzklassen zu den Zuständen von A? 0:53:43 Frage: Wann kann dieses Verfahren abgebrochen werden? 0:57:26

01:03:21

Theoretische Grundlagen der Informatik, Vorlesung, WS...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/10/27

01 |0:00:00 Starten 0:00:30 Ziele der Vorlesung TGI 0:13:46 Wiederholung aus Grundbegriffe der Informatik 0:17:17 Wörter 0:21:24 Formale Sprachen 0:31:12 Reguläre Sprachen 0:36:04 Reguläre Ausdrücke 0:39:46 Reguläre Ausdrücke – Beispiele 0:43:48 Endliche Automaten 0:53:24 Kontextfreie Grammatiken 0:58:07 Beispiel Kontextfreie Grammatiken

18 results

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

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