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

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