26 episodes

Die Vorlesung gibt eine Einführung in die theoretischen Grundlagen der Informatik. Folgende Themen werden u.a. behandelt:
1. Formale Sprachen und Automatentheorie Chomsky-Hierarchie (reguläre, kontextfreie, Typ0-Sprachen, reguläre Ausdrücke) Grammatiken (Typen, Eindeutigkeit, Abgeschlossenheit) Automatenmodelle (endliche Automaten, Kellerautomaten, Turingmaschinen)
2. Entscheidbarkeit und Berechenbarkeit Entscheidbarkeit, Aufzählbarkeit Universelle Turingmaschine, Diagonalisierung, Halteproblem Berechenbarkeit, µ-rekursive Funktionen, Church/Turing-These
3. Komplexitätstheorie Optimierungs- und Entscheidungsprobleme Codierung Klassen P und NP, NP-Vollständigkeit Parametrisierte Komplexität

Theoretische Grundlagen der Informatik Universität Konstanz

    • Technology

Die Vorlesung gibt eine Einführung in die theoretischen Grundlagen der Informatik. Folgende Themen werden u.a. behandelt:
1. Formale Sprachen und Automatentheorie Chomsky-Hierarchie (reguläre, kontextfreie, Typ0-Sprachen, reguläre Ausdrücke) Grammatiken (Typen, Eindeutigkeit, Abgeschlossenheit) Automatenmodelle (endliche Automaten, Kellerautomaten, Turingmaschinen)
2. Entscheidbarkeit und Berechenbarkeit Entscheidbarkeit, Aufzählbarkeit Universelle Turingmaschine, Diagonalisierung, Halteproblem Berechenbarkeit, µ-rekursive Funktionen, Church/Turing-These
3. Komplexitätstheorie Optimierungs- und Entscheidungsprobleme Codierung Klassen P und NP, NP-Vollständigkeit Parametrisierte Komplexität

Top Podcasts In Technology

Listeners Also Subscribed To

More by Universität Konstanz