DM860: Online algoritmer

Kurset udbydes efter behov og udbydes ikke nødvendigvis hvert år. Eksamensforsøg for DM860 udbydes efter følgende plan, når kurset udbydes: Ordinær eksamen (januar), første reeksamen (marts) og 2. reeksamen i (juni eller august).

Studerende, der følger kurset, forventes at kunne anvende grundlæggende sandsynlighedsteori og analysere algoritmer.

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. 

Kurset har til formål at sætte den studerende i stand til at forstå de grundlæ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.

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

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

Skemalagte undervisningstimer: 

Antal undervisningstimer i alt: 72

Heraf: 

Fællestimer i klasselokale/auditorium: 72  

I forelæsning introduceres og perspektiveres begreber, teorier og modeller. I øvelsestimer træner de studerende færdigheder og trænger dybere ned i det stof.

Andre planlagte undervisningsaktiviteter:  

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