Online-algoritmer

Algoritmer er alle steder. Nu om dage er der computere involveret i næsten alt, hvad vi foretager os, og de bruger algoritmer for at vide, hvad de skal gøre. En algoritme er en opskrift på, hvordan man løser et givet problem eller udfører en bestemt opgave. Når man bruger ordet algoritme, tænker man som regel, at det i sidste ende er en computer, der skal udføre opgaven, men en mad- eller strikke-opskrift er i princippet også en algoritme.

Et godt eksempel er en algoritme til at fordele passagerer i et tog. Når man bestiller pladsbillet hos DSB, får man med det samme at vide, hvor i toget man skal sidde. Som regel betyder det, at færre passagerer kan få en pladsbillet, end hvis pladserne først blev fordelt lige før afgang. Hvordan kan det nu være, tænker du? Lad os se på et eksempel: Forestil dig et meget lille tog, som kun har to pladser. Hvis de to første reservationer er til strækningerne Ålborg-Århus og Odense-København, kan systemet give de to passagerer samme plads i toget, hvilket vil være godt, hvis der senere kommer en reservation til hele strækningen Ålborg-København. Men det kunne jo også være, at der i stedet for en reservation til strækningen Ålborg-København kommer reservationer til strækningerne Ålborg-Odense og Århus-København. I det tilfælde ville det have været bedre at placere de to første passagerer på hver sin plads! Og problemet bliver selvfølgelig ikke nemmere, når toget har mere end to pladser...

Problemer som pladsreservations-problemet, hvor man er nødt til at tage beslutninger her og nu uden at kende fremtidige behov, kaldes online-problemer, og de tilhørende algoritmer kaldes online-algoritmer.

Der kan være brug for online-algoritmer i mange forskellige situationer: når et program skal beslutte, hvilke hukommelses-sider der skal være i den hurtige hukommelse, når jobs skal fordeles på servere, så serverne belastes nogenlunde jævnt, når man skal beslutte, om man skal købe eller leje ski, osv.

Hvordan designer man algoritmer, som garderer sig rimeligt mod en ukendt fremtid? Har online-algoritmen overhovedet en chance for at løse opgaven nogenlunde godt? Og hvordan måler vi dette? Det ser vi nærmere på i dette foredrag.