Universitetet i Bergen : Doktorgrader : 2009

NY DOKTORGRAD

Opportunistiske algoritmer

Daniel Lokshtanov   
Daniel Lokshtanov disputerer mandag 22. juni 2009 for PhD-graden ved Universitetet i Bergen med avhandlingen:

“New Methods in Parameterized Algorithms and Complexity”

Veldig mange av beregningsproblemene som dukker opp i praksis har ikke latt seg løse effektivt på en datamaskin, og det er konsensus blant de fleste eksperter på feltet at en stor klasse av disse problemene neppe noen gang vil få en effektiv løsning. Siden vi likevel trenger å håndtere problemene som dukker opp, må vi enten nøye oss med dataprogrammer som finner løsninger som ikke nødvendigvis er optimale, eller ty til programmer som på noen datasett krever ekstremt mye tid og dataressurser.

I denne avhandlingen studeres dataprogrammer, eller algoritmer som i verste fall vil bruke årevis, selv på små datasett, men som løser problemet effektivt dersom det lar seg gjøre. Mer konkret leter algoritmen etter struktur og smutthull i datasettet, og dersom algoritmen finner denne strukturen kan datasettet løses raskt. På denne måten er algoritmen opportunistisk – dersom en mulighet for å løse problemet raskt byr seg vil algoritmen ta den. Flere metoder blir studert, og nye metoder blir utviklet for å finne struktur, for å utnytte den, og også for å bevise at en konkret type struktur ikke lar seg utnytte med mindre så å si alle tenkelige problemer kan løses effektivt.

Metodene blir anvendt på en lang rekke problemer, blant annet på aggregering av søkeinformasjon. Dersom man leter etter noe på ulike søkemotorer vil de forskjellige søkemotorene som oftest gi ulikt resultat, og også rangere de samme treffene ulikt. Man ønsker å lage en enkelt liste som stemmer godt overens med resultatene fra alle søkemotorene. Et overraskende resultat oppnådd i avhandlingen er at dersom man fargelegger søkeresultatene med tilfeldig valgte farger, vil denne fargeleggingen med høy sannsynlighet være veldig nyttig for å finne en liste som stemmer overens med de gitte rangeringene. Denne tilnærmingen gir den hittil raskeste algoritmen for dette problemet, og viser seg å være nyttig i flere andre sammenhenger, blant annet i bioinformatikk.

Personalia:
Daniel Lokshtanov er født i 1984 i Moskva. Han er Bachelor i Matematikk og Master i Informatikk ved Universitetet i Bergen, med et år av mastergraden tilbragt ved University of Waterloo.

Tidspunkt og sted for disputasen:
22.06.2009, kl. 10:15, Store auditorium i Høyteknologisenteret i Bergen (HiB)

Kontaktpersoner:
Daniel Lokshtanov , epost: Daniel.lokshtanov@ii.uib.no
Mediekontakt Mia Kolbjørnsen, tlf. 55 58 90 39 (a), e-post: mia.kolbjornsen@form.uib.no

Avhandlingen kan lånes på Bibliotek for realfag. For kjøp/bestilling av avhandlingen, kontakt kandidaten direkte.