Modellering för kombinatorisk optimering

5 hp

Kursplan, Avancerad nivå, 1DL448

Kod
1DL448
Utbildningsnivå
Avancerad nivå
Huvudområde(n) med fördjupning
Datavetenskap A1N, Teknik A1N
Betygsskala
Underkänd (U), godkänd (3), icke utan beröm godkänd (4), med beröm godkänd (5)
Fastställd av
Teknisk-naturvetenskapliga fakultetsnämnden, 30 augusti 2018
Ansvarig institution
Institutionen för informationsteknologi

Behörighetskrav

120 hp inklusive Baskurs i matematik, Algebra I samt en fortsättningskurs i programmering eller annan kurskombination innehållande grundläggande koncept i algebra, kombinatorik, logik, graf- och mängdteori samt implementering av enkla sökalgoritmer. Engelska 6. (Med en svensk kandidatexamen uppfylls kravet på engelska.)

Mål

Efter godkänd kurs ska studenten kunna:

  • modellera ett kombinatoriskt problem i ett lösar-oberoende villkorsmodelleringsspråk
  • jämföra och utvärdera modeller av kombinatoriska problem uttryckta i villkorsmodelleringsspråk
  • beskriva och jämföra olika villkorslösningstekniker som kan användas av lösare till ett villkorsmodelleringsspråk, t.ex. villkorsprogrammering, lokal sökning, Boolesk satisfierbarhet och heltalsprogrammering
  • välja en lämplig villkorslösningsteknik att prova för ett nytt kombinatoriskt problem och motivera valet
  • designa och utvärdera olika modeller av kombinatoriska problem för olika villkorslösningstekniker.

Innehåll

Kursens fokus ligger på modellering av optimeringsproblem. Modellerna kan sedan användas för att lösa problemen med färdig lösare. Verktyg för att lösa svåra kombinatoriska optimeringsproblem genom att först modellera dem i ett lösaroberoende villkorsmodelleringsspråk för att sedan lösa dem med hjälp av en färdig lösare. Kombinatoriska (satisfierbarhets- eller optimerings-) problem, villkorsmodelleingsspråk, huvuddrag hos olika villkorslösningstekniker, heuristiker och "good practice" i modellering och lösning av kombinatoriska problem, exempel på tillämpningar av kombinatorisk problemlösning.

Undervisning

Föreläsningar, lektioner och handledning.

Examination

Muntlig och skriftlig redovisning av uppgifter.

Om särskilda skäl finns får examinator göra undantag från det angivna examinationssättet och medge att en enskild student examineras på annat sätt. Särskilda skäl kan t.ex. vara besked om särskilt pedagogiskt stöd från universitetets samordnare för studenter med funktionsnedsättning.

FÖLJ UPPSALA UNIVERSITET PÅ

facebook
instagram
twitter
youtube
linkedin