Nummer

INF3421
Titel

Komplexitätstheorie
Art der Vorlesung

Wahlpflicht
ECTS 6
Arbeitsaufwand
- Kontaktzeit
- Selbststudium
Arbeitsaufwand:
180 h
Kontaktzeit:
60 h / 4 SWS
Selbststudium:
120 h
Veranstaltungsdauer 1 Semester
Häufigkeit des Angebots Im Wintersemester
Unterrichtssprache Deutsch
Prüfungsform

Klausur (mündliche Prüfung bei geringer Teilnehmeranzahl)

Lehrform(en) Vorlesung
Inhalt

Themen sind u.a. Komplexitätsmaße und ihre grundlegenden Beziehungen, Hierarchiesätze, Reduktion und Vollständigkeit, Alternierung und Schaltkreise, die polynomielle Hierarchie und Komplexität von Fragen der Approximierbarkeit.

Qualifikationsziele

Die Studierenden haben eine Übersicht über das Gefüge der wichtigsten Komplexitätsklassen und daher einen Bezugsrahmen zur komplexitätsmäßigen Einordnung kombinatorischer Fragestellungen. Sie haben ein Problembewusstsein entwickelt bzgl.\ der anscheinenden notorischen Schwierigkeit der kombinatorischen Fragestellungen sowie der formalen Ungewissheit dieser Sachlage.

Vergabe von Leistungspunkten/Benotung
Lehrform
Status
SWS
LP
Prüfungsform
Prüfungsdauer
Benotung
Berechnung
Modulnote (%)
Teilnahmevoraussetzungen Es gibt keine besonderen Voraussetzungen.
Dozent/in Lange
Literatur / Sonstiges

Hopcroft u. Ullman, Introduction to automata theory, languages and computation, 1979 Rogers, The theory of recursive functions and effective computability, 1989 Arora and Barak. Computational complexity: a modern approach, 2009.

Zuletzt angeboten nicht bekannt
Geplant für derzeit nicht geplant
Zugeordnete Studienbereiche BIOINFM2510, INFM2510, INFM3410, MDZINFM2510, MEINFM3210