KIT | KIT-Bibliothek | Impressum | Datenschutz

09: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 26.11.2019

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

  • 0:00:00 Start
  • 0:00:08 Letzte Vorlesung
  • 0:08:16 Plan für heute
  • 0:10:46 Das Problem 3SAT
  • 0:12:53 Beweis: NP-Vollständigkeit von 3SAT
  • 0:31:50 Das Problem 2SAT
  • 0:34:00 Das Problem MAX2SAT
  • 0:36:49 Das Problem CLIQUE
  • 0:39:07 Beweis: NP-Voillständigkeit von CLIQUE
  • 0:54:25 Das Problem COLOR
  • 0:55:33 Beweis: NP-Vollständigkeit von 3COLOR
  • 0:57:09 Konstruktion von 3COLOR-Instanz G
  • 1:02:30 Polynomialität der Reduktion
  • 1:03:12 Instanz G 3-färbbar
  • 1:08:08 Zwischenstand Polynomiale Reduktion
  • 1:10:27 Das Problem EXACT COVER
  • 1:12:53 Beweis: NP-Vollständigkeit von EXACT COVER
  • 1:14:34 Konstruktion von (X, S)
  • 1:22:00 G 3-färbbar -> exakte Überdeckung
Open Access Logo


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