Berechenbarkeit und Komplexität

Modulnummer
TI5001
Modulverantwortliche
Bettina Just
Dozenten
  • Wolfgang Henrich
  • Bettina Just
  • Hans-Rudolf Metz
  • Albert Schneider
  • Kurzbeschreibung
    Die Vorlesung behandelt: Berechenbarkeit, Entscheidbarkeit, rekursive Aufzählbarkeit; Halteprobleme; Gödels Unvollständigkeitssatz; Zeitkomplexitätsklassen; P-NP-Problem; Cooks Satz.
    Qualifikations- und Lernziele

    Die Absolvierenden haben fundierte Kenntnisse über:

    • Grundsätzliche Möglichkeiten und Grenzen der Algorithmisierbarkeit
    • Komplexitätsklassen von Berechnungsproblemen, insbesondere P und NP

    • Die Absolvierenden sind in fachergreifenden Diskussionen in der Lage, die grundsätzlichen Möglichkeiten der Informatik erzeugend darzulegen.

    Lerninhalte
    • Turing-Maschinen, -Berechenbarkeit, -Aufzählbarkeit, -Entscheidbarkeit
    • primitiv- und mu-Rekursivität
    • Ackermannfunktion
    • Haltepro p blem ,
    • Reduzierbarkeit
    • Komplexitätsklassen, Zeitkomplexität, Speicherkomplexität
    • P-NP-Problem, NP-Vollständigkeit
    • Erfüllbarkeits-Problem der Aussagenlogik (SAT)
    • Cookscher Satz
    • Approximierbarkeit NP-vollständiger Berechnungsprobleme
    • Optional: Fortgeschrittenere Themen wie Zufälligkeit und Pseudozufälligkeit, Anwendungen in der Kryptographie, PCP-Theorem, Beschreibungskomplexität
    Moduldauer (Semester)
    1
    Unterrichtssprache
    Deutsch
    Gesamtaufwand
    6 CrP; 180 Stunden, davon etwa 60 Stunden Präsenzzeit.
    Semesterwochenstunden
    4
    Lernformen

    Seminaristischer Unterricht 4 SWS

    Geprüfte Leistung

    Prüfungsvorleistung: 2 anerkannte Hausübungen Prüfungsleistung: Klausur

    Bewertungsstandard

    Bewertung der Prüfungsleistung nach § 9 der Prüfungsordnung (Teil I)

    Häufigkeit des Angebots
    Einmal im Jahr
    Literatur
    • M. Sipser: Introduction to the Theory of Computation PWS Publishing Company
    • S. Arora, B. Barak: Computational Complexity - A Modern Approach, Cambridge University Press
    • V. Vazirani: Approximation Algorithms, Springer
    • I. Wegener: Komplexitätstheorie, Springer
    Voraussetzungen

    Keine

    Voraussetzung für Module