Online-algoritmer

Online-algoritmer

v/ Lene Monrad Favrholdt, PhD, Lektor, SDU

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.

BEMÆRK: Aktiviteten afvikles i samarbejde med UNF, hvorfor også andre end ATU'ere kan deltage

PRAKTIK: Der er ingen spisepause eller forplejning til denne aktivitet.

FIND VEJ: Du finder lokalet U46 på SDU's hovedgang Gydehutten, her! 

AFVIKLER:  Der er ingen afvikler fra ATU til stede til denne aktivitet, og du skal derfor fjernregistrere dig som deltager. Du fjernregistrerer dig ved at sende en e-mail til christian@atusyd.dk på dagen, når aktiviteten starter. Forsinkelser og afbud på dagen meldes også til Christian.