Nye algoritmer og nye bredde-parameteriseringer

Hver dag brukes datamaskiner til å løse tusenvis av oppgaver i hverdagen vår. Vi vil gjerne at dette skal gjøres ved hjelp av raske algoritmer. Om man ser på et dataprogram som utfører noe så enkelt som å telle antall ord i et tekstdokument, kan man forvente at det vil ta omtrent dobbelt så lang tid å utføre oppgaven dersom dokumentet er dobbelt så langt. Dette ansees som raskt. Selv for et dokument på flere millioner ord vil man da ikke måtte vente lenge på svaret.

I eksempelet over er tekstdokumentet såkalt input til dataprogrammet og vi uttrykker (kjøre-)tiden det tar å løse problemet ved hjelp av lengden av input. For mer kompliserte problemer er dessverre de kjappeste kjøretider veldig trege uttrykt kun med lengden av input. Et vanlig eksempel er at tiden det tar å løse problemet i verste fall er dobbelt så lang når lengden på input øker minimalt - for eksempel med ett ord i et tekstdokument. Da vil programmet bruke 1000 ganger så lang tid på et dokument med 70 ord enn på et med 60 ord og på et dokument med 90 ord brukes over en million ganger så lang tid som på et med 70 ord. Men selv for slike problemer vil man ofte i praksis bruke mindre tid, siden andre egenskaper enn lengden på input påvirker kjøretiden. For eksempel kan det tenkes at oppgaven løses hurtigere dersom ordene i dokumentet er veldig korte, eller dersom kun få unike ord er brukt. Innenfor parameterisert kompleksitetsteori ser man på kjøretider uttrykt med annet enn bare lengden på input, slik at man får en mer korrekt analyse av kjøretiden på å løse et problem, dersom det er andre faktorer enn lengden på input som avgjør tidsbruken.

I sin avhandling studerer Sigve Hortemo Søther nye parametere for å bedre kunne uttrykke kjøretiden til en rekke problemer. Mange problemer modelleres ved hjelp av grafer, og blant de mest kjente graf-parametre finner vi tre-bredde og klikk-bredde. I avhandlingen introduseres et alternativ kalt split-matching-bredde som forener mange av de beste egenskapene ved disse to graf-parametrene.

Personalia:

Sigve Hortemo Sæther er født i 1987 og vokste opp i Arendal. Han fullførte sin bachelorgrad i informatikk i 2009 og tok mastergraden i informatikk i 2011, begge på Universitetet i Bergen. Han har vært ansatt som stipendiat i algoritmegruppen ved Universitetet i Bergen siden høsten 2011 og har hatt Prof. Jan Arne Telle fra institutt for informatikk som sin hovedveileder.