KIT | KIT-Bibliothek | Impressum | Datenschutz

Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 01.02.2017, 24

Worsch, Thomas; KIT | Webcast [Hrsg.]

  • 0:00:00 Starten
  • 0:00:59 Algorithmusbegriss informell
  • 0:03:47 Erinnerung: partielle Funktion von A nach B
  • 0:05:39 Turingmaschinen: Ursprung
  • 0:08:33 Eine Turingmaschine im Bild
  • 0:13:48 Turingmaschine formalisiert
  • 0:15:28 Turingmaschine: graphische Darstellung
  • 0:19:23 Turingmaschine: tabellarische Darstellung
  • 0:20:26 Beispielberechnung
  • 0:23:01 Turingmaschine: Konfigurationen
  • 0:25:48 Turingmaschine: "" überschaubare"" Bandbeschriftungen
  • 0:27:48 Ein Schritt einer Turingmaschine
  • 0:30:31 Längere Beispielberechnung von BB3
  • 0:33:13 Berechnungen und Endkonfigurationen
  • 0:36:18 Rechnen bir zur Endkonfiguration
  • 0:37:14 zwei Arten von Turingmaschinen
  • 0:38:15 Eingaben und Anfangskonfigurationen
  • 0:40:53 Ergebnisse von Turingmaschinenberechnungen
  • 0:44:19 Beispiel: Palindromerkennung
  • 0:58:27 Entscheidbare und aufzählbare Sprachen
  • 1:01:36 Was ist wichtig
  • 1:06:22 Berechungskomplexität
  • 1:07:59 Zeitkomplexität - der Rechenzeitbedarf einer TM
  • 1:12:43 Zeitkomplexität der TM für Palindromerkennung
  • 1:14:39 Platzkomplexität oder Raumkomplexität einer TM
  • 1:15:54 Raumkomplexität der TM für Palindromerkennung
  • 1:17:18 Zeitkomplexität versus Raumkomplexität
  • 1:20:03 Eine Komplexitätsklasse ist eine Menge von Problemen
  • 1:22:29 P und PSPACE - zwei wichtige Komplexitätsklassen
  • 1:25:02 Beziehung zwischen P und PSPACE - unklar
  • 1:27:55 Was ist wichtig
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Anthropomatik und Robotik (IAR)
Publikationstyp Audio & Video
Publikationsdatum 09.02.2017
Erstellungsdatum 01.02.2017
DOI 10.5445/DIVA/2017-97
Identifikator KITopen-ID: 1000114511
Lizenz KITopen-Lizenz
Serie Grundbegriffe der Informatik, Vorlesung, WS 2016/17
Folge 24
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page