09: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20,

Theoretische Grundlagen der Informatik,...

09: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 26.11.2019

Listen now

Description

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 Problem EXACT COVER 1:12:53 Beweis: NP-Vollständigkeit von EXACT COVER 1:14:34 Konstruktion von (X, S) 1:22:00 G 3-färbbar -> exakte Überdeckung

More Episodes

See all »

18: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 04.02.2020

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

Published 02/06/20

Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

Published 02/06/20

17: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 28.01.2020

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...

Published 01/30/20