FID3005 Villkorsprogrammering 7,5 hp

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.

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).

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

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

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).

Benoit Baudry

• 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.