ID2204 Villkorsprogrammering 7,5 hp

Constraint Programming

Kursen handlar om att modellera och lösa kombinatoriska (optimerings) problem med hjälp av villkorsprogrammering (constraint programming). Villkorsprogrammering har pekats ut somett strategiskt område inom datalogi av ACM. Kombinatoriska problem finns överallt, exempelvis att tilldela och schemalägga resurser, designa introduktioner för processorer, samt optimera instruktionsschemaläggning vid kompilering. Den här kursen lär ut de grundläggande koncepten inom villkorsprogrammering, tillämpningar, utökningar, samt dess relation till andra tekniker för kombinatorisk optimering.

  • Utbildningsnivå

    Avancerad nivå
  • Huvudområde

    Informationsteknik
  • Betygsskala

    A, B, C, D, E, FX, F

Kurstillfällen/kursomgångar

VT19 för programstuderande

VT20 för programstuderande

Lärandemål

Kursens tema är att modellera och lösa kombinatoriska (optimerings) problem med hjälp av villkorsprogrammering ("constraintprogramming"). Villkorsprogrammering har pekats ut som ett strategisktområde inom datalogi av ACM. Kombinatoriska problem finns överallt,exempelvis att tilldela och schemalägga resurser, designa intruktionerför processorer, samt optimera instruktionsschemaläggning vidkompilering. Den här kursen behandlar de grundläggande koncepten inomvillkorsprogrammering, tillämpningar, utökningar, samt dess relationtill andra tekniker för kombinatorisk optimering.  

Kursens övergripande mål är att skapa en förståelse för de grundläggande koncepten bakom villkorsprogrammering;

öva upp färdighet i att modellera och lösa kombinatoriska problem;
öva upp färdighet i att kunna uttnytja starka algoritmiska tekniker;
skapa en förståelse för för tjänster och begränsningar hos villkorsprogrammering.  

Efter kursen skall studenten kunna:  

  • förklara och använda grundläggande modelleringstekniker för villkorsproblem vilket inkluderar val av variabler, villkor, och optimeringskrtieria.
  • beskriva och använda djupet-först sökning samt "branch-and-bound" sökning för att lösa kombinatoriska problem.  
  • beskriva och förklara villkorspropagering samt förgrening och utforskning inom sökning. Bevisa korrekthet, överensstämmelse ("consistency"), och fullständighet för propagerare som implementerar villkor. Definiera och bevisa korrekthet för förgreningsstrategier. Beskriva optimeringar av villkorspropagering baserat på fixpunktsresonemang.  
  • beskriva avancerade modelleringstekniker, analysera om dessa tekniker är applicerbara på givna kombinatoriska problem. Exempel på tekniker är: generella symmetrier, värde- och   variabel-symmetrier, symmetrieliminering med villkor, symmetrieliminering under sökning, domineringsvillkor, redundanta villkor, redundant modellering och kanalisering, att använda starka algoritmiska tekniker och förgreningsheuristiker.  
  • beskriva och använda Régin's algoritm för distinct villkoret som ett exempel på stark villkorspropagering. Förklara algoritmer för element villkoret, linjära villkor, och villkor för disjunkt schemaläggning. Implementera en enkel propageringsalgoritm.
  • förklara de huvudsakliga förtjänsterna och begränsningarna med villkorsprogrammering samt hur villkorsprogrammering relaterar till andra metoder (lokalsökning och heltalsprogrammering).

Kursens huvudsakliga innehåll

Att modellera med villkorsprogrammering:

grundläggande lösningsmetoder (propagering och sökning), tekniker för modellering (implicerade villkor, symmetrireduktion), förfining av modeller, heuristiska sökmetoder, tillämpning på problem av industristorlek.

Grundläggande principer för villkorsprogrammering:

modeller för propagering och sökning samt deras väsentliga egenskaper, olika nivåer av överrensstämmelse (consistency), olika villkorsdomäner. Starka algoritmiska metoder: Régin's algoritm för distinct, edge-finding, integrering (nödvändiga egenskaper för propagering). Förhållande till andra tekniker för att lösa kombinatoriska problem (heltalsprogrammering, lokalsökning), diskussion om förtjänsteroch begränsingar, hybrid-varianter (t.ex. column generation).

Behörighet

Kurser i grundläggande datalogi, diskret matematik, algoritmer och datastrukturer. Grundläggande färdigheter i objektorienterad programmering (till exempel: i Java eller C++). 

Rekommenderade förkunskaper

Kunskaper motsvarande minst en av: SF1610 Diskret matematik, ID1015 Logik för datavetenskap, ID2213 Logikprogrammering, ID1218 Tillämpad programmering.

Litteratur

Hand outs, vetenskapliga artiklar och kurskompendium.

Examination

  • LAB1 - Laborationer, 3,0, betygsskala: P, F
  • TEN1 - Tentamen, 4,5, betygsskala: A, B, C, D, E, FX, F

Krav för slutbetyg

Godkänd skriftlig tentamina (TEN1; 4.5hp) samt godkändainlämningsuppgifter (LAB1; 3hp). 

Inlämningsuppgifterna betygsätts med P/F (godkänd eller underkänd). 

Kursen omfattar fyra inlämningsuppgifter som måste lösas och lämnas in i tid (du har en veckas tid att lösa varjeinlämningsuppgift). Varje inlämningsuppgift kommer att ha 5 poängfördelat på deluppgifter. För att bli godkänd på inlämningsuppgiftsdelen av kursen måste du få minst 10 poängtotalt på de tre inlämningsuppgifterna. Om du lämnar in en uppgift i tid så kan poängen, totalt 20 poäng,även användas som bonuspoäng till tentan. Notera: bonuspoängen är endast giltiga för innevarande läsår. 

Poängsumman på tentan är 200 poäng. Betyget för kursen bestäms av det totala antalet poäng,d.v.s. summan av tentapoäng och bonuspoäng fråninlämningsuppgifterna. Du behöver minst 100 poäng totalt för attbli godkänd på tentan. Tentan betygsätts med betygen A-F. 

Betyget för den totala poängsumman n är som följer:

n >= 180: A
180 > n >= 160: B 
160 > n >= 140: C
140 > n >= 120: D 
120 > n >= 100: E   
100 > n >= 80: Fx
80 > n       : F 

I händelse av betyg Fx så är kompletterande examination möjliginom en månad efter den ursprungliga tentan. I det fallet såkommer kursansvarige att på begäran tillhandahålla en extrainlämningsuppgift att lösas inom en veckas tid. 

Ges av

EECS/Datavetenskap

Kontaktperson

Schulte, Christian

Examinator

Christian Schulte <cschulte@kth.se>

Versionsinformation

Kursplan gäller från och med VT2019.
Examinationsinformation gäller från och med VT2019.