09: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 28.11.2017

1:09:58
 
Teilen
 

Archivierte Serien ("Inaktiver Feed" status)

When? This feed was archived on April 24, 2022 14:32 (2M ago). Last successful fetch was on March 31, 2021 15:27 (1+ y ago)

Why? Inaktiver Feed status. Unsere Server waren nicht in der Lage einen gültigen Podcast-Feed für einen längeren Zeitraum zu erhalten.

What now? You might be able to find a more up-to-date version using the search function. This series will no longer be checked for updates. If you believe this to be in error, please check if the publisher's feed link below is valid and contact support to request the feed be restored or if you have any other concerns about this.

Manage episode 198837312 series 2078468
Von Karlsruher Institut für Technologie (KIT) entdeckt von Player FM und unserer Community - Das Urheberrecht hat der Herausgeber, nicht Player FM, und die Audiodaten werden direkt von ihren Servern gestreamt. Tippe auf Abonnieren um Updates in Player FM zu verfolgen oder füge die URL in andere Podcast Apps ein.
09 | 0:00:00 Starten 0:00:39 NP-Vollständigkeit 0:02:03 Transitivität der poly. Transformation 0:02:31 Korollar 0:03:49 Das Problem 3-SAT 0:05:37 Beweis: NP-Vollständigkeit von 3-SAT 0:20:16 Das Problem 2SAT 0:22:09 Das Problem MAX2SAT 0:24:18 Das Problem CLIQUE 0:27:48 Beweis: NP-Vollständigkeit von CLIQUE 0:36:44 Das Problem COLOR 0:37:57 Beweis: NP-Vollständigkeit von 3COLOR 0:39:06 Konstruktion von 3COLOR-Instanz G 0:43:16 Beispielgraph zur Reduktion 0:45:12 Polynomialität der Reduktion 0:45:35 Instantz I erfüllbar auch Instanz G erfüllbar 0:45:57 Instanz G ist 3-färbbar 0:50:30 Das Problem EXACT COVER 0:53:51 Beweis: NP-Vollständigkeit von EXACT COVER 0:55:30 Konstruktion von (X,S) 1:04:50 G dreifärbbar (X,S) hat exakte Überdeckung

19 Episoden