DM205: On-line algoritmer (5 ECTS)

STADS: 15006201

Niveau
PhD-kursus

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

Ansvarlige undervisere
Joan Boyar, Professor, Ph.d.
Tlf.: 6550 2338 Email: joan@imada.sdu.dk

Skemaoplysninger
Hold Type Dag Tidsrum Lokale Uger Kommentar
Fælles I Mandag 14-16 IMADA Seminarrum 06-13
Fælles I Onsdag 14-16 IMADA Seminarrum 06-13
Fælles I Torsdag 08-10 IMADA Seminarrum 06-13
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal. 3. + 4.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


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

Eksamensdato
Den ordinære eksamen finder sted den 31. March 2014
Reeksamen finder sted den 22. August 2014

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 og eksamenstilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. September 2010 til 31. January 2017.