Aufbauend auf die VU Komplexitätstheorie werden weiterführende Themen im Bereich der Komplexitätstheorie behandelt. Im Wintersemester 2016/7 werden wir die Komplexität von "counting problems" und "enumeration problems" näher betrachten.
Die TeilnehmerInnen werden mit wesentliche Forschungsartikel zu "counting problems" und "enumeration problems" vertraut gemacht. Dabei werden wir sowohl klassische Grundlagen-Artikel in diesen Bereichen anschauen als auch Artikel aus der neueren Forschungsliteratur mit Komplexitätsanalysen konkreter (Zähl- und Aufzähl-)Probleme.
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.
65 h Erstellung der Kurzzusammenfassungen und Präsentationen 10 h Anwesentheit
----------------------------------------------------------------
75 h = 3 Ects
Im Laufe des Semester wird jede/r TeilnehmerInnen 2 Forschungsartikel bearbeiten, d.h.: Erstellung einer Kurzzusammenfassung und einer Präsentation im Seminar. Weitere Details werden in der Vorbesprechung gegeben.
Voraussetzung: VU Komplexitätstheorie 181.142
