DM833: Approksimationsalgoritmer (5 ECTS)
STADS: 15009601Niveau
Kandidatkursus forhåndsgodkendt som PhD-kursus
Undervisningsperiode
Kurset afholdes to gange om året, én gang i efteråret og én gang i foråret.
Kurset udbydes efter behov
Ansvarlige undervisere
Email: lenem@imada.sdu.dkSkemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.
Kommentar:
Ubegrænset deltagerantal.
Indgangskrav:
Ingen
Faglige forudsætninger:
Studerende, der følger kurset, forventes at:
- Stoffet fra DM553: Kompleksitet og beregnelighed eller DM508: Algoritmer og Kompleksitet skal være kendt.
Formål
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.
Kurset giver et fagligt grundlag for at gå i dybden med et specialiseret emne indenfor området, fx i forbindelse med specialet.
Kurset giver et fagligt grundlag for at gå i dybden med et specialiseret emne indenfor området, fx i forbindelse med specialet.
Målbeskrivelse
For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evnen til at:
- 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.
- forklare begreberne pseudo-polynomiel og stærkt NP-hård og give eksempler.
- forklare begreberne PTAS, asymptotisk PTAS og FPTAS med eksempler.
- beskrive ligheder og forskelle mellem forskellige LP-teknikker.
Indhold
Kurset indeholder følgende faglige hovedområder:
- Kombinatoriske algoritmer, LP-baserede algoritmer, vertex cover, set cover, TSP, Multiway cut, k-center, knapsack, bin packing, scheduling.
- Meddeles ved kursets start.
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).
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
Undervisningsform
I introfasen introduceres og perspektiveres begreber, teorier og modeller. I træningsfasen træner de studerende færdigheder og trænger dybere ned i det stof.
I studiefasen får de studerende faglige, personlige og sociale erfaringer, der sætter dem i stand til at befæste og videreudvikle deres videnskabelige kompetencer. Der er fokus på fordybelse, forståelse og udvikling af samarbejdskompetencer.
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 1. feb 2017.
