KIT | KIT-Bibliothek | Impressum | Datenschutz

Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 24.11.2016, 07

Wagner, Dorothea; KIT | Webcast [Hrsg.]

  • 0:00:00 Starten
  • 0:01:06 Die Klasse P
  • 0:03:19 Die Klasse NP
  • 0:04:47 Die Nichtdeterministische Turingmaschine
  • 0:05:17 Zeitkomplexität für NTM
  • 0:08:55 Große Frage der Theoretischen Informatik
  • 0:11:38 NP-Vollständigkeit
  • 0:24:35 Transitivität der poly. Transformation
  • 0:25:46 Korollar
  • 0:28:28 Das Problem SAT (satisfiability)
  • 0:31:05 Weitere Beispiele für SAT-Instanzen
  • 0:33:44 Der Satz von Cook (Steven Cook, 1971)
  • 0:36:00 Beweis
  • 0:42:53 Beweis: Konstruktion der Variablen
  • 0:49:48 Beweis
  • 0:53:35 Beweis: Konstruktion der Klauseln - Übersicht
  • 0:56:09 Klauselgruppe 1:
  • 0:59:10 Klauselgruppe 2:
  • 1:00:15 Klauselgruppe 3:
  • 1:01:50 Klauselgruppe 4:
  • 1:03:23 Klauselgruppe 5:
  • 1:04:36 Klauselgruppe 6:
  • 1:06:51 Klauselgruppe 6, 1:
  • 1:09:51 Klauselgruppe 6,2:
  • 1:13:35 Konstruktion der Klauseln - Zwischenergebnis
  • 1:15:11 Polynomialität der Transformation
  • 1:15:45 Polynomialität - Klauselgruppe 1:
  • 1:16:20 Polynomialität - Klauselgruppe 2:
  • 1:17:25 Polynomialität - Klauselgruppe 3:
  • 1:17:56 Polynomialität - Klauselgruppe 4:
  • 1:18:38 Polynomialität - Klauselgruppe 5:


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