KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Wagner, Dorothea; Sauer, Jonas; Brückner, Guido; Zentrum für Mediales Lernen (ZML) [Hrsg.]

  • 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
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 06.12.2019
Erstellungsdatum 05.12.2019
DOI 10.5445/DIVA/2019-953
Identifikator KITopen-ID: 1000117104
Lizenz KITopen-Lizenz
Serie Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20
Folge 11
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page