FID3005 Villkorsprogrammering 7,5 hp

Constraint Programming

Kursomgång och genomförande

Kursomgångar saknas för tidigare och kommande terminer, samt för innevarande termin.

Kursinformation

Innehåll och lärandemål

Kursinnehåll *

Att modellera med villkorsprogrammering: grundläggande lösningsmetoder  (villkorspro­ pagering och sökning), tekniker for modellering (redundanta villkor, symmetrielimi­ nering), förfining  av modeller  med hjälp av starka  algoritmiska  metoder,  heuristiska sökmetoder,  tillämpning på problem  av industristorlek.

Grundläggande principer för villkorsprogrammering: modeller för propagering och sök­ ning samt deras väsentliga egenskaper, olika nivåer av överrensstämmelse  ("consisten­ cy"), olika villkorsdomäner.

Starka algoritmiska metoder: Regin's algoritm for distinct,  edge-finding, integrering  (nöd­vändiga egenskaper for propagering).

Förhållande till andra  tekniker för att  lösa kombinatoriska problem: heltalsprogrammering, lokalsökning;  diskussion  om  förtjänster  och  begränsningar, hybrid-varianter (t.ex. co­ lumn generation).

Forskningsöversikt: framträdande  konferenser och tidskrifter. Nuvarande trender och kopp­lingar till andra forskningsområden.

Lärandemål *

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  utnyttja  starka  algoritmiska  tekniker;  skapa en förståelse  för förtjänster  och begränsningar hos villkorsprogrammering.

Efter kursen skall studenten kunna:

• förklara  och använda grundläggande  modelleringstekniker for villkorsproblem vilket inkluderar  val av variabler, villkor, och optimeringskriterier.

• beskriva och använda djupet-först sökning samt branch-and-boundsökning för att lösa kombinatoriska problem.

• beskriva och förklara villkorspropagering samt förgrening  och utforskning inom sök­ ning. Bevisa korrekthet, överensstämmelse ("consistency"), och fullständighet  för pro­ pagerare som implementerar villkor. Definiera  och bevisa korrekthet for förgrenings­ strategier. Beskriva optimeringar av villkorspropagering baserat på fixpunkts resonemang.

• beskriva avancerade modelleringstekniker, analysera om dessa tekniker är applicerbara på givna kombinatoriska problem. Exempel på tekniker ar: generella symmetrier, varde­ och variabel-symmetrier, symmetrieliminering  med villkor, symmetrieliminering  un­ dersökning,  domineringsvillkor, redundanta  villkor, redundant  modellering och kana­ lisering, att använda starka algoritmiska  tekniker  och förgreningsheuristiker.

• beskriva och använda Regin's algoritm för distinct villkoret som ett exempel på stark villkorspropagering. Förklara algoritmer for element villkoret, linjära villkor, och vill­ kor for disjunkt schemaläggning. Implementera en enkel propageringsalgoritm.

• förklara de huvudsakliga förtjänsterna och begränsningarna  med villkorsprogramme­ ring samt hur villkorsprogrammering relaterar till andra metoder (lokalsökning och heltalsprogrammering).

Kursupplägg

Ingen information tillagd

Kurslitteratur och förberedelser

Särskild behörighet *

Ingen information tillagd

Rekommenderade förkunskaper

Ingen information tillagd

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 *

P, F

Examination *

  • EXA1 - Examination, 7,5 hp, betygsskala: P, 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.

Godkänd skriftlig tentamina,  godkända inlämningsuppgifter och godkänd tillämpning av nu­ varande forskning (till exempel: användning i en forskningsartikel, forskningsrapport, eller forskningsprojekt).

Kursen betygsatts med betygen P /F (godkänd eller underkänd).

Möjlighet till komplettering

Ingen information tillagd

Möjlighet till plussning

Ingen information tillagd

Examinator

Benoit Baudry

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

Kurswebb

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

Kurswebb FID3005

Ges av

EECS/Programvaruteknik och datorsystem

Huvudområde *

Ingen information tillagd

Utbildningsnivå *

Forskarnivå

Påbyggnad

Ingen information tillagd

Forskarkurs

Forskarkurser på EECS/Programvaruteknik och datorsystem