🚀 From Google Podcasts to Moon FM in No Time: Your Hassle-Free Migration Guide
👉

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

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

  • 1 hour 15 minutes
    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
    21 August 2015, 12:30 pm
  • 1 hour 24 minutes
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 09.12.2014, Lektion 11
    11: Vorlesung: Das Problem COLOR
    21 August 2015, 12:27 pm
  • 58 minutes 2 seconds
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 11.12.2014, Übung 4
    Übung 4: Turingmaschinen und Berechenbarkeit | Komplexitätsklassen
    21 August 2015, 12:22 pm
  • 1 hour 24 minutes
    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
    21 August 2015, 12:18 pm
  • 1 hour 8 minutes
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 18.12.2014, Lektion 13
    13: Vorlesung: Komlexitätsklassen
    21 August 2015, 12:14 pm
  • 1 hour 17 minutes
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 08.01.2015, Übung 5
    Übung 5: Optimierungsproblem, Optimalwertproblem, Entscheidungsproblem | NP-vollständige Probleme
    21 August 2015, 12:10 pm
  • 1 hour 11 minutes
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 13.01.2015, Lektion 14
    14: Vorlesung: Grammatiken
    21 August 2015, 12:06 pm
  • 1 hour 23 minutes
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 15.01.2015, Lektion 15
    15: Vorlesung: Grammatiken
    21 August 2015, 12:03 pm
  • 1 hour 22 minutes
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 20.01.2015, Übung 6
    Übung 6: NP und co-NP | Pseudopolynomielle Algorithmen | Approximationsalgorithmen |Ganzzahlige Programme
    21 August 2015, 11:59 am
  • 1 hour 24 minutes
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 22.01.2015, Lektion 16
    16: Vorlesung: Kontextfreie Sprachen
    21 August 2015, 11:53 am
  • 1 hour 28 minutes
    Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 27.01.2015, Lektion 17
    17: Vorlesung: Kontextfreie Sprachen
    21 August 2015, 11:48 am
  • More Episodes? Get the App
About Theoretische Grundlagen der Informatik, Vorlesung, WS14/15
Links
Listeners Also Subscribed To
© MoonFM 2024. All rights reserved.