DM867: Kombinatorisk Optimering

Det Naturvidenskabelige Studienævn

Undervisningssprog: Dansk, men engelsk ved internationale studerende
EKA: N340014102
Censur: Ekstern prøve
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Efterår
Niveau: Kandidat

STADS ID (UVA): N340014101
ECTS-point: 10

Godkendelsesdato: 25-04-2019


Varighed: 1 semester

Version: Godkendt - aktiv

Kommentar

NYT kursus E18

Indgangskrav

Ingen

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

Se BlackBoard for pensumlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Efteråret

Udprøvninger

Mundtlig eksamen samt opgavesæt afleveret i løbet af kurset.

EKA

N340014102

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Fulde navn og SDU brugernavn

Sprog

Følger, som udgangspunkt, undervisningssprog

Hjælpemidler

Oplyses på kurset

ECTS-point

10

Uddybende information

Opgavebesvarelsen danner, sammen med udvalgte emner fra kurset, grundlag for den mundtlige eksamen. Censor vil have mulighed for at se besvarelserne af opgaverne.

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

70 timer per semester

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

Ansvarlig underviser

Navn E-mail Institut
Jørgen Bang-Jensen jbj@imada.sdu.dk

Skemaoplysninger

Administrationsenhed

Institut for Matematik og Datalogi (datalogi, fiktiv)

Anbefalede studieforløb

Profil Program Semester Periode