Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

11: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 05.12.2019

Listen Later
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
...more
View all episodesView all episodes
Download on the App Store
Theoretische Grundlagen der Informatik, Vorlesung, WS19/20By Karlsruher Institut für Technologie (KIT)

More shows like Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

View all
KIT Campus – Studieren und mehr | 2013 by Karlsruher Institut für Technologie (KIT)

KIT Campus – Studieren und mehr | 2013

0 Listeners

IEEE International Conference on Robotics and Automation, 2013 by Karlsruher Institut für Technologie (KIT)

IEEE International Conference on Robotics and Automation, 2013

0 Listeners

CAD tutorial in Mechanical Design, WT13/14 by Karlsruhe Institute of Technology (KIT)

CAD tutorial in Mechanical Design, WT13/14

0 Listeners

KIT Campus – Studieren und mehr | 2014 by Karlsruher Institut für Technologie (KIT)

KIT Campus – Studieren und mehr | 2014

0 Listeners

Internationales Forum am ZAK by Karlsruher Institut für Technologie (KIT)

Internationales Forum am ZAK

0 Listeners

Transport Phenomena in the Biosphere by Karlsruher Institut für Technologie (KIT)

Transport Phenomena in the Biosphere

0 Listeners

Einführung in die Geophysik 1, WS17/18, Vorlesung by Karlsruher Institut für Technologie (KIT)

Einführung in die Geophysik 1, WS17/18, Vorlesung

0 Listeners

Edeltalk - mit Dominik & Kevin by Papaplatte & Reeze

Edeltalk - mit Dominik & Kevin

18 Listeners

Kulturwissenschaft gestern und morgen by Karlsruher Institut für Technologie (KIT)

Kulturwissenschaft gestern und morgen

0 Listeners