11: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 05.12.2019
Update: 2019-12-06
Description
11 |
0:00:00 Start
0:01:57 Verallgemeinerte NP-Schwere
0:04:05 Das Problem INTEGER PROGRAMMING
0:07:55 INTEGER PROGRAMMING ist NP-schwer
0:16:21 Bemerkungen
0:21:18 Kapitel
0:24:34 Pseudopolynomiale Algorithmen
0:28:14 Beispiel: Problem KNAPSACK
0:37:52 Starke NP-Vollständigkeit
0:44:41 Kapitel
0:47:54 Absolute Approximationsalgorithmen
0:49:27 Das allgemeine KNAPSACK-Suchproblem
0:51:56 Negativ-Resultat
0:53:52 (Kontrapositions-)Beweis
0:59:35 Approximation mit relativer Gütegarantie
1:01:11 Genereller Ansatz
1:03:54 Beispiel: Greedy-Algorithmus für KNAPSACK
1:12:18 Grenzen für den Greedy-Algorithmus
0:00:00 Start
0:01:57 Verallgemeinerte NP-Schwere
0:04:05 Das Problem INTEGER PROGRAMMING
0:07:55 INTEGER PROGRAMMING ist NP-schwer
0:16:21 Bemerkungen
0:21:18 Kapitel
0:24:34 Pseudopolynomiale Algorithmen
0:28:14 Beispiel: Problem KNAPSACK
0:37:52 Starke NP-Vollständigkeit
0:44:41 Kapitel
0:47:54 Absolute Approximationsalgorithmen
0:49:27 Das allgemeine KNAPSACK-Suchproblem
0:51:56 Negativ-Resultat
0:53:52 (Kontrapositions-)Beweis
0:59:35 Approximation mit relativer Gütegarantie
1:01:11 Genereller Ansatz
1:03:54 Beispiel: Greedy-Algorithmus für KNAPSACK
1:12:18 Grenzen für den Greedy-Algorithmus
Comments
In Channel
Download from Google Play
Download from App Store
United States00:00
00:00
x
