NY DOKTORGRAD
Hvis du ikke kan håndtere det, forvandle det!
 Foto: Mostofa Patwary |
"Space and Time Efficient Structural Improvements of Dynamic Programming Algorithms"
I løpet av de to siste tiårene har bruken av datamaskiner og mengden av digital informasjon økt dramatisk i alle deler av samfunnet. Gitt en mengde informasjon, slik som passasjerstatistikker eller meteorologiske målinger, står vi overfor beregningsmessige utfordringer, som vi kaller for "problemer", slik som oppsetting av togruter eller å produsere værmeldinger. For at slike problemer skal kunne løses av datamaskiner, må datamaskinen motta en oppskrift med nøyaktige instrukser, som kalles en "algoritme". Mange raske og effektive algoritmer har blitt utviklet i løpet av de siste 60 årene. Dessverre finnes det mange problemer som ikke lar seg løse effektivt ved hjelp av algoritmene vi kjenner så langt. Hvert av disse, såkalt NP-harde, problemene ville ta flere enn 1000 år og all tilgjengelig datalagringskapasitet å løse hvis vi bruker de algoritmene vi så langt kjenner.
Nederlof har tatt for seg en sentral teknikk i utvikling av algoritmer som kalles "Dynamisk Programmering (DP)". Teknikken går ut på å dele opp problemet i mindre biter, løse småbitene for seg, lagre løsningene, og komme frem til en måte å kombinere de lagrede løsningene til å løse hele problemet. En av de utfordringene med denne teknikken er lagringskapasitet, siden man ender opp med veldig mange løsninger som må lagres underveis. Nederlof bidrar med metoder for å redusere lagringskapasitet som trengs for DP. De nye metodene går ut på å omforme strukturen til den lagrede informasjonen. På den måten kan biter som ikke lenger er nødvendige, identifiseres og forkastes. For mange algoritmer basert på DP, introduseres det nye alternative algoritmer som beviselig krever så mye mindre lagringskapasitet at de tilsvarende problemene nå kan faktisk løses med eksisterende lagringskapasitet. Et av høydepunktene i arbeidet er "Delmendgesum"- problemet: Den regjerende beste algoritmen helt siden 1950-tallet har i avhandlingen blitt forbedret til å kunne løse problemet like raskt men med betraktelig mye mindre lagringsbehov.
Personalia:
Jesper Nederlof er født i 1985 i Gorinchem, Nederland. Han fikk sin mastergrad i anvendt informatikk i 2008 fra Universitetet i Utrecht, Nederland. Han har vært ansatt som stipendiat ved Institutt for informatikk ved Universitetet i Bergen siden november 2008, under veiledning av Professor Pinar Heggernes. I februar 2012 starter han som postdoktor ved Universitetet i Utrecht og vil fortsette arbeidet fra doktoravhandlingen.
Tidspunkt og sted for prøveforelesningen:
25.11.2011, kl. 10.15. Oppgitt emne: "Property testing"
Sted: Høyteknologisenteret, Datablokken, 2.etg. Lille Auditorium
Tidspunkt og sted for disputasen:
09.12.2011, kl. 10.15, Høyteknologisenteret, Datablokken, 2.etg. Store Auditorium
Kontaktpersoner:
Jesper Nederlof, tlf: 55 58 41 87, epost: Jesper.Nederlof@ii.uib.no
Mediekontakt ved Kommunikasjonsavdelingen
E-post: mediekontakt[ætt]uib.no
Telefon: 55 58 89 00
Avhandlingen kan lånes på Bibliotek for realfag. For kjøp/bestilling av avhandlingen, kontakt kandidaten direkte.