Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 24.11.2016, 07

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

Το περιεχόμενο παρέχεται από το Karlsruher Institut für Technologie (KIT). Όλο το περιεχόμενο podcast, συμπεριλαμβανομένων των επεισοδίων, των γραφικών και των περιγραφών podcast, μεταφορτώνεται και παρέχεται απευθείας από τον Karlsruher Institut für Technologie (KIT) ή τον συνεργάτη της πλατφόρμας podcast. Εάν πιστεύετε ότι κάποιος χρησιμοποιεί το έργο σας που προστατεύεται από πνευματικά δικαιώματα χωρίς την άδειά σας, μπορείτε να ακολουθήσετε τη διαδικασία που περιγράφεται εδώ https://el.player.fm/legal.

7+ y ago 1:25:14

MP4•Αρχική οθόνη επεισοδίου

07 | 0:00:00 Starten 0:01:06 Die Klasse P 0:03:19 Die Klasse NP 0:04:47 Die Nichtdeterministische Turingmaschine 0:05:17 Zeitkomplexität für NTM 0:08:55 Große Frage der Theoretischen Informatik 0:11:38 NP-Vollständigkeit 0:24:35 Transitivität der poly. Transformation 0:25:46 Korollar 0:28:28 Das Problem SAT (satisfiability) 0:31:05 Weitere Beispiele für SAT-Instanzen 0:33:44 Der Satz von Cook (Steven Cook, 1971) 0:36:00 Beweis 0:42:53 Beweis: Konstruktion der Variablen 0:49:48 Beweis 0:53:35 Beweis: Konstruktion der Klauseln - Übersicht 0:56:09 Klauselgruppe 1: 0:59:10 Klauselgruppe 2: 1:00:15 Klauselgruppe 3: 1:01:50 Klauselgruppe 4: 1:03:23 Klauselgruppe 5: 1:04:36 Klauselgruppe 6: 1:06:51 Klauselgruppe 6, 1: 1:09:51 Klauselgruppe 6,2: 1:13:35 Konstruktion der Klauseln - Zwischenergebnis 1:15:11 Polynomialität der Transformation 1:15:45 Polynomialität - Klauselgruppe 1: 1:16:20 Polynomialität - Klauselgruppe 2: 1:17:25 Polynomialität - Klauselgruppe 3: 1:17:56 Polynomialität - Klauselgruppe 4: 1:18:38 Polynomialität - Klauselgruppe 5:

18 επεισόδια

#Hochschulbildung #Bildung #Vorlesung #Informatik #Berechnungsmodelle #Determinismus #Nichtdeterminismus #Berechenbarkeit #Komplexitätstheorie #Grammatiken #Karlsruher Instituts Für Technologie KIT #Video #KIT #Theorie