Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

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.