Theoretische Grundlagen Der Informatik, Vorlesung, WS 2016/17, 06.12.2016, 09 Theoretische Grundlagen Der Informatik, Vorlesung, WS16/17 podcast

Artwork

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

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.

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17 « »
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 06.12.2016, 09

7+ y ago 1:23:35

Teilen

MP4•Episode-Home

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.

09 | 0:00:00 Starten 0:06:41 Das Problem SUBSET SUM 0:07:46 NP-Vollständigkeit von SUBSET SUM 0:24:03 Das Problem PARTITION 0:31:06 Das Problem KNAPSACK 0:37:32 Auswirkungen auf die Frage P=NP 0:45:42 Zusammenfassung 0:47:57 Die Klassen NPI, co-P und co-NP 0:54:22 Das TSP-Komplement-Problem 0:57:40 Lemma 1:00:00 Bemerkung 1:01:25 Das Problem Subgraphisomorphie 1:03:14 Das Problem Graphismorphie 1:09:06 Suchprobleme 1:10:21 Beispiel: TSP-Suchproblem 1:11:03 Beispiel: Hamilton–Kreis Suchproblem 1:12:04 Aufzählungsprobleme 1:12:44 Reduzierbarkeit für Suchprobleme 1:15:36 Orakel-Turing-Machine 1:19:40 NP-schwer 1:20:39 Beweisskizze

… continue reading

18 Episoden

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

Artwork

Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 06.12.2016, 09

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

published 7+ y ago

Teilen

MP4•Episode-Home

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.

09 | 0:00:00 Starten 0:06:41 Das Problem SUBSET SUM 0:07:46 NP-Vollständigkeit von SUBSET SUM 0:24:03 Das Problem PARTITION 0:31:06 Das Problem KNAPSACK 0:37:32 Auswirkungen auf die Frage P=NP 0:45:42 Zusammenfassung 0:47:57 Die Klassen NPI, co-P und co-NP 0:54:22 Das TSP-Komplement-Problem 0:57:40 Lemma 1:00:00 Bemerkung 1:01:25 Das Problem Subgraphisomorphie 1:03:14 Das Problem Graphismorphie 1:09:06 Suchprobleme 1:10:21 Beispiel: TSP-Suchproblem 1:11:03 Beispiel: Hamilton–Kreis Suchproblem 1:12:04 Aufzählungsprobleme 1:12:44 Reduzierbarkeit für Suchprobleme 1:15:36 Orakel-Turing-Machine 1:19:40 NP-schwer 1:20:39 Beweisskizze

… continue reading

18 Episoden

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

Alle Folgen

×

Willkommen auf Player FM!

Player FM scannt gerade das Web nach Podcasts mit hoher Qualität, die du genießen kannst. Es ist die beste Podcast-App und funktioniert auf Android, iPhone und im Web. Melde dich an, um Abos geräteübergreifend zu synchronisieren.

Höre 500+ Themen zu