DM860: Online algoritmer (10 ECTS)

STADS: 15019501

Niveau
Kandidatkursus forhåndsgodkendt som PhD-kursus

Undervisningsperiode
Kurset er placeret i forårssemesteret.

Ansvarlige undervisere
Email: joan@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal.

Indgangskrav:
Bestået bachelorgrad i datalogi, matematik, anvendt matematik, matematik-økonomi eller tilsvarende.

Faglige forudsætninger:
Studerende, der følger kurset, forventes at:

• Kunne anvende grundlæggende sandsynlighedsteori og analysere algoritmer

Formål
Kurset har til formål at sætte den studerende i stand til at forstå de gundlæggende begreber i online problemstillinger og algoritmer, især design- og analyseteknikker for online algoritmer.

Formålet med kurset er at studere online problemer og algoritmer. Et problem er online, hvis man skal behandle en sekvens af forespørgsler ved at træffe beslutning om hver eneste forespørgsel uden at kende de efterfølgende. Eksempler på online problemstillinger, der kan have denne natur, er pakning af containere, investeringer på børsen, fordeling af job til forskellige processorer, paging/buffer problemer, reorganisering af symboltabeller, reservation af båndbredde i et netværk og reservation af sæder i et tog. I kurset vil der blive lagt stor vægt på analysen af kvaliteten af algoritmerne, samt designteknikker.

Kurset bygger oven på den viden, der er erhvervet i kurserne DM549 Diskrete Metoder til Datalogi eller MM537 Introduktion til Matematiske Metoder, DM551 Algoritmer og Sandsynlighed eller MM541 Kombinatorisk Matematik, DM507 Algoritmer og Datastrukturer, og DM553 Kompleksitet og Beregnelighed.. 

Kurset giver et fagligt grundlag for at lave et speciale indenfor online algoritmer. 

I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at:

• Beskrive, analysere og løse avancerede problemstillinger i online algoritmer ved hjælp af de lærte modeller 
• Analysere fordele og ulemper ved forskellige kvalitetsmål 
• Kunne forstå og på et videnskabeligt grundlag reflektere over principper og grundlæggende egenskaber omkring online problemer og algoritmer
• Give ekspertviden om online algoritmer, der er baseret på den højeste internationale forskning 
• Give viden om et udvalg af specialiserede modeller og metoder udviklet inden for online algoritmer baseret på højeste internationale forskning, herunder emner fra fagets forskningsfront
• Udvikle nye varianter af de lærte metoder, hvor det konkrete problem kræver det

 

Målbeskrivelse
For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evnen til at:

• Lave competitive analyse på vilkårlige online algoritmer
• Sammenligne to vilkårlige online algorithmer med relative worst order analyse
• Bruge teknikker fra kurset til at designe og analysere deterministiske og randomiserede online algoritmer, samt online algoritmer med ”advice”.
• Bevise øvre og nedre grænser mht. specifikke kvalitetsmål for online algoritmer
• Tilpasse kendte online algoritmer til specialtilfælde af kendte problemer og til nye problemer 
• Designe og analysere nye on-line algoritmer til at løse problemer, som i natur minder om problemer fra kurset

Indhold
Kurset indeholder følgende faglige hovedområder:

• Competitive analyse
• Andre kvalitetsmål, herunder relative worst order analyse
• Deterministiske og randomiserede algoritmer, samt online algoritmer med ”advice”
• Øvre og nedre grænser
• Flere konkrete online problemstillinger, herunder paging og list accessing

Litteratur

Meddeles ved kursets start.

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

Forudsætningsprøver

1. Projektopgaver, som er en forudsætning for deltagelse i eksamenselement a). Bestået/ikke-bestået, intern censur ved underviser. (15019512).

    

Eksamen- og censurform:

1. Mundtlig eksamen. (10 ECTS). Bedømmes med ekstern censur og karakter efter 7-trinsskalaen. (15019502).

    

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 36 timer
Træningsfase: 36 timer, heraf:
 - Eksaminatorie: 36 timer

Aktiviteter i studiefasen

1. Anvendelse af den tilegnede viden i projekter.
2. Sammenfatning af videnskabelige artikler/bogkapitler.

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.

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 2017 til 31. januar 2019.