Midlertidig beskrivelse

Belastning

0,25 semesterenheder.

Forudsætninger

DM02, DM11. DM19 vil være en fordel.

Indhold

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.

Følgende emner vil blive berørt: "competitive" analyse, deterministiske og randomiserede algoritmer, øvre og nedre grænser, listetilgangsproblemet, "paging" problemet, k-server problemet, arbejdsfordeling.

Eksamen

Mundtlig med karakter efter 13-skalaen.

Specielle forhold

Kursus afviklingen er usædvanlig. Hele eller dele af kurset vil blive afholdt på engelsk. Der tages forbehold for delvis udestående koordination med DIKU, samt for godkendelse i studienævnet.

Mere information følger løbende.