ID2204 Villkorsprogrammering 7,5 hp

Utbildningsnivå	Avancerad nivå	Kursnivå (A-D)	D
Huvudområde	Informationsteknik	Betygsskala	A, B, C, D, E, FX, F

• Kurshemsida

• Kurssida på KTH Social

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 degrundläggande koncepten bakom villkorsprogrammering;
öva upp färdigheti att modellera och lösa kombinatoriska problem;
öva upp färdighet iatt kunna uttnytja starka algoritmiska tekniker;
skapa enförståelse för förtjänster och begränsningar hosvillkorsprogrammering.  

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 hp, betygsskala: P, F
• TEN1 - Tentamen, 4,5 hp, 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 tre inlämningsuppgifter som måste lösas ochlä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 ärendast 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

ICT/Programvaru- och datorsystem

Kontaktperson

Schulte, Christian

Examinator

Christian Schulte <cschulte@kth.se>

Versionsinformation

Kursplan giltig från och med HT08.
Examinationsinformation giltig från och med HT07.