KIT | KIT-Bibliothek | Impressum | Datenschutz

06: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 15.11.2018

Ueckerdt, Torsten; KIT | Webcast [Hrsg.]

  • 0:00:00 Start
  • 0:00:09 Letzte Vorlesung
  • 0:03:24 Die Universelle Sprache
  • 0:14:02 Satz von Rice – Motivation
  • 0:17:55 Bemerkungen zum Satz von Rice
  • 0:22:13 Das Post'sche Korrespondenzproblem
  • 0:31:13 Eigenschaften von (semi-)entscheidbaren Sprachen
  • 0:32:25 Komplexitätstheorie
  • 0:34:36 Wie sieht ein Problem aus?
  • 0:37:46 Definition: Problem
  • 0:40:37 Definition:Kodierungsschema
  • 0:46:51 Äquivalenz von Kodierungsschemata
  • 0:48:35 Entscheidungsprobleme
  • 0:50:57 Korrespondenz von Entscheidungsproblemen und Sprachen
  • 0:52:43 Entscheidungsprobleme und Turing-Maschinen
  • 0:54:34 Zeitkomplexität
  • 0:57:38 Die Klasse P
  • 1:01:00 Schwierigkeit von Entscheidungs- und Optimierungsproblem
  • 1:04:53 Algorithmus OPT-TOUR (als Beweis)
  • 1:10:08 Bemerkungen zum Algorithmus
  • 1:13:17 Zwischenstand Komplexitätstheorie
  • 1:17:01 Die Nichtdeterministische Turing-Maschine
  • 1:23:02 Übertragung auf Entscheidungsprobleme II
Open Access Logo


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