DM865: Heuristikker og approximationsalgoritmer

Kommentar

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

Indgangskrav

Kurset kan ikke følges af studerende, der har bestået DM811, DM833 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 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

Mange optimeringsproblemer fra industrielle anvendelser som skedulering, logistik, energiplanlægning, sportsplanlægning, mm kan formuleres som diskrete optimeringsproblemer, men de kan ikke løses optimalt inden for en rimelig tid. Her spiller heuristikker, meta-heuristikker og approksimations-algoritmer en væsentlig rolle. Generelle heuristikker og metaheuristikker er løst definerede regler for at finde nær-optimale løsninger. De er ofte inspireret af naturen. For eksempel er de lokale søgeteknikker baseret på princippet om trial and error, hvilket er en mulig måde, hvorpå mennesker intuitivt løser et problem. Succesen af specifikke heuristikker til at løse konkrete problemer på en tilfredsstillende måde afhænger af indsigt i strukturen af problemet og af muligheden for en effektiv implementering. I modsætning til heuristikker har approksimations-algoritmer en garanteret køretid og løsningskvalitet. For eksempel gennemgår vi en simpel og hurtig algoritme, som garanterer at finde en TSP-tur, som er højst en halv gang længere end den optimale. I dette kursus vil vi studere heuristikker og approksimationsalgoritmer med en række konkrete NP-fuldstændige problemer som eksempel.

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

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

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

Se itslearning for pensumlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Juni

Udprøvninger

Mundtlig eksamen

EKA

N340040102

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Studiekort

Sprog

Følger, som udgangspunkt, undervisningssprog

Varighed

25 minutter

Hjælpemidler

Oplyses på kurset

ECTS-point

Uddybende information

Mundtlig eksamen på baggrund af: den teoretiske del og to praktiske projektopgaver tidligere afleveret.

Vejledende antal undervisningstimer

84 timer per semester

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 er implementering af nogle af algoritmerne gennemgået i kurset.

Ansvarlig underviser

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

Yderligere undervisere

Navn	E-mail	Institut	By
Lene Monrad Favrholdt	lenem@imada.sdu.dk	Algoritmer

Skemaoplysninger

Odense

Vis fuldt skema

Administrationsenhed

Institut for Matematik og Datalogi (datalogi)

Team hos Uddannelsesjura & Registratur

NAT

Udbudssteder

Odense

Anbefalede studieforløb

Profil	Uddannelse	Semester	Udbuds periode

Overgangsordninger

Overgangsordninger beskriver, hvordan et kursus erstatter et andet kursus, når der ændres i et studieforløb.

Hvis der er lavet en overgangsordning for et kursus vil den fremgå af oversigten.
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.