DM860: Online algoritmer

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser, men engelsk ved internationale studerende
EKA: N340035102
Censur: Ekstern prøve
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Forår
Niveau: Kandidatkursus forhåndsgodkendt som Ph.d.-kursus

STADS ID (UVA): N340035101
ECTS-point: 10

Godkendelsesdato: 29-10-2018


Varighed: 1 semester

Version: Godkendt - aktiv

Kommentar

Kurser afløser den tidligere version af kurser 15019501  (tidligere UVA).

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 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.

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

Se BlackBoard for pensumlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Eksamenslement a)

Tidsmæssig placering

Juni

Udprøvninger

Mundtlig eksamen

EKA

N340035102

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Studiekort

Sprog

Følger, som udgangspunkt, undervisningssprog

Hjælpemidler

Oplyses på kurset 

ECTS-point

10

Uddybende information

Eksamen består af:



  • Et opgavesæt som skal løses selvstændigt og tæller som en del af den endelige eksamen

  • To opgavesæt som må laves i grupper på op til 3 og tæller som en del af den endelige eksamen


I eksamensterminen, hvor opgavesættene er afleveret, gives karakteren ud fra en helhedsvurdering af de tre opgavesæt samt den mundtlige eksamen. Censor vil have adgang til besvarelserne af opgaverne.

 Reeksamen er en mundtlig eksamen, der bedømmes med ekstern censur og karakter efter 7 trinsskalaen.

Vejledende antal undervisningstimer

72 timer per semester

Undervisningsform

  • Introfase (forelæsning, holdtimer) - 36 timer
  • træningsfase: 36 timer, heraf 36 eksaminatorie

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.

Aktiviteter i studiefasen 

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

Ansvarlig underviser

Navn E-mail Institut
Joan Boyar joan@imada.sdu.dk

Skemaoplysninger

Administrationsenhed

Institut for Matematik og Datalogi (datalogi, fiktiv)

Team hos Registrering & Legalitet

NAT

Anbefalede studieforløb

Profil Program Semester Periode