Mälardalens högskola, Institutionen för Datateknik

Inledning till Villkorsprogrammering, 5,0 poäng

Introduction to Constraint Programming

Kurskod:
Nivå:D/Doktorand
Ämne:DatalogiUtbildningsområde:Naturvetenskap
ECTS:
Kursspråk:Svenska (Engelska vid behov)
Fastställandedatum:
Förändringsdatum:
Giltig fr.o.m.:

Syfte

Presentera grundläggande begrepp, metoder och tillämpningar inom villkorsprogrammering

Innehåll

Grundläggande begrepp för villkorsproblem som satisfierbarhet och olika typer av konsistens samt algoritmer för sökning och för att säkerställa konsistens. Olika typer av domäner: Flyttalsintervall, Boolska och andra ändliga domäner. Specifika tekniker och metoder för ändliga domäner, villkorslogikprogrammering, beräkningsträd, sökning och propagering. Globala villkor, Villkors(hyper)grafer, generaliserad bågkonisistens och grafalgoritmer.Exempel på tillämpningar från planering, schemaläggning, packnings- och placeringsproblem.

Undervisning

Föreläsningar, inlämningsuppgifter och laborationer.

Särskild behörighet

(Datastrukturer och algoritmer 5p, en av kurserna Funktionell programmering 5p eller Logikprogrammering 5p och en av kurserna Kompilatorteknik 5p eller Automater, beräkningar och formella metoder 5p eller motsvarande.)

Elementär grafteori, diskret matematik, komplexitetsteori och helst logikprogrammering. Gärna grundläggande kombinatorik och optimeringslära.

Examination

INL2, 2,0 poäng, Inlämningsuppgifter
LAB3, 3,0 poäng, Laborationer

Betyg

U eller G.

Litteratur

Edward Tsang Introduction to constraint satisfaction
Kim Mariott & Edwars Stuckey Constraint Programming
Stenciler och vävplatser