KIT | KIT-Bibliothek | Impressum | Datenschutz

08: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 27.11.2018

Ueckerdt, Torsten; KIT | Webcast [Hrsg.]

  • 0:00:00 Start
  • 0:00:22 Letzte Vorlesung
  • 0:06:59 Plan für heute
  • 0:09:46 Pas Problem 3SAT
  • 0:11:29 Beweis: NP-Vollständigkeit von 3SAT
  • 0:30:58 Das Problem 2SAT
  • 0:31:54 Das Problem MAX2SAT
  • 0:33:51 Das Problem CLIQUE
  • 0:35:32 Beweis: NP - Vollständigkeit von CLIQUE
  • 0:48:25 Das Problem COLOR
  • 0:50:25 NP-Vollständigkeit von 3COLOR
  • 0:52:26 Konstruktion von 3COLOR-Instanz G
  • 0:55:48 Polynomialität der Reduktion
  • 0:56:35 Instanz/ erfüllbar
  • 1:03:01 Zwischenstand Polynomiale Reduktion
  • 1:13:41 Das Problem EXACT COVER
  • 1:16:23 NP - Vollständigkeit von EXACT COVER
  • 1:18:00 Konstruktion
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 29.11.2018
Erstellungsdatum 27.11.2018
DOI 10.5445/DIVA/2018-901
Identifikator KITopen-ID: 1000116084
Serie Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page