Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 24.11.2016, 07

1:25:14
 
Teilen
 

Fetch error

Hmmm there seems to be a problem fetching this series right now. Last successful fetch was on February 01, 2019 07:08 (1+ y ago)

What now? This series will be checked again in the next day. If you believe it should be working, please verify the publisher's feed link below is valid and includes actual episode links. You can contact support to request the feed be immediately fetched.

Manage episode 188073600 series 1569372
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.
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 Beweis: Konstruktion der Klauseln - Übersicht 0:56:09 Klauselgruppe 1: 0:59:10 Klauselgruppe 2: 1:00:15 Klauselgruppe 3: 1:01:50 Klauselgruppe 4: 1:03:23 Klauselgruppe 5: 1:04:36 Klauselgruppe 6: 1:06:51 Klauselgruppe 6, 1: 1:09:51 Klauselgruppe 6,2: 1:13:35 Konstruktion der Klauseln - Zwischenergebnis 1:15:11 Polynomialität der Transformation 1:15:45 Polynomialität - Klauselgruppe 1: 1:16:20 Polynomialität - Klauselgruppe 2: 1:17:25 Polynomialität - Klauselgruppe 3: 1:17:56 Polynomialität - Klauselgruppe 4: 1:18:38 Polynomialität - Klauselgruppe 5:

18 Episoden