
06: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 15.11.2018
Autor
Herausgeber
Beteiligtes Institut
Institut für Theoretische Informatik (ITI)
Genre
Beschreibung
06 |
0:00:00 Start
0:00:09 Letzte Vorlesung
0:03:24 Die Universelle Sprache
0:14:02 Satz von Rice – Motivation
0:17:55 Bemerkungen zum Satz von Rice
0:22:13 Das Post'sche Korrespondenzproblem
0:31:13 Eigenschaften von (semi-)entscheidbaren Sprachen
0:32:25 Komplexitätstheorie
0:34:36 Wie sieht ein Problem aus?
0:37:46 Definition: Problem
0:40:37 Definition:Kodierungsschema
0:46:51 Äquivalenz von Kodierungsschemata
0:48:35 Entscheidungsprobleme
0:50:57 Korrespondenz von Entscheidungsproblemen und Sprachen
0:52:43 Entscheidungsprobleme und Turing-Maschinen
0:54:34 Zeitkomplexität
0:57:38 Die Klasse P
1:01:00 Schwierigkeit von Entscheidungs- und Optimierungsproblem
1:04:53 Algorithmus OPT-TOUR (als Beweis)
1:10:08 Bemerkungen zum Algorithmus
1:13:17 Zwischenstand Komplexitätstheorie
1:17:01 Die Nichtdeterministische Turing-Maschine
1:23:02 Übertragung auf Entscheidungsprobleme II
Laufzeit (hh:mm:ss)
01:25:32
Serie
Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19
Publiziert am
19.11.2018
Fachgebiet
Lizenz
Auflösung | 1280 x 720 Pixel |
Seitenverhältnis | 16:9 |
Audiobitrate | 128000 bps |
Audio Kanäle | 2 |
Audio Codec | aac |
Audio Abtastrate | 48000 Hz |
Gesamtbitrate | 934102 bps |
Farbraum | yuv420p |
Container | mov,mp4,m4a,3gp,3g2,mj2 |
Medientyp | video/mp4 |
Dauer | 5132 s |
Dateiname | DIVA-2018-852_hd.mp4 |
Dateigröße | 599.243.514 byte |
Bildwiederholfrequenz | 25 |
Videobitrate | 800005 bps |
Video Codec | h264 |
Embed-Code