Die bekannten Komplexitätsklassen P und NP klassifizieren Entscheidungsprobleme. In vielen Fällen ist man aber daran interessiert, _was_ die Lösung ist, und nicht nur ob eine Lösung existiert. In diesem Seminar wollen wir uns anschauen, in welche Komplexitätsklassen man Suchprobleme klassifizieren kann und wann und wie sich die Komplexität von ihren Entscheidungsversionen unterscheiden.
Insbesondere betrachten wir totale Suchprobleme, also Probleme die immer eine Lösung haben die dennoch schwer zu finden ist. Komplexitätsklassen mit denen wir uns beschäftigen werden sind zum Beispiel PLS, PPAD, PPP, CLS/EOPL/PLS geschnitten PPAD und UEOPL.
Die Literatur ist in Englisch, die Vorträge können auf Deutsch oder Englisch sein, abhängig vom Publikum.
Master-Studierende der Informatik oder Mathematik
- Vorlesung "Höhere Algorithmik" oder vergleichbare Veranstaltung
- P, NP und Reduktionen sind bekannt
Spezialliteratur aus Zeitschriften
Course No | Course Type | Hours |
---|---|---|
19306711 | Seminar | 2 |
Time Span | 18.04.2024 - 18.07.2024 |
---|---|
Instructors |
Michaela Krüger
|
0086c_k150 | 2014, BSc Informatik (Mono), 150 LPs |
0086d_k135 | 2014, BSc Informatik (Mono), 135 LPs |
0087d_k90 | 2015, BSc Informatik (Kombi), 90 LPs |
0088d_m60 | 2015, MSc Informatik (Kombi), 60 LPs |
0089c_MA120 | 2014, MSc Informatik (Mono), 120 LPs |
0207b_m37 | 2015, MSc Informatik (Lehramt), 37 LPs |
0208b_m42 | 2015, MSc Informatik (Lehramt), 42 LPs |
0458a_m37 | 2015, MSc Informatik (Lehramt), 37 LPs |
0471a_m42 | 2015, MSc Informatik (Lehramt), 42 LPs |
0496a_MA120 | 2016, MSc Computational Science (Mono), 120 LPs |
0556a_m37 | 2018, M-Ed Fach 1 Informatik (Lehramt an Integrierten Sekundarschulen und Gymnasien), 37 LPs |
0556b_m37 | 2023, M-Ed Informatik Fach 1 (Lehramt an Integrierten Sekundarschulen und Gymnasien), 37 LP |
0557a_m42 | 2018, M-Ed Fach 2 Informatik (Lehramt an Integrierten Sekundarschulen und Gymnasien), 42 LPs |
0557b_m42 | 2023, M-Ed Informatik Fach 2 Informatik (Lehramt an Integrierten Sekundarschulen und Gymnasien), 42 LPs |
Day | Time | Location | Details |
---|---|---|---|
Thursday | 14-16 | T9/SR 006 Seminarraum | 2024-04-18 - 2024-07-18 |