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.

Visa kursinformation utifrån vald termin och kursomgång:

Kursomgång och genomförande

Ingen kursomgång är vald

Välj termin och kursomgång ovan för att få information från rätt kursplan och kursomgång.

Kursinformation

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.

Kursupplägg

Ingen information tillagd

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

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 samordnare för 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

Christian Schulte

Ytterligare information

Kurswebb

Ytterligare information om kursen kan hittas på kurswebben via länken nedan. Information på kurswebben kommer framöver flyttas till denna sida.

Kurswebb ID2204

Ges av

EECS/Datavetenskap

Huvudområde *

Datalogi och datateknik, Informationsteknik

Utbildningsnivå *

Avancerad nivå

Påbyggnad

Ingen information tillagd

Kontaktperson

Schulte, Christian

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.

Övrig information

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