DM877: Constraint-programmering

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser
EKA: N340071102
Censur: Intern prøve, to eller flere bedømmere
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Efterår
Niveau: Kandidat

STADS ID (UVA): N340071101
ECTS-point: 5

Godkendelsesdato: 12-05-2020


Varighed: 1 semester

Version: Godkendt - aktiv

Kommentar

Kurset udbydes efter behov og udbydes ikke nødvendigvis hvert år. Eksamensforsøg for DM877 udbydes efter følgende plan, når kurset udbydes: Efterår (kursusstart september): ordinær eksamen (januar), første reeksamen (marts) og 2. reeksamen i (juni eller august).

Indgangskrav

Kurset kan ikke følges af studerende, der har bestået DM811, DM826 eller DM841.

Faglige forudsætninger

Studerende, der følger kurset, forventes at kunne:

  • anvende algoritmer og data strukturer
  • vurdere kompleksitet af algoritmer, med hensyn til såvel køretid som pladsforbrug
  • programmere

Stoffet fra DM550 Introduktion til Programmering og DM507 Algoritmer og Datastrukturer skal være kendt. 

Formål

Kurset har til formål at sætte den studerende i stand til at anvende constraint-programmering systemer, hvilket er vigtigt i forhold til at kunne løse beregningsmæssigt ikke-triviale problemer på en alligevel i praksis tit effektiv måde. Eksempler af disse problemer er diskrete optimeringsproblemer som skedulering, logistik, energiplanlægning, sportsplanlægning og ressourcallokering.  For at hjælpe at løse disse problemer, programmeringsparadigmer til generelle formål blevet udviklet. Dette kursus giver en introduktion til en af disse: Constraint-programmering.

Constraint-programmering er et programmeringssprogsparadigme, hvor variabler og betingelser mellem variabler udtrykkes i en deklarativ form. En løsning søges ved forsøgsvis at tildele en værdi valgt fra et gyldigt domæne til en variabel og derefter ved at filtrere værdier fra domænerne af de øvrige variabler, hvis disse ikke kunne være del af en løsning i følge de givet betingelser.

Man kan simpelthen ikke lære at takle de udfordringer man står over for i diskret optimering uden at forsøge at løse reelle problemer. Kurset sigter mod at give første hånds erfaring gennem programmeringsopgaver, der omfatter brug af værktøj, som illustrerer mange af de grundlæggende begreber, der er omfattet i forelæsningerne.

Kurset bygger oven på den viden, der er erhvervet i kurserne DM550 Introduktion til Programmering og DM507 Algoritmer og datastrukturer. Kurset giver et fagligt grundlag for at lave et speciale, hvor algoritmer til diskret optimering skal designes, analyseres og implementeres.

I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at:

  • Give kompetence til at planlægge og udføre videnskabelige projekter på højt fagligt niveau herunder styre arbejds- og udviklingssituationer, der er komplekse, uforudsigelige og forudsætter nye løsningsmodeller
  • Give færdigheder i at beskrive, analysere og løse avancerede datalogiske problemstillinger ved hjælp af de lærte modeller
  • Give færdigheder i at analysere fordele og ulemper ved forskellige algoritmer, specielt med hensyn til ressourceforbrug
  • Give færdigheder i at belyse fremsatte hypoteser på kvalificeret teoretisk baggrund og forholde sig kritisk til egne og andres forskningsresultater og videnskabelige modeller
  • Give færdigheder i at udvikle nye varianter af de lærte metoder, hvor det konkrete problem kræver det
  • Give færdigheder i at formidle gennem en skriftlig rapport forskningsbaseret viden og diskutere professionelle og videnskabelige problemstillinger med fagfæller
  • Give ekspertviden om diskret optimering og løsning metoder fra fagets internationale forskningsfront

Målbeskrivelse

For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evne til at:            

  • modellere et problem der i natur minder om dem, der ses i kurset, inden for rammerne af constraint-programmering
  • argumentere vedrørende de forskellige modellerings valg med hensyn til teorien bag komponenterne af constraint-programmering, herunder globale betingelser, propagators, søgning og forgreningsordninger.
  • udvikle en løsningsprototype ved hjælp af et constraint-programmeringssystem
  • foretage en eksperimentel analyse, rapportere resultaterne og drage fornuftige konklusioner ud fra disse.
  • beskrive det udførte arbejde i et passende sprog.

Indhold

Kurset indeholder følgende faglige hovedområder: 

  • constraint-tilfredshedmodel
  • lokal konsistens og propagation
  • globale betingelser
  • søgning og træ-baserede søgeheuristikker
  • symmetribrud
  • tilfældig genstart strategi og stor skala nabolag
  • Constraint-programmeringssystemer
  • anvendelser: puslespil, kombinatorisk design, ruteplanlægning, skemalægning.

Litteratur

Se itslearning for pensumlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Efterår

Udprøvninger

Obligatoriske opgaver

EKA

N340071102

Censur

Intern prøve, to eller flere bedømmere

Bedømmelse

7-trinsskala

Identifikation

Fulde navn og SDU brugernavn

Sprog

Følger, som udgangspunkt, undervisningssprog

Hjælpemidler

Oplyses på kurset.

ECTS-point

5

Vejledende antal undervisningstimer

44 timer per semester

Undervisningsform

På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

  • Introfase 26 timer 
  • Træningsfase 18 timer 

Aktiviteter i studiefasen bastår i:

  • Løsning af ugentlige opgaver med henblik på diskussion af disse ved eksaminatorierne
  • Løsning af projektopgaverne
  • Selvstudium af visse emner fra lærebogen
  • Selvstændig opsamling på intro og træningsfasen

Ansvarlig underviser

Navn E-mail Institut
Marco Chiarandini marco@imada.sdu.dk Algoritmer

Skemaoplysninger

Administrationsenhed

Institut for Matematik og Datalogi (datalogi)

Team hos Uddannelsesjura & Registratur

NAT

Udbudssteder

Odense

Anbefalede studieforløb

Profil Uddannelse Semester Udbuds periode