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

Grundbegriffe der Informatik, Vorlesung, WS16/17

24 | 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