KIT | KIT-Bibliothek | Impressum | Datenschutz

Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 19.01.2016, Vorlesung - 19

Sanders, Peter

  • 0:00:00 Starten
  • 0:03:08 Beweis SUBSET SUM
  • 0:03:31 Beweis ""SUBSET SUM ist NP-hart""
  • 0:03:34 SUBSET SUM
  • 0:06:04 Die SUBSET SUM Instanz
  • 0:10:08 Beispiel
  • 0:13:55 Beweisidee
  • 0:18:29 F erfüllbar -> Instanz lösbar
  • 0:20:42 Instanz lösbar -> F erfüllbar
  • 0:23:44 Beispiel Rucksackproblem
  • 0:24:29 Rucksackproblem
  • 0:26:11 Reduktionen
  • 0:26:56 PARTITION
  • 0:28:30 Beweis SUBSET SUM <= pPARTITION
  • 0:38:39 Integer Linear Programming (ILP)
  • 0:40:14 Beweis von ""ILP ist NP-hart""
  • 0:41:18 Ist ILP in NP ?
  • 0:44:52 Umgang mit NP-harten Probleme
  • 0:55:29 Optimierungsprobleme
  • 0:56:11 NP vollständig
  • 0:57:26 Nichtapproximierbarkeit des Handlungsreisendenproblems (TSP)
  • 1:00:20 alpha-Approximation von TSP
  • 1:01:13 HamiltonCycle<=palpha-Approximation von TSP
  • 1:05:45 Pseudopolynomielle Algorithmen
  • 1:07:56 Beispiel Rucksackproblem

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