BRICS · Contents · Programme

Algorithmic Topics In Constraint Programming

A BRICS Mini-Course
November 15, 22 and 29, 2005

Lectures by
Irit Katriel, irit@daimi.au.dk
BRICS, Dept. of Computer Science, University of Aarhus


Course Contents

Constraint Programming (CP) is a general name for programming paradigms in which the programmer does not provide an algorithm, but rather specifies a set of properties that the solution must have (the constraints) and leaves it up to the solver to find the solution. Linear programming and SAT solving are special cases in which the constraints are restricted (linear inequalities or CNF formulas, respectively). In its most general form, CP does not restrict the types of constraints that may appear in a program.

The aim of this course is to serve as an introduction to algorithmic research in Constraint Programming. While CP applies many "AI-ish" and heuristic approaches, there are also plenty of crisp algorithmic problems which may appeal to the more theoretically-minded types.

I will assume that the students have basic knowledge in algorithms and data structures. In particular, I will assume familiarity with the following concepts: priority queue, graph (directed/undirected), bipartite graph, matching, perfect matching, flow (in a directed graph), the Ford-Fulkerson algorithm for finding a maximum flow, residual graph.

Course material available at: www.daimi.au.dk/ irit/teaching/CP_course/

Programme

Tuesday November 15, 2005, 10:15-12:00 in Shannon 159

Tuesday November 22, 2005, 10:15-12:00 in Shannon 159

Tuesday November 29, 2005, 10:15-12:00 in Shannon 159