Constraint Satisfaction - Interactive curriculae of TU Ilmenau
The interactive curriculae provide information on the degree programmes offered by the TU Ilmenau.
Please refer to the respective study and examination rules and regulations for the legally binding curricula (Annex Curriculum).
You can find all details on planned lectures and classes in the course catalogue.
Please note that this page is no longer updated. All modules and study plans from PO version 2021 onwards (Bachelor and Master study programs) are now available on the Campus Portal.
| module properties Constraint Satisfaction in degree program Master Informatik 2021 | |
|---|---|
| module number | 201196 |
| examination number | 2200874 |
| department | Department of Computer Science and Automation |
| ID of group | 2242 (Algorithms) |
| module leader | Prof. Dr. Christoph Berkholz |
| term | winter term only |
| language | Deutsch |
| credit points | 5 |
| on-campus program (h) | 34 |
| self-study (h) | 116 |
| obligation | elective module |
| exam | oral examination performance, 30 minutes |
| details of the certificate | |
| link to Moodle course | https://moodle.tu-ilmenau.de/course/view.php?id=3564 |
| teacher | Prof. Berkholz |
| signup details for alternative examinations | |
| maximum number of participants | |
| previous knowledge and experience | |
| learning outcome | - Die Studierenden kennen grundlegende Designkonzepte, um eigenständig Verfahren zur Lösung von Constraint Satisfaction Problemen zu entwickeln. - Die Studierenden sind in der Lage, CSP-Algorithmen anforderungsgerecht zu entwickeln und Methoden auf neue Probleme strategieorientiert anzuwenden. - Die Studierenden kennen grundlegende Begriffe und Methoden Komplexitätsanalyse von CSP-Klassen und sind in der Lage, selbständig Reduktionen zu entwickeln. Sie sind mit gängigen Komplexitätshypothesen vertraut, um CSP-Klassen einordnen und bewerten zu können. - Die Studierenden können die Komplexität von Constraint Satisfaction Problemen unter Berücksichtigung unterschiedlicher Beurteilungsmaßstäbe untersuchen, in Beziehung setzen und bewerten. - Die Studierenden sind in der Lage, aktuelle Forschungsergebnisse im Bereich Constraint Satisfaction durchdacht einzuordnen, methodisch nachzuvollziehen und strategieorientiert anzuwenden. |
| content | Das Constraint Satisfaction Problem (CSP) umfasst eine große Klasse von Suchproblemen, deren Ziel es ist, eine Lösung zu finden, die alle vorgegebenen Nebenbedingungen (Constraints) erfüllt. Durch seine Allgemeinheit haben das CSP und seine Lösungsmethoden (constraint solving) Anwendungen in vielfältigen Bereichen der Informatik, beispielsweise beim Planen und Scheduling, der kombinatorischen Optimierung, dem automatischen Schließen und der Anfrageauswertung in Datenbanken. Dieses Modul widmet sich der Theorie des Constraint Satisfaction Problems. Im algorithmischen Teil werden sowohl generelle Lösungsmethoden, wie Constraint Propagation und Suchstrategien, als auch spezialisierte Techniken, welche die Struktur spezifischer Constraints und des Constraintnetzwerks ausnutzen, betrachtet. Komplementiert wird der algorithmische Teil durch eine detaillierte Komplexitätsbetrachtung des CSPs. Die Kernfrage ist hierbei: Welche Arten von CSPs lassen sich effizient lösen und für welche Klassen von CSP-Instanzen ist dies (unter gewissen Komplexitätsannahmen) nicht möglich? |
| media of instruction and technical requirements for education and examination in case of online participation | |
| literature / references | Die Vorlesung folgt einem eigenen Skript. Als Einstieg und Hintergrund des algorithmischen Teils ist zu empfehlen: Rina Dechter: Constraint processing. Elsevier Morgan Kaufmann 2003 Krzysztof R. Apt: Principles of constraint programming. Cambridge University Press 2003 |
| evaluation of teaching | |