DM867: Kombinatorisk Optimering

Ingen

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/MM850.
  
• Kendskab til lineær programmering og basal teori for strømning i netværk (f.eks fra DM551/MM851 eller DM817) er en fordel men ikke en forudsætning, da de nødvendige ting introduceres i kurset.
  

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, DM551/MM851 og DM553/MM850.
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.

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.

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.
• Orienteringer af grafer.
• Heltals programmering.
• Approksimationsalgoritmer.
• Flervarestrømninger og disjunkte veje.
• Træ-dekomponeringer af grafer og  algoritmiske anvendelser af sådanne.
• Parametericeret kompleksitet.
• NP-kompletheds beviser.
• Grafer uden inducerede kredse af længde mere end 3.

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

• Introfase (forelæsning, holdtimer) - Antal timer: 35
  
• 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