Berechenbarkeit und Komplexität

Kurzame
Berech. u. Komplexität
Modulnummer
TI5001
Modulverantwortlicher
  • Bettina Just
Dozent
  • 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
  • Halteproblem
  • 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