DM867: Kombinatorisk Optimering
Kommentar
Indgangskrav
Faglige forudsætninger
Studerende, der følger kurset, forventes at:
- Have kendskab til basale datastrukturer og grafalgoritmer, som dem der undervises i DM507.
- Have kendskab til problemkompleksitet, herunder klasserne P og NP, samt basale approksimationsalgoritmer svarende til de emner der dækkes i DM553.
- Kendskab til lineær programmering og basal teori for strømning i netværk (f.eks fra DM817) er en fordel men ikke en forudsætning, da de nødvendige ting introduceres i kurset.
Formål
Kurset har til formål at sætte den studerende i stand til at:
- Anvende teori og metoder fra kombinatorisk optimering til at resonere om problemer af kombinatorisk natur.
- Udvikle effektive algoritmer til løsning af praktiske problemer som i natur ligner dem der behandles i kurset.
- Kunne argumentere for at et kombinatorisk optimeringsproblem er NP-hårdt og foreslå metoder til at opnå approksimative løsninger ved hjælp af de metoder man lærer i kurset.
- Udvikle ny teori og metoder for kombinatoriske optimeringsproblemer som er beslægtede med dem man møder i kurset.
Kurset bygger oven på den viden, der er erhvervet i kurserne DM507 og DM553.
Kurset giver et fagligt grundlag for at lave et speciale inden for kombinatorisk optimering, herunder grafalgoritmer.
I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at den studerende skal:
- Kunne analysere og løse avancerede problemstillinger indenfor kombinatorisk optimering ved hjælp af de lærte metoder
- Kunne løse praktiske optimeringsproblemer ved hjælp af de lærte metoder
- Kunne udvikle nye varianter af de lærte metoder med henblik på anvendelse af disse på nye problemtyper.
Målbeskrivelse
For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evnen til at:
- Kunne anvende teorien fra kurset som et redskab til at løse problemer som i natur ligner dem fra kurset.
- Kunne anvende algoritmer fra kurset som delkomponenter i mere komplekse algoritmer.
- Kunne anvende teori og algoritmer fra kurset til at løse praktiske optimeringsproblemer.
- Kunne identificere, samt argumentere om, kombinatoriske optimeringsproblemer ud fra en beskrivelse af sådanne i ord.
- Kunne vurdere om et givet kombinatorisk optimeringsproblem, som i natur ligner dem fra kurset, kan løses effektivt eller om det er NP-hårdt.
- Kunne anvende algoritmiske metoder som baserer sig på trædekomponeringer af grafer.
Indhold
Kurset indeholder følgende faglige hovedområder:
- Pardannelser i grafer og generalisationer af disse.
- Matroider og disses anvendelse i kombinatorisk optimering.
- Branchings i digrafer.
- Grafsammenhæng.
- Heltals programmering.
- Approksimationsalgoritmer.
- Flervarestrømninger og disjunkte veje.
- Trædekomponeringer af grafer med algoritmiske anvendelser.
- Parametericeret kompleksitet.
- NP-kompletheds beviser.
- Grafer uden inducerede kredse af længde mere end 3.
Litteratur
Eksamensbestemmelser
Eksamenselement a)
Tidsmæssig placering
Udprøvninger
Mundtlig eksamen samt opgavesæt afleveret i løbet af kurset.
EKA
Censur
Bedømmelse
Identifikation
Sprog
Hjælpemidler
ECTS-point
Uddybende information
Reeksamen i samme eksamenstermin eller i umiddelbar forlængelse heraf. Reeksamen er en mundtlig eksamen, der bedømmes med karakter efter 7-skalaen og ekstern censur.
Vejledende antal undervisningstimer
Undervisningsform
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
- Introfase (forelæsning, holdtimer) - Antal timer: 40
- træningsfase: Antal timer: 30
Introfasen består af forelæsninger ved underviser. Her gennemgås teori og metoder og disse illustreres med eksempler. Introfasen suppleres af træningsfasen, hvor de studerende ugentligt arbejder med nye opgaver, der belyser de emner som aktuelt studeres. Endeligt består studiefasen af yderligere selvstændig læsning af og reflektion over kursus materialerne, samt løsning af de 2 projektopgaver som udgør kursets evaluering.
Aktiviterter i studiefasen:
- 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