DM865: Heuristikker og approximationsalgoritmer
Kommentar
Indgangskrav
Faglige forudsætninger
- anvende algoritmer og data strukturer
- vurdere kompleksitet af algoritmer, med hensyn til såvel køretid som pladsforbrug
- programmere
Stoffet fra DM507 Algoritmer og Datastrukturer og DM550 Introduktion til Programmering skal være kendt. Det er en fordel at kende stoffet fra DM553 Kompleksitet og beregnelighed eller DM508 Algoritmer og Kompleksitet og stoffet fra DM559 Lineær og heltals-programmering.
Formål
Kurset bygger oven på den viden, der er erhvervet i kurserne DM550 Introduktion til Programmering og DM507 Algoritmer og datastrukturer. Referencer til koncepter fra DM554 Lineær og heltalsprogrammering samt DM553 Kompleksitet og beregnelighed eller DM508 Algoritmer og Kompleksitet kan finde sted i kursusforløbet. 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
- designe specialiserede versioner af generelle heuristikker, greedy og lokal søgning og metaheuristikker for problemer, der i natur minder om dem, der ses i kurset.
- udvikle en løsningsprototype baseret på lokal-søgning og metaheuristikker.
- foretage en eksperimentel analyse, rapportere resultaterne og drage fornuftige konklusioner ud fra disse.
- beskrive det udførte arbejde i et passende sprog, evt. med brug af pseudokode.
- give et overblik over de problemer og teknikker, vi har studeret i kurset
- give en præcis beskrivelse og analyse af hver af de algoritmer, vi har studeret i kurset.
Indhold
Kurset indeholder følgende teknikker:
- Kombinatoriske algoritmer
- LP-baserede algoritmer
- grådige algoritmer
- (stokastiske) lokal-søgnings-algoritmer
- meta-heuristikker
Teknikkerne anvendes bl.a. på følgende konkrete problemer:
- set cover
- traveling salesman
- satisfiability, scheduling
- bin-packing, knapsack
Litteratur
Eksamensbestemmelser
Eksamenselement a)
Tidsmæssig placering
Udprøvninger
Mundtlig eksamen
EKA
Censur
Bedømmelse
Identifikation
Sprog
Hjælpemidler
ECTS-point
Uddybende information
Mundtlig eksamen på baggrund af: den teoretiske del og to praktiske projektopgaver tidligere afleveret.
Eksamensformen ved reeksamen kan være en anden end eksamensformen ved den ordinære eksamen.
Vejledende antal undervisningstimer
Undervisningsform
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 42 timer
Træningsfase: 42 timer, heraf:
- Eksaminatorie: 42 timer
Der vil være forelæsninger, opgave-regning og programmering. I forelæsningerne gennemgås teorien, delvis via dialog med de studerende. Gennem opgave-regning udvikles bedre forståelse af teorien, og gennem implementering gives erfaring med udfordringerne i og fordelene ved de forskellige teknikker og algoritme-typer.
Aktiviteter i studiefasen
- Implementering af nogle af algoritmerne gennemgået i kurset.