Universitetet i Bergen : Doktorgrader : 2008

NY DOKTORGRAD

Raskere løsning av vanskelige problemer

Alexey Stepanov   
Alexey Stepanov disputerer 3. desember for PhD-graden ved Universitetet i Bergen med avhandlingen:

"Exact Algorithms for Hard Listing, Counting and Decision Problems".

Vi har mange forskjellige problemer å løse hver dag. Innen informatikk snakker vi om lette P-problemer som kan løses raskt. Vanskelige NP-problemer kan det ta mange år å løse. Et eksempel på et såkalt NP-problem er å finne den korteste veiruten som begynner i Oslo, besøke alle byer i Norge kun en gang, og så tilbake til utgangspunktet i Oslo.

I avhandlingen beskriver Stepanov noen vanskelige NP-problemer med praktisk anvendelse og gir løsninger til dem. Problemene kommer fra forskjellige vitenskapsområder: nettverk, kommunikasjon, biologi etc.

For eksempel gir kandidaten raskt løsningen til problemet som heter "Full Degree Spanning Tree". Spørsmålet er hvordan man kan bruke minst mulig antall trykkmålere i ett vannettverk for å registrere trykket i alle deler av nettverket. Dersom man kan benytte færre antall trykkmålere i nettverket, kan man redusere kostnader i større nettverk.

Stepanov presenterer nye algoritmer for å løse vanskelige problemer og nye metoder for analysering av disse algoritmene.

Resultater fra flere avhandlinger kan brukes i mange forskjellige algoritmer for andre typer problem.

Personalia:
Alexey Stepanov er født i 1983 i en liten by i Nord-Russland. Han tok mastergrad ved Sankt Petersburgs Statsuniversitet i 2004, og begynte på doktorgraden samme år ved Universitetet i Bergen.

Tidspunkt og sted for disputasen:
03.12.2008, kl. 13:15, Stort Auditorium, rom 2144, Datablokken, Høyteknologisenteret, Thormøhlensgt. 55

Kontaktpersoner:
Alexey Stepanov, epost: ljosha@ljosha.org
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. For kjøp/bestilling av avhandlingen, kontakt kandidaten direkte.