BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Constraint Satisfaction Problems - Diptarko Roy\, Churchill Colleg
 e
DTSTART:20171129T193000Z
DTEND:20171129T200000Z
UID:TALK96562@talks.cam.ac.uk
CONTACT:Matthew Ireland
DESCRIPTION:Constraint satisfaction problems (CSPs) involve finding an ass
 ignment of discrete values to variables under the presence of constraints 
 which limit what combinations of assignments are allowed. An example would
  be colouring a graph with a limited number of colours\, such that no two 
 adjacent nodes have the same colour\, or solving a Sudoku puzzle.  These b
 oth involve potentially searching a combinatorially large space of candida
 te solutions for a feasible assignment.\n\nThe talk will begin with an int
 roduction to CSPs and some examples\, and point out the specific deficienc
 ies of naive approaches such as basic backtracking (as in Prolog)\, and ho
 w constraint propagation and specialised algorithms for global constraints
  improve on this. We’ll then see how a sequence of successively more sop
 histicated approaches and heuristics reduce graph colouring and Sudoku fro
 m requiring intractable amounts of time to being solvable within seconds.
LOCATION:Wolfson Hall\, Churchill College
END:VEVENT
END:VCALENDAR