Modellering för kombinatorisk optimering

5 hp

Kursplan, Avancerad nivå, 1DL448

Det finns en senare version av kursplanen.
Kod
1DL448
Utbildningsnivå
Avancerad nivå
Huvudområde(n) med fördjupning
Datavetenskap A1N, Teknik A1N
Betygsskala
Med beröm godkänd, icke utan beröm godkänd, godkänd, underkänd
Fastställd av
Teknisk-naturvetenskapliga fakultetsnämnden, 9 mars 2017
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.

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.

FÖLJ UPPSALA UNIVERSITET PÅ

facebook
instagram
twitter
youtube
linkedin