09: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 28.11.2017

Theoretische Grundlagen der Informatik, Vorlesung, WS17/18

เนื้อหาจัดทำโดย Karlsruher Institut für Technologie (KIT) เนื้อหาพอดแคสต์ทั้งหมด รวมถึงตอน กราฟิก และคำอธิบายพอดแคสต์ได้รับการอัปโหลดและจัดเตรียมโดย Karlsruher Institut für Technologie (KIT) หรือพันธมิตรแพลตฟอร์มพอดแคสต์โดยตรง หากคุณเชื่อว่ามีบุคคลอื่นใช้งานที่มีลิขสิทธิ์ของคุณโดยไม่ได้รับอนุญาต คุณสามารถปฏิบัติตามขั้นตอนที่อธิบายไว้ที่นี่ https://th.player.fm/legal

6+ y ago 1:09:58

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.

09 | 0:00:00 Starten 0:00:39 NP-Vollständigkeit 0:02:03 Transitivität der poly. Transformation 0:02:31 Korollar 0:03:49 Das Problem 3-SAT 0:05:37 Beweis: NP-Vollständigkeit von 3-SAT 0:20:16 Das Problem 2SAT 0:22:09 Das Problem MAX2SAT 0:24:18 Das Problem CLIQUE 0:27:48 Beweis: NP-Vollständigkeit von CLIQUE 0:36:44 Das Problem COLOR 0:37:57 Beweis: NP-Vollständigkeit von 3COLOR 0:39:06 Konstruktion von 3COLOR-Instanz G 0:43:16 Beispielgraph zur Reduktion 0:45:12 Polynomialität der Reduktion 0:45:35 Instantz I erfüllbar auch Instanz G erfüllbar 0:45:57 Instanz G ist 3-färbbar 0:50:30 Das Problem EXACT COVER 0:53:51 Beweis: NP-Vollständigkeit von EXACT COVER 0:55:30 Konstruktion von (X,S) 1:04:50 G dreifärbbar (X,S) hat exakte Überdeckung

19 ตอน