Website
Modulhandbuch vor WS 2014/15

Modul CS4003

Komplexitätstheorie (Komplex)

Dauer:


1 Semester
Angebotsturnus:


Wird nicht mehr angeboten
Leistungspunkte:


4
Studiengang, Fachgebiet und Fachsemester:
  • Master Informatik 2012 (Wahlpflicht), Anwendungsfach IT-Sicherheit und Zuverlässigkeit, 2. oder 3. Fachsemester
  • Master Informatik 2012 (Pflicht), Vertiefungsblock Algorithmik und Komplexität, 2. oder 3. Fachsemester
  • Master Mathematik in Medizin und Lebenswissenschaften 2010 (Wahl), Informatik, 2. Fachsemester
Lehrveranstaltungen:
  • Komplexitätstheorie (Vorlesung mit Übungen, 3 SWS)
Workload:
  • 45 Stunden Präsenzstudium
  • 65 Stunden Selbststudium und Aufgabenbearbeitung
  • 10 Stunden Prüfungsvorbereitung
Lehrinhalte:
  • Struktur von Zeit- und Platz-Klassen, Polynomiellle Hierarchie
  • Vergleich verschiedener Reduktionsarten, Vollständigkeitsbegriffe
  • uniforme und nichtuniforme Berechnungsmodelle
  • Randomisierung, Berechnungen mit Fehlern
  • Kommunikationskomplexität, interaktive Protokolle
  • Separation von Komplexitätsklassen, Relativierung
  • Quanten- und DNA-Computing
Qualifikationsziele/Kompetenzen:
  • tieferes Verständnis der Begriffe und Methoden der Komplexitätsanalyse
  • Kenntnis der Beziehungen zwischen Maschinenmodellen und Komplexitätsmaßen
  • Fähigkeit, algorithmische Probleme bezüglich ihrer Komplexität einzuordnen
Vergabe von Leistungspunkten und Benotung durch:
  • Mündliche Prüfung
Setzt voraus:
Modulverantwortlicher:
Lehrende:
Literatur:
  • R. Reischuk: Einführung in die Komplexitätstheorie - Teubner, 1990
  • S. Arora, B. Barak: Computational Complexity - Cambridge UP 2009
  • C. Papadimitriou: Computational Complexity - Addison-Wesley, 1994
  • K. Wagner, G. Wechsung: Computational Complexity - Reidel, 1986
  • J. van Leeuwen: Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity - Elsevier 1990
Sprache:
  • Englisch, außer bei nur deutschsprachigen Teilnehmern
Letzte Änderung:
2.3.2021

Modulhandbuch online

Zur Liste aller Module

Modulhandbuch als PDF

Modulhandbuch Master Informatik