KIT | KIT-Bibliothek | Impressum | Datenschutz

Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 01.12.2016, 08

Wagner, Dorothea; KIT | Webcast [Hrsg.]

  • 0:00:00 Starten
  • 0:00:37 Wiederholung: NP-Vollständigkeit
  • 0:06:10 Wiederholung: Transitivität der poly. Transformation
  • 0:06:40 Wiederholung: Korollar
  • 0:07:37 Wiederholung: Das Problem SAT (satisfiability)
  • 0:12:17 Das Problem 3-SAT
  • 0:13:13 Beweis: NP-Vollständigkeit von 3-SAT
  • 0:30:07 Das Problem 2SAT
  • 0:34:40 Das Problem MAX2SAT
  • 0:38:02 Das Problem CLIQUE
  • 0:39:32 Beweis: NP-Vollständigkeit von CLIQUE
  • 0:51:19 Das Problem COLOR
  • 0:54:56 Beweis: NP-Vollständigkeit von 3COLOR
  • 0:57:29 Konstruktion von 3COLOR-Instanz G
  • 1:01:05 Beispielgraph zur Reduktion
  • 1:04:20 Polynomialität der Reduktion
  • 1:04:56 Instanz I erfüllbar => Instanz G erfüllbar
  • 1:07:12 Instanz I erfüllbar <= Instanz G erfüllbar
  • 1:08:02 Das Problem EXACT COVER
  • 1:13:06 Beweis: NP-Vollständigkeit von EXACT COVER
  • 1:14:28 Konstruktion von (X,S)
  • 1:24:05 G dreifärbbar => (X,S) hat exakte Überdeckung
  • 1:25:47 G dreifärbbar <= (X,S) hat exakte Überdeckung

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