))
Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 12.01.2016, Vorlesung - 17
Archivierte Serien ("Inaktiver Feed" status)
When?
This feed was archived on March 08, 2022 09:49 (
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 188073169 series 1569371
Inhalt bereitgestellt von Karlsruher Institut für Technologie (KIT). Alle Podcast-Inhalte, einschließlich Episoden, Grafiken und Podcast-Beschreibungen, werden direkt von Karlsruher Institut für Technologie (KIT) oder seinem Podcast-Plattformpartner hochgeladen und bereitgestellt. Wenn Sie glauben, dass jemand Ihr urheberrechtlich geschütztes Werk ohne Ihre Erlaubnis nutzt, können Sie dem hier beschriebenen Verfahren folgen https://de.player.fm/legal.
17: Vorlesung| 0:00:00 Starten 0:00:53 Wiederholung Komplexitätstheorie 0:08:54 Polynominale Reduzierbarkeit 0:09:55 Beispiel 0:10:57 NP-harte und Np-Vollständige Probleme 0:13:22 Ein einfacher Weg zu Ruhm und Reichtum ? 0:13:50 SAT: Das Erfüllbarkeitsproblem 0:17:03 Beweis von SAT 0:17:31 Beweis das SAT-NP-hart ist. 0:19:45 Variablen für F 0:24:53 Die Architektir von F= 0:27:08 Beweis w gehört zu der Sprache L, was daraus folgt das F erfüllbar ist 0:31:44 Es kann nur einen geben 0:33:05 Randbedingung 0:37:00 Anfangsbedingung 0:38:46 Übergangsbedingung Ü1, t->t+1 0:42:01 Übergangsbedingung Ü2, t->t+1 0:42:42 Endebedingung E 0:43:56 Gesamtgröße von F 0:48:06 Weitere NP-vollständige Probleme 0:55:04 3SAT (KNF) 0:56:56 Satz: 3SAT ist NP-vollständig 0:58:29 Beweis ""3SAT ist NP-hart"" 1:00:12 Negation in die Blätter drücken 1:01:23 Beispiel 1:03:04 Nichtblattknoten -> Neue Variablen 1:05:52 Beispiel 1:06:34 Erfüllbarkeitsäquivalenz von F1 1:07:57 Beispiel 1:10:15 F1 -> 3KNF
…
continue reading
27 Episoden
Teilen
