NY DOKTORGRAD
Om det som datamaskiner finner vanskelig
 |
"Techniques in Parameterized Algorithm Design"
Avhandlingen omhandler metoder for å gi algoritmer(løsningsmetoder) for en gruppe beregningsproblemer kalt de ”NP-harde” problemene. Felles for problemene i denne gruppen er at de er vanskelige for datamaskiner å løse innen rimelig tid, det vil si at man ikke kjenner noen effektiv algoritme for noen av dem. Mange av disse problemene er av stor praktisk interesse og det har blitt fremsatt en lang rekke metoder for å finne brukbare algoritmer også for problemer i denne gruppen. En av de nyeste metodene er parameteriserte algoritmer, hvor man har vist at en del av de NP-harde problemene kan løses effektivt gitt antagelser om problemet vi ønsker å løse, for eksempel at løsningen skal være av begrenset størrelse.
Parameteriserte Algoritmer er et relativt nytt felt og det er gjort få helhetlige arbeider som dekker de forskjellige teknikkene som finnes for å lage algoritmer av denne typen. Gjennom Slopers avhandling får vi for første gang en kategorisering av de forskjellige teknikkene i feltet etter teknikkenes virkemåter. Dette har ledet til en bedre forståelse for hvilke problemer det lar seg utvikle parameteriserte algoritmer for og avhandlingen gjør også feltet mer oversiktlig for nye forskere. I tillegg blir teknikkene anvendt på en rekke beregningsproblemer hvor særlig metoden ”kronedekomposisjon” blir trukket frem og videreutviklet.
Personalia:
Christian Sloper er født i 1977 og oppvokst på Askøy utenfor Bergen. Han er utdannet cand. scient i informatikk ved Universitetet i Bergen i 2001. I de siste fire årene har han vært ansatt som doktorgradstipendiat ved Institutt for Informatikk, Universitetet i Bergen under det NFR-finansierte prosjektet ”Parameterisert kompleksitet og grafalgoritmer”, i tillegg har han hatt forskerstillinger ved University of Newcastle i Australia og Univerzita Karlova i Praha.
Tidspunkt og sted for disputasen:
06.03.2006, kl. 14:15, Stort Auditorium, rom 2144, Datablokken, Høyteknologisenteret, Thormøhlensgt. 55
Kontaktpersoner:
Christian Sloper, tlf. 55 58 41 62, epost: christian.sloper@ii.uib.no
Formidlingsavdelingen v/ mediekontakt Monika Sandnesmo, tlf. 55 58 91 70 (a), epost: monika.sandnesmo@form.uib.no
Avhandlingen kan lånes på Det matematisk-naturvitenskapelige fakultetsbibliotek. Avhandlingen finnes også elektronisk tilgjengelig her:
http://hdl.handle.net/1956/1112
For kjøp/bestilling av avhandlingen kontakt kandidaten direkte.