05: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 06.11.2017

Algorithmen 2, Vorlesung, WS17/18

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.

6+ y ago 1:21:00

MP4•Episode-Home

Archivierte Serien ("Inaktiver Feed" status)

When? This feed was archived on November 30, 2021 06:09 (2+ y ago). Last successful fetch was on March 31, 2021 07:26 (3y 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.

05 | 0:00:00 Starten 0:00:34 Turing-Reduzierbarkeit 0:02:47 Pseudopolynomielle Laufzeit 0:05:58 Zwei kleine Warnungen 0:07:55 KNAPSACK Suchproblem 0:10:22 KNAPSACK: Codierungen der Eingabe 0:11:47 Schwere des KNAPSACK Suchproblems 0:12:41 KNAPSACK: pseudopolynomielle Laufzeit 0:22:08 Polynomielle Approximationsschema 0:25:56 PTAS versus FPTAS 0:26:34 Von pseudopolynomieller zu polynomieller Laufzeit 0:28:12 FPTAS für KNAPSACK 0:32:14 epsApproxKnapsack ist FPTAS 0:32:46 epsApproxKnapsack ist FPTAS: Approximation 0:36:12 epsApproxKnapsack ist FPTAS: Polynomialzeit 0:37:06 Varianten von Approximation: zwei Beispiele 0:37:56 Anfang der Übung 0:38:33 Approximationsalgorithmen: Grundlagen 0:40:40 Approximationsalgorithmen: Gütemaß 0:43:43 Approximationsalgorithmen: Klassen 0:47:55 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen 0:49:52 2-Approximation für Jobs Scheduling 0:51:27 4/3- Approximation für Jobs Scheduling 0:52:00 Fall 1: kleiner Job 0:56:49 Nur große Jobs 1:03:52 Minimum Metric TSP 1:13:46 Kleine Änderung in der Definition 1:14:21 Perfekt balancierte Graphpartitionierung 1:15:58 3-Partion 1:17:08 Reduktion

26 Episoden

#Hochschulbildung #Bildung #Vorlesung #Informatik #Strukturen #Daten #Toolbox #Korrektheitsargumente #Effizienzanalyse #Algorithmen #Mathematik #Karlsruher Instituts Für Technologie KIT #Video #KIT