Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 01.12.2016, 08

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

Контент предоставлен Karlsruher Institut für Technologie (KIT). Весь контент подкастов, включая эпизоды, графику и описания подкастов, загружается и предоставляется непосредственно компанией Karlsruher Institut für Technologie (KIT) или ее партнером по платформе подкастов. Если вы считаете, что кто-то использует вашу работу, защищенную авторским правом, без вашего разрешения, вы можете выполнить процедуру, описанную здесь https://ru.player.fm/legal.

7+ y ago 1:27:34

MP4•Главная эпизода

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 3COLOR-Instanz G 1:01:05 Beispielgraph zur Reduktion 1:04:20 Polynomialität der Reduktion 1:04:56 Instanz I erfüllbar => Instanz G erfüllbar 1:07:12 Instanz I erfüllbar <= Instanz G erfüllbar 1:08:02 Das Problem EXACT COVER 1:13:06 Beweis: NP-Vollständigkeit von EXACT COVER 1:14:28 Konstruktion von (X,S) 1:24:05 G dreifärbbar => (X,S) hat exakte Überdeckung 1:25:47 G dreifärbbar <= (X,S) hat exakte Überdeckung

18 эпизодов

#Hochschulbildung #Bildung #Vorlesung #Informatik #Berechnungsmodelle #Determinismus #Nichtdeterminismus #Berechenbarkeit #Komplexitätstheorie #Grammatiken #Karlsruher Instituts Für Technologie KIT #Video #KIT #Theorie