07: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 16.11.2017

Theoretische Grundlagen der Informatik, Vorlesung, WS17/18

コンテンツは Karlsruher Institut für Technologie (KIT) によって提供されます。エピソード、グラフィック、ポッドキャストの説明を含むすべてのポッドキャストコンテンツは、Karlsruher Institut für Technologie (KIT) またはそのポッドキャストプラットフォームパートナーによって直接アップロードされ、提供されます。誰かがあなたの著作権で保護された作品をあなたの許可なく使用していると思われる場合は、ここで概説されているプロセスに従うことができますhttps://ja.player.fm/legal。

6+ y ago 1:19:25

MP4•エピソードのホーム

アーカイブされたシリーズ ("無効なフィード" status)

When? This feed was archived on April 24, 2022 14:32 (2y ago). Last successful fetch was on March 31, 2021 15:27 (3y ago)

Why? 無効なフィード status. サーバーは持続期間に有効なポッドキャストのフィードを取得することができませんでした。

What now? You might be able to find a more up-to-date version using the search function. This series will no longer be checked for updates. If you believe this to be in error, please check if the publisher's feed link below is valid and contact support to request the feed be restored or if you have any other concerns about this.

07 | 0:00:00 Starten 0:00:06 Definitionen zur TM 0:01:15 Unentscheidbarkeit der Diagonalsprache 0:02:42 Die Universelle Sprache 0:09:51 Satz von Rice - Motivation 0:17:10 Das Post'sche Korrespondenzproblem 0:21:44 Eigenschaften von (semi-)entscheibaren Sprachen 0:28:02 Komplexitätstheorie 0:32:53 Wie sieht ein Problem aus? 0:37:56 Definition: Problem 0:39:34 Definition: Kodierungsschema 0:43:19 Äquivalenz von Kodierungsschemata 0:44:33 Entscheidungsprobleme 0:46:43 Korrespondenz von Entscheidungsproblemen und Sprachen 0:51:27 Zeitkomplexität 0:53:04 Die Klasse P 0:56:35 Algorithmus OPT-TOUR (als Beweis) 0:59:27 Die Nichtdeterministische Turingmaschine 1:04:41 Übertragung auf Entscheidungsprobleme PI 1:07:16 Bemerkungen zur NTM 1:13:15 Die Klasse NP

19 つのエピソード