DM833: Approksimationsalgoritmer (5 ECTS)

STADS: 15009601

Niveau
Kandidatkursus

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

Ansvarlige undervisere
Email: lenem@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal. 4. kvartal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra DM508: Algoritmer og Kompleksitet skal være kendt.

Kursusintroduktion
Mange vigtige optimeringsproblemer kan ikke løses optimalt inden for en rimelig tid, og her spiller approksimations-algoritmer en væsentlig rolle. I modsætning til heuristikker har approksimations-algoritmer en garanteret køretid og løsningskvalitet. Et simpelt eksempel er den grådige algoritme, som leverer et vertex cover med højst dobbelt så mange knuder som i et optimalt vertex cover. I dette kursus vil vi studere approksimationsalgoritmer med en række konkrete NP-fuldstændige problemer som eksempel.

Forventet læringsudbytte
Efter kurset forventes den studerende at kunne
- give et overblik over de problemer og teknikker, vi har studeret i kurset.
- give en præcis definition af hvert af de kombinatoriske problemer, vi har studeret i kurset.
- give en præcis beskrivelse og analyse af hver af de algoritmer, vi har studeret i kurset.

Emneoversigt
Kombinatoriske algoritmer, LP-baserede algoritmer, vertex cover, set cover, TSP, Multiway cut, k-center, knapsack, bin packing, scheduling.

Litteratur
Der er i øjeblikket ikke angivet nogle materialer for kurset.

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

Forudsætningsprøver
Ingen

Eksamen- og censurform:
Mundtlig eksamen. Bedømmelse efter 7-trinsskalaen, ekstern censur (5 ECTS). (15009602)

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 22 timer
Træningsfase: 20 timer, heraf:
 - Eksaminatorie: 20 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.

Denne kursusbeskrivelse var gyldig fra 1. februar 2013 til 31. januar 2017.