NY DOKTORGRAD
Raskere løsning av vanskelige problemer
 |
"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.