Universitetet i Bergen : Doktorgrader : 2007

NY DOKTORGRAD

Utforsking av grenseområdet mellom det «effektive» og det «ineffektive»

Frederic Dorn   
Frederic Dorn disputerer 14. september for PhD graden ved Universitetet i Bergen med avhandlingen:

«Designing Subexponential Algorithms: Problems, Techniques & Structures»

En algoritme er en oppskrift til å løse et bestemt problem, som leverer en løsning uansett inndata. Algoritmer har mange anvendelser. Hvert enkelt dataprogram, hver maskin eller robotprogram er basert på en algoritme, komplisert eller enkel. Mange av de implementerte algoritmene er problemspesifikke og ganske ofte ikke optimalt utviklet. Selv om algoritmiske problemer utgjør kjernen av informatikk, kommer de sjelden som matematisk presise spørsmål. Mens datamaskiner og anvendelser har blitt utviklet i et dramatisk tempo de siste tiårene, har algoritmeteori blitt konfrontert med nye utfordringer. Maskinene blir raskere og grensen for det som regnes å være effektivt utvides stadig. Denne avhandlingen omhandler nettopp utforsking av grenseområdet mellom «effektive» og «ineffektive» algoritmer.

En utbredt antakelse er at eksponensiell kjøretid er den beste vi kan ha for algoritmer som løser NP-harde problemer, og eksponensielle algoritmer regnes som ineffektive. Likevel kan vi for mange NP-harde problemer blant annet fra logistikk, molekylærbiologi og nettverk finne algoritmer som er brukbare inntil en praktisk akseptabel inndatastørrelse. De siste årene har det blitt mer og mer populært å studere algoritmer som har såkallt «subeksponensielle» kjøretider. Målet er å utnytte strukturen av inndata for å få en sublineær eksponent i kjøretiden. I mange av de studerte algoritmene er eksponenten lik kvadratroten av inndatastørrelsen.

Arbeidet er fokusert på to aspekter av det å finne subeksponensielle algoritmer. Det teoretiske aspektet er fokusert på antakelser om inndatastrukturen og det algoritmiske aspekt på undersøkelse og forbedring av flere dynamisk programmeringsmetoder som brukes for å få raske og effektive algoritmer for forskjellige problemer.

Personalia:
Frederic Dorn er født i 1975 i Freiburg, Tyskland.
Han tok mastergrad i informatikk og matematikk ved Universitetet i Tübingen, Tyskland i 2004 og fra 2004 har han arbeidet med doktorgraden ved Institutt for Informatikk, Universitetet i Bergen, Norge.

Tidspunkt og sted for disputasen:
14.09.2007, kl. 13:00, Stort auditorium, rom 2144, Datablokken, Høyteknologisenteret, Thormøhlensgt. 55

Kontaktpersoner:
Frederic B. Dorn, epost: Frederic.Dorn@ii.uib.no
Formidlingsavdelingen v/ mediekontakt Mia Kolbjørnsen, tlf. 55 58 90 39 (a), e-post: mia.kolbjornsen@form.uib.no

Avhandlingen kan lånes på Det matematisk-naturvitenskapelige fakultetsbibliotek. Avhandlingen er elektronisk tilgjenglig i BORA. For kjøp/bestilling av avhandlingen kontakt kandidaten direkte.