KIT | KIT-Bibliothek | Impressum | Datenschutz

23: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 25.01.2019

Worsch, Thomas; KIT | Webcast [Hrsg.]

  • 0:00:00 Start
  • 0:00:05 Turingmaschinen
  • 0:04:32 Unentscheidbare Probleme
  • 0:04:59 Beispielcodierung
  • 0:16:51 Das Halteproblem
  • 0:19:24 Beweis mit Diagonalisierung
  • 0:30:28 Weitere unentscheidbare Probleme
  • 0:34:48 Erinnerung: BB3
  • 0:36:22 Fleißige Biber und die Busy-Beaver-Funktion
  • 0:43:20 Steam-Powered Turing Machine ;-)
  • 0:44:04 Zusammenfassung
  • 0:44:25 Beginn der Übung
  • 0:44:56 Endlicher Akzeptor
  • 0:48:28 Beispiele regulärer Sprachen
  • 0:52:19 Akzeptoren: Komplement
  • 0:54:53 Akzeptoren: Schnitt
  • 0:59:54 Akzeptoren: Vereinigung
  • 1:03:32 Reguläre Sprachen und kontextfreie Grammatiken
  • 1:07:38 Turing-Maschinen (TMs)
  • 1:17:10 Analyse: Zeit- und Platzbedarf
  • 1:18:56 TM: Akzeptor, Entscheider
  • 1:25:34 TMs und endliche Akzeptoren
  • 1:27:35 Church-Turing-These

Zugehörige Institution(en) am KIT Institut für Anthropomatik und Robotik (IAR)
Publikationstyp Audio & Video
Publikationsdatum 29.01.2019
Erstellungsdatum 25.01.2019
Sprache Deutsch
DOI 10.5445/DIVA/2019-97
Identifikator KITopen-ID: 1000116285
Lizenz KITopen-Lizenz
Serie Grundbegriffe der Informatik, Vorlesung, WS 2018/19
Folge 23
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page