KIT | KIT-Bibliothek | Impressum | Datenschutz

12: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 10.12.2019

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

  • 0:00:00 Start
  • 0:00:42 Wiederholung letzte Vorlesung
  • 0:08:12 Definition
  • 0:14:31 Metrisches TSP
  • 0:16:07 Approximation von min-METRIC-TSP
  • 0:27:08 Bemerkungen zur Approximierbarkeit
  • 0:31:25 Approximationsschemata
  • 0:37:51 Ein FPTAS für max-KNAPSACK
  • 0:42:18 Pseudopolynomialer. optimaler Algorithmus für max-KNAPSACK
  • 0:52:46 Maximierungsprobleme
  • 1:01:47 Optimierungsprobleme
  • 1:10:58 Approximierbarkeit von min-Vertex-Color
  • 1:23:39 Abschluss des Kapitels zur Komplexitätstheorie
Open Access Logo


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