DM205: On-line algoritmer (5 ECTS)

STADS: 15006201

Niveau
PhD-kursus

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

Ansvarlige undervisere
Email: kslarsen@imada.sdu.dk

Yderligere undervisere
joan@imada.sdu.dk

Skemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.

Kommentar:
Ubegrænset deltagerantal. Kurset kører i 1. kvartal.
DM205 har reeksamen efter 2. kvartal.

Indgangskrav:
Ingen

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

Kursusintroduktion
En problemstilling er "on-line", hvis man skal behandle en sekvens af forespørgsler ved at træffe beslutning vedrørende hver enkelt forespørgsel uden at kende de efterfølgende. Den beslutning, man tager, kan få store konsekvenser for ens muligheder for at servicere efterfølgende forespørgsler. Eksempler på 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 vi dog primært fokusere på de mere datalogiske problemstilllinger. Formålet med kurset er at give kendskab til on-line problemstillinger og algoritmer generelt, samt de mest anvendelige problemklasser i særdeleshed. Der lægges stor vægt på analysen af kvaliteten af algoritmerne, samt designteknikker.

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

• lave competitive analyse på vilkårlige on-line algoritmer
• sammenligne to vilkårlige on-line algorithmer med relative worst order analysis
• bruge teknikker fra kurset til at designe deterministiske og randomiserede on-line algoritmer
• bevise øvre og nedre grænser på kvalitetsmål for on-line algoritmer
• tilpasse kendte on-line 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

Emneoversigt
Competitive analyse, relative worst order analyse, deterministiske og randomiserede algoritmer, øvre og nedre grænser, flere konkrete on-line problemstillinger.

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 med ekstern censur og karakter efter 7-trinsskalaen. (15006202)

Reeksamen følger reglerne i eksamensbekendtgørelsen
Tids placering for reeksamen fremgår af udbuddet

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

Forelæsninger, antal timer 21.
Eksaminatorietimer/opgaveregning, antal timer 21.
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. september 2010 til 31. januar 2017.