Seminar Komplexität Boolescher Funktionen
Dozent: Prof. Dr. Christoph Berkholz
Inhalt
In diesem Seminar befassen wir uns mit der Komplexität von booleschen Funktion in eingeschränkten Berechnungsmodellen, wie Schaltkreisen oder Entscheidungsdiagrammen.
Im Gegensatz zur klassischen Komplexitätstheorie, in der boolesche Funktionen bzw. Entscheidungsprobleme bezüglich ihres Ressourcenverbrauchs auf Turingmaschinen charakterisiert werden und Härtebeweise häufig auf unbewiesenen Annahmen, wie P≠NP, beruhen, können untere Schranken an die Größe von bestimmten Schaltkreisen und Entscheidungsbäumen, die konkrete Funktionen berechnen, ohne komplexitätstheoretische Annahmen bewiesen werden.
Ziel des Seminars ist es, verschiedene Berechnungsmodelle für boolesche Funktionen zu kennenzulernen und sich Techniken zum Beweisen unterer Schranken anzueignen.
Zeit / Ort
Ort: Seminarraum RUD25, 3.408
Zeit: wird in Moodle bekannt gegeben, geplant ist:
- Ein Vorbesprechungstermin Ende Oktober 2021.
- Blockseminar an 2-3 Terminen im Januar/Februar 2022.
Organisation
Das Seminar ist als Blockseminar in Präsenz geplant. Um am Seminar teilzunehmen, schreiben Sie sich in AGNES ein.
Weitere Informationen und Termine werden in Moodle bereitgestellt. Der Einschreibeschlüssel zum Moodle-Kurs wird zum Vorlesungsbeginn an die in AGNES zugelassenen Studierenden verschickt.
Beachten Sie die aktuellen Hygieneregeln zur Teilnahme an Präsenzveranstaltungen.