DM209: Kombinatorisk optimering II (5 ECTS)

STADS: 15007801

Niveau
PhD-kursus

Undervisningsperiode
Kurset er placeret i efterårssemesteret.
Kurset udbydes efter behov.

Ansvarlige undervisere
Email: jbj@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal. 3. kvartal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Bachelorgrad i datalogi eller matematik. Stoffet fra DM508 Algoritmer og kompleksitet og DM515 Introduktion til lineær og heltalsprogrammering forudsættes kendt.

Kursusintroduktion
Formålet med dette kursus og dets forgænger Kombinatorisk optimering I er at bibringe de studerende et indgående kendskab til emner indenfor kombinatorisk optimering. Flere af de metoder som behandles har stor praktisk anvendelighed. Disse sammenhænge vil blive belyst grundigt i kurserne.

Forventet læringsudbytte
Ved kursets afslutning forventes den studerende at kunne:

• anvende teorien og algoritmerne fra kurset på konkrete probleminstanser.
• redegøre for beviser indenfor kursets pensum.
• redegøre for de i kurset gennemgåede algoritmer og for deres kompleksiteter.
• anvende metoder, modeller og algoritmiske ideer fra kurset i nye problemsammenhænge, der i natur ligner de i kurset behandlede emner.

Emneoversigt
Heltallighed af polyedre, Approksimationsalgoritmer, Fixed parameter algoritmer, Lagrange relaxation, multicommodity flows og disjunkte veje i grafer, netværkdesign, , træ-dekomponeringer og anvendelser af sådanne, NP-komplethed, chordal graphs.

Litteratur

• Meddeles ved kursets start.

Pensum
Se pensumbeskrivelse.

Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Ingen

Eksamen- og censurform:
Mundtlig eksamen der bedømmes efter 7-trinsskalaen ved ekstern censur. (15007802)

Reeksamen følger reglerne vedtaget i studienævnet.
Reeksamen kan have en anden form end den ordinære eksamen.

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

Forelæsninger, 22 timer
Eksaminatorietimer, 14 timer
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på dansk eller engelsk, afhængigt af underviseren. Dog altid på Engelsk ved deltagelse af internationale studerende.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Dette er den nyeste version af en kursusbeskrivelse, som trådte i kraft den 2. jan 2012.