NY DOKTORGRAD
Prisen for perfeksjon – Algoritmer for vanskelige oppgaver
 |
“Exponential Time Algorithms: Structures, Measures, and Bounds”
I Informatikk skiller man mellom enkle og vanskelige oppgaver. Enkle oppgaver kan løses ved en datamaskin med en liten mengde beregningsressurser – processortid og minne. Derimot krever harde oppgaver enorme mengder beregningsressurser. Den vanligste strategien for å håndtere på dette problemet er å regne kun tilnærmelsesløsninger, i stedet for optimale løsninger, for disse vanskelige oppgaver.
I avhandlingen studeres nøyaktige algoritmer for å løse forskjellige vanskelige oppgaver optimalt. En algoritme for en oppgave er en slags oppskrift på en programmerer, vanligvis beskrevet i naturlig språk eller pseudo-kode. Algoritmene skal være raskere enn å prøve ut alle muligheter (“brute-force”) eller andre tidligere kjente algoritmer.
En av de vanskelige oppgavene studert i denne avhandlingen er å fjerne et minimum antall noder fra et nettverk slik at det ikke er noen flere sykler i nettverket. Dette er et typisk matematisk abstraksjon av flere konkrete oppgaver som naturlig oppstår i ulike programmer, håndtering for eksempel med genommontering, integrert krets-design, og mange andre.
Med den nye algoritmen som er presentert og analysert i denne avhandlingen, er det mulig å beregne optimale løsninger på denne oppgaven for nettverk som har 23 % flere noder.
Dessuten oppgavesensitiv forbedrede algoritmer, mer generelle strategier er utarbeidet i avhandlingen som er avhengige av kombinasjonen av eksisterende teknikker for design og analysen av algoritmer.
Personalia:
Serge Gaspers er født i 1981 i Luksemburg, Luksemburg og oppvokst i Kayl, Luksemburg. Han er utdannet master i informatikk ved Université Paul Verlaine – Metz, Frankrike, i 2005. Siden januar 2006 har han jobbet med doktorgraden ved Institutt for Informatikk, Universitetet i Bergen.
Tidspunkt og sted for disputasen:
05.12.2008, kl. 11:15, VIL VITE, Vitensenter AS, Auditoriet, Thormøhlensgt.
51
Kontaktpersoner:
Serge Gaspers, epost: serge@ii.uib.no
Mediekontakt Therese Marianne Istad, tlf. 55 58 91 70 (a), e-post: therese.istad@form.uib.no
Avhandlingen kan lånes på Bibliotek for realfag. Avhandlingen er elektronisk tilgjengelig i BORA. For kjøp/bestilling av avhandlingen, kontakt kandidaten direkte.