22: Turinmaschinen und Sprachen: Ein Überblick über Endkonfigurationen und Entscheidbarkeit
In dieser Sitzung werden die Konzepte von Turinmaschinen, Endkonfigurationen, entscheidbaren und aufzählbaren Sprachen sowie die Komplexitätsklassen P und PSPACE behandelt. Die Themen umfassen unter anderem endliche Automaten, ein Beispiel für eine nicht
KIT Lehre und Wissen
1.2K views • Jan 23, 2019
About this video
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
Dozent:
Dr. Thomas Worsch | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik
Vorlesungsaufzeichnung: KIT | WEBCAST
http://webcast.kit.edu
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
Dozent:
Dr. Thomas Worsch | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik
Vorlesungsaufzeichnung: KIT | WEBCAST
http://webcast.kit.edu
Tags and Topics
Browse our collection to discover more content in these categories.
Video Information
Views
1.2K
Likes
11
Duration
01:24:54
Published
Jan 23, 2019
User Reviews
4.2
(1) Related Trending Topics
LIVE TRENDSRelated trending topics. Click any trend to explore more videos.
No specific trending topics match this video yet.
Explore All Trends