26 Folgen

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

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15 Karlsruher Institut für Technologie

    • Kurse

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

    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

    • 1 Std. 15 Min.
    • video
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 09.12.2014, Lektion 11

    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 09.12.2014, Lektion 11

    11: Vorlesung: Das Problem COLOR

    • 1 Std. 24 Min.
    • video
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 11.12.2014, Übung 4

    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 11.12.2014, Übung 4

    Übung 4: Turingmaschinen und Berechenbarkeit | Komplexitätsklassen

    • 58 Min.
    • video
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 16.12.2014, Lektion 12

    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

    • 1 Std. 24 Min.
    • video
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 18.12.2014, Lektion 13

    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 18.12.2014, Lektion 13

    13: Vorlesung: Komlexitätsklassen

    • 1 Std. 8 Min.
    • video
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 08.01.2015, Übung 5

    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 08.01.2015, Übung 5

    Übung 5: Optimierungsproblem, Optimalwertproblem, Entscheidungsproblem | NP-vollständige Probleme

    • 1 Std. 17 Min.

Top‑Podcasts in Kurse

Mehr von Karlsruher Institut für Technologie