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

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

İçerik Karlsruher Institut für Technologie (KIT) tarafından sağlanmıştır. Bölümler, grafikler ve podcast açıklamaları dahil tüm podcast içeriği doğrudan Karlsruher Institut für Technologie (KIT) veya podcast platform ortağı tarafından yüklenir ve sağlanır. Birinin telif hakkıyla korunan çalışmanızı izniniz olmadan kullandığını düşünüyorsanız burada https://tr.player.fm/legal özetlenen süreci takip edebilirsiniz.

7+ y ago 1:27:34

MP4•Bölüm sayfası

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 bölüm

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