10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 05.12.2017

1:26:14
 
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 198837313 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.
10 | 0:00:00 Starten 0:03:27 Das Problem SUBSET SUM 0:04:50 NP-Vollständigkeit von SUBSET SUM 0:18:59 Das Problem Partition 0:25:38 Das Problem KNAPSACK 0:28:21 Beweis: NP-Vollständigkeit von KNAPSACK 0:32:43 Auswirkung auf die Frage P=NP 0:37:29 Zusammenfassung 0:41:47 Die Klassen NPI, co-P und co-NP 0:45:07 Vermutete Situation 0:50:03 Das TSP-Komplement-Problem 0:52:03 Lemma 1:02:23 Suchprobleme 1:05:08 Beispiel: TSP-Suchproblem 1:06:53 Beispiel: Hamilton-Kreis Suchproblem 1:08:09 Aufzählungsprobleme 1:09:11 Reduzierbarkeit für Suchprobleme 1:12:28 Orakel-Turing-Maschine 1:13:56 Orakel-TM: Verhalten im Fragezustand 1:16:35 Turing-Reduktion 1:19:07 NP-schwer 1:22:30 Beweisskizze

19 Episoden