NY DOKTORGRAD
Jakten på trær i matematiske modeller
 |
"New results on minimal triangulations"
Avhandlingen beskriver nye og mer effektive metoder for å finne strukturer i beregningsproblemer. Noen beregningsproblemer, som i utgangspunktet krever mye ressurser, kan løses effektivt i de tilfeller den matematiske modellen av problemet kan beskrives med en enkel struktur. Trær er et eksempel på en slik enkel struktur, men forekommer sjelden i modeller fra det virkelige liv. På grunn av dette studerer vi en trelignende struktur kalt “tre-dekomponering”. Denne strukturen kan beskrives som en oppdeling av problemet i delproblemer, der avhengigheten mellom disse danner et “tre” med en rot, og mange greiner.
Det kan være krevende å finne den optimale tre-dekomponeringen. Avhandlingen omhandler derfor jakten på en type tre-dekomponeringer kalt “minimale trianguleringer”. Disse dekomponeringene kan sees på som lokale optimale løsninger, og er mulig å finne innen rimelig tid. Selv om problemet med å finne minimale trianguleringer på en effektiv måte har vært studert siden midten på 1970-tallet, er det først i Villangers avhandling at fremskritt har blitt gjort. Dette må regnes som et betydelig resultat innen feltet.
Gjennom dette arbeidet har det kommet fram nye egenskaper som øker forståelsen av minimale trianguleringer. Disse egenskapene har blant annet blitt brukt til å utforme nye og mer effektive data-strukturer, som igjen har bidratt til mer effektive metoder for å finne minimale trianguleringer. I tillegg har oppdagelsen av disse egenskapene ledet til en forbedret løsningmetode for å finne den optimale tre-dekomponeringen.
Personalia:
Yngve Villanger er født i 1974 og oppvokst i Norheimsund i Kvam herad. Han er utdannet cand. scient i informatikk ved Universitetet i Bergen i 2002. I de siste fire årene har han vært ansatt som doktorgradsstipendiat ved Institutt for Informatikk, Universitetet i Bergen. Første halvdel av 2005 ble arbeidet utført ved Université d'Orléans i Frankrike.
Tidspunkt og sted for disputasen:
25.04.2006, kl. 12:15, Stort Auditorium, rom 2144, Datablokken, Høyteknologisenteret, Thormøhlensgt. 55
Kontaktpersoner:
Yngve Villanger, tlf. 55 58 40 92, epost: yngve.villanger@uib.no
Formidlingsavdelingen v/ mediekontakt Monika Sandnesmo, tlf. 55 58 91 70 (a), e-post: monika.sandnesmo@form.uib.no
Avhandlingen kan lånes på Det historisk-filosofiske fakultetsbibliotek. Avhandlingen finnes elektronisk tilgjengelig her: http://hdl.handle.net/1956/1146
For kjøp/bestilling av avhandlingen kontakt kandidaten direkte.