Theoretische Grundlagen der Informatik, Vorlesung, WS14/15 Karlsruher Institut für Technologie (KIT)
-
- Bildung
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu
-
- video
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 04.12.2014, Lektion 10
10: Vorlesung: NP-Vollständigkeit | Das Problem 3-SAT | Beweis: NP-Vollständigkeit von 3-SAT | Das Problem 2SAT | Das Problem MAX2SAT | Das Problem CLIEQUE | Beweis: NP-Vollständigkeit von CLIQUE | Das Problem COLOR | Beweis: NP-Vollständigkeit von 3COLOR | Konstruktion von 3COLOR-Instanz G | Beispielgraph zur Reduktion | Polynomialität der Reduktion
-
- video
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 09.12.2014, Lektion 11
11: Vorlesung: Das Problem COLOR
-
- video
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 11.12.2014, Übung 4
Übung 4: Turingmaschinen und Berechenbarkeit | Komplexitätsklassen
-
- video
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 16.12.2014, Lektion 12
12: Vorlesung: Das Problem Subgraphisomorphie | Suchprobleme | Beispiel: TSP-Suchproblem | Beispiel: Hamilton-Kries Suchproblem | Aufzählungsprobleme | Reduzierbarkeit für Suchprobleme | Orakel-Turing-Maschine | Orakel-TM: Verhalten im Fragezustand | Turing-Reduktion | NP-schwer | Beweisskizze | Verallgemeinerte NP-Schwere | Das Problem INTERGER PROGRAMMING | Beweis | Pseudopolynomielle Algorithmen | Beispiel: Problem KNAPSACK | Starke NP-Vollständigkeit | Absolute Approximationsalgorithmen | Das allgemeine KNAPPSACK-Suchproblem | Satz | (Widerspruchs-)Beweis | Approximation mit relativer Gütegarantie | Beispiel: Greedy-Algorithmus für KNAPSACK
-
- video
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 18.12.2014, Lektion 13
13: Vorlesung: Komlexitätsklassen
-
- video
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 08.01.2015, Übung 5
Übung 5: Optimierungsproblem, Optimalwertproblem, Entscheidungsproblem | NP-vollständige Probleme