På jakt etter struktur

Algoritmer er et svært viktig fagfelt innen naturvitenskapen, matematikken og informasjonsvitenskapen og har de ti siste årene spilt en kritisk rolle innenfor samfunnet som helhet. Algoritmer påvirker i stadig større grad hvordan samfunnet utvikler seg, hvordan vi som mennesker kommuniserer med hverandre og oppfatter verden rundt oss. Uheldigvis er det slik at de aller fleste interessante problemene innenfor informatikk ikke lar seg løse generelt av noen algoritme, dersom man ønsker å få et svar i løpet av sin egen levetid.

Et spørsmål som da kommer opp er om det virkelig er nødvendig å løse disse problemene generelt, eller om man kan forvente at de instansene som vi er interessert i har struktur som kan utnyttes. Det viser seg at ofte er nettopp dette tilfelle. De fleste nettverk man jobber med, som veinett og stømnett, biologiske data eller mer abstrakt data som sosiale nettverk eller aktivitet på internett, innehar slik struktur man kan utnytte.

Dregi har i sitt doktorgradsarbeid utviklet nye og raskere algoritmer for å oppdage og representere slik struktur i data som omgir oss. Han har blant annet utviklet algoritmer for trebredde, den viktigste og mest studerte strukturen av denne typen. Videre har han jobbet med hvordan man kan utnytte denne typen strukturer til å gjøre algoritmer raskere. I lys av dette har han utviklet metoder for å preprossesere data, gi tilnærmede svar hvor det å løse problemet optimalt ikke er mulig og han har utviklet raskere eksakte algoritmer. Ved hjelp av lignende metoder har han også jobbet med å identifisere hirarkier i sosiale nettverk.

Personalia:

Markus Fanebust Dregi er født i 1988 og oppvokst i Bergen. Han har en bachelor i Matematikk, Informatikk og Teknologi fra Universitetet i Oslo og en master i Informatikk fra Universitetet i Bergen. Doktorgradsarbeidet har vært utført i tilknytning til prosjektet "Beating Hardness by Preprocessing" finansiert av Bergen Forskningsstiftelse og har vært veiledet av Professor Daniel Lokshtanov.