KIT | KIT-Bibliothek | Impressum | Datenschutz

Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 09.02.2016, Vorlesung und Übung - 25

Sanders, Peter; Gog, Simon

  • 0:00:00 Starten
  • 0:02:07 Caesar-Chiffre
  • 0:05:07 Monoalphabetische Verschiebungschiffre
  • 0:06:57 Vigenère-Verschlüsselung
  • 0:20:34 Set Cover
  • 0:27:01 Set Cover Beispiel 1
  • 0:27:37 Set Cover ist NP-vollständig
  • 0:27:53 Beweis ""Set Cover ist NP-hart""
  • 0:35:36 Set Cover Beispiel 2
  • 0:37:40 Beweis F erfüllbar
  • 0:41:18 Bewies ""3SAT ist NP-hart""
  • 0:42:14 Negation in die Blätter drücken
  • 0:43:25 Nichtblattknoten -> Neue Variablen
  • 0:47:21 Clique
  • 0:47:43 Clique Beispiel
  • 0:50:22 Subset Sum
  • 0:50:50 Die Subset Sum Instanz
  • 0:52:51 Integer Linear Programming (ILP)
  • 0:53:30 Directed Hamilton Cycle (DHC)
  • 0:56:23 Umgang mit NP-harten Problemen
Open Access Logo


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