Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage

• weiterführende Themen der Komplexitätstheorie zu bennen
• grundlegende Forschungsergebnisse über Probleme widerzugeben, die über die klassische Komplexitätstheorie von Entscheidungsproblemen hinausgehen
• die relevante Literatur zu Abzähl- und Aufzählproblemen  zu überblicken
• die Komplexität von Abzähl- und Aufzählproblemen  zu analysieren

Meistens, wenn detaillierte Komplexitätsanalysen durchgeführt werden, ist die Komplexität von "decision problems" gemeint. Hier gibt es auch die ausgereifteste Komplexitätstheorie zur Untersuchung und Komplexitätsklassifizierung von Problemen. In vielen Anwendungen sind aber "counting problems" und "enumeration problems" eventuell noch wichtiger als "decision problems", z.B.: im Datenbankenbereich, bei der Auswertung von Anfragen, ist man üblicherweise an der Ausgabe aller Antworten interessiert und nicht nur an der Frage, ob es zumindest eine Antwort gibt.

Die Studierenden müssen mündliche Präsentationen on ausgewählten Forschungsartikeln zu den im Seminar behandelten Themen vorbereiten

Aufwandsabschätzung

 65 h Erstellung der Kurzzusammenfassungen und Präsentationen
 10 h Anwesentheit

----------------------------------------------------------------

 75 h = 3 Ects

Die Beurteilung basiert auf den mündlichen Präsentationen

Voraussetzung: VU Komplexitätstheorie 181.142