22: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 23.01.2019

22 | 0:00:00 Start 0:00:40 Endliche Automaten 0:02:22 Beispiel einer nicht erkennbaren Sprache 0:13:53 Zusammenfassung / Was ist wichtig ? 0:16:19 Turingmaschinen 0:19:33 Eine Turingmaschine im Bild 0:25:27 Turingmaschine: graphische Darstellung/ tabellarische Darstellung 0:28:42 Beispielberechnung 0:35:53 Längere Beispielberechnung von BB3 0:37:56 Berechnung und Endkonfigurationen 0:48:04 Beispiel: Palindromerkennung 0:56:10 Entscheidbare und aufzählbare Sprachen 1:01:54 Zeitkomplexität - der Rechenzeitbedarf einer TM 1:06:30 Raumkomplexität 1:07:49 Zeitkomplexität versus Raumkomplexität 1:09:48 Eine Komplexitätsklasse ist eine Menge von Problemen 1:11:35 P und PSPACE- Zwei wichtige Komplexitätsklassen 1:17:40 Unentscheidbare Probleme 1:19:46 Codierung von Turingmaschinen