VL Constraint Satisfaction: Algorithms and Complexity
Dozent: Prof. Dr. Christoph Berkholz
Inhalt
The Constraint Satisfaction Problem (CSP) models general search problems, where the goal is to find a solution that satisfies all given constraints. Due to its generality, constraint solving has multiple applications in computer science: examples include reasoning, scheduling and planning in artificial intelligence, query evaluation in databases, or optimization in operations research.
In this course, we focus on the theory of solving CSPs. We will learn about general purpose techniques from constraint programming such as constraint propagation and search strategies and discuss algorithmic approaches tailored towards specific types of constraints and restricted classes of instances.
The algorithmic part of this course is complemented by an in-depth complexity theoretic analysis of constraint solving. While the CSP is NP-complete in general, our goal is to understand on which classes of instances constraint solving becomes tractable and when it remains hard.
Zeit / Ort
Dienstag, 11-13, RUD26 1'305 (Vorlesung)
Donnerstag, 11-13, RUD26 1'305 (Vorlesung/Übung)
Organisation
Die Lehrveranstaltung findet in Präsenz statt, die Möglichkeit einer Onlineteilnahme ist nicht vorgesehen. Abhängig von den Teilnehmenden werden die Lehrinhalte auf Deutsch oder auf Englisch vermittelt.
Um an der Lehrveranstaltung teilzunehmen, schreiben Sie sich in AGNES zur Übung ein.
Weitere Informationen werden in Moodle bereitgestellt. Der Einschreibeschlüssel wird zum Vorlesungsbeginn an die in AGNES zugelassenen Studierenden verschickt und in der ersten Vorlesung am
Dienstag, 19.10.2021, 11:15, RUD26 1'305
bekannt gegeben.
Beachten Sie die aktuellen Hygieneregeln zur Teilnahme an Präsenzveranstaltungen.