Hoppa till huvudinnehållet

ID2204 Villkorsprogrammering 7,5 hp

Kursomgångar saknas för aktuella eller kommande terminer.
Rubriker med innehåll från kursplan ID2204 (VT 2020–) är markerade med en asterisk ( )

Innehåll och lärandemål

Kursinnehåll

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

  • Att modellera med villkorsprogrammering.
  • Grundläggande lösningsmetoder: propagering och sökning.
  • Tekniker för modellering, 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 propagering; olika villkorsdomäner; starka algoritmiska metoder för propagering.
  • Förhållande till andra tekniker för att lösa kombinatoriska problem (heltalsprogrammering, lokalsökning), diskussion om förtjänster och begränsingar, hybridvarianter.

Lärandemål

Efter godkänd kurs ska studenten kunna 

  • använda tekniker för att modellera och lösa villkorsproblem
  • förklara de principer som ligger till grund för tekniker för att lösa villkorsproblem
  • förklara de huvudsakliga förtjänsterna och begränsningarna med villkorsprogrammering samt hur villkorsprogrammering relaterar till andra metoder.

Kurslitteratur och förberedelser

Särskild 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.

Utrustning

Ingen information tillagd

Kurslitteratur

Ingen information tillagd

Examination och slutförande

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

Betygsskala

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

Examination

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

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

Möjlighet till komplettering

Ingen information tillagd

Möjlighet till plussning

Ingen information tillagd

Examinator

Etiskt förhållningssätt

  • Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
  • Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
  • Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.

Ytterligare information

Kursrum i Canvas

Registrerade studenter hittar information för genomförande av kursen i kursrummet i Canvas. En länk till kursrummet finns under fliken Studier i Personliga menyn vid kursstart.

Ges av

Huvudområde

Datalogi och datateknik, Informationsteknik

Utbildningsnivå

Avancerad nivå

Påbyggnad

Ingen information tillagd

Kontaktperson

Thomas Sjöland (sjoland@kth.se)

Övrig information

Obs. Kursen är inställd fr.om. VT20

I denna kurs tillämpas EECS hederskodex, se: http://www.kth.se/eecs/utbildning/hederskodex.