Kombinatoriske beregninger

Anta at du vil legge opp en kortest mulig reiserute for å besøke alle hovedsteder i Europa. Selv om dette er et enkelt problem å formulere viser det seg at det er svært vanskelig å finne den beste løsningen. Faktisk vet man ikke om en bedre fremgangsmåte enn å prøve alle mulige reiseruter. Det gjør at selv for et fåtall byer vil en superdatamaskin trenge flere år for å finne løsningen.

Men selv om det generelle problemet er vanskelig, finnes det situasjoner hvor man kan utnytte den underliggende strukturen til en gitt instans slik at man likevel kan finne en løsning effektivt. Fagområdet som studer denne typen egenskaper kalles for Parametrisert kompleksitet. Boolean-width er en slik egenskap som kan brukes for å utvikle raskere løsningsmetoder.

Til nå har alt arbeid rundt Boolean-width vært utelukkende teoretisk. Sharmin har i sin avhandling studert hvordan boolean-width kan brukes i praksis. Dette har involvert å utvikle og å teste dataprogram som tar for seg vanskelige problem og avgjør om de lar seg løse effektivt. Konklusjonen fra hennes arbeid er at det finnes en rekke situasjoner hvor boolean-width kan gi raskere løsningsmetoder sammenlignet med tilsvarende metoder.

Personalia:
Sadia Sharmin er født i 1983 i Mymensing, Bangladesh. Hun er utdannet fra Department of Computer Science and Engineering (CSE) ved Bangladesh University of Engineering and Technology (BUET). Siden 2010 har hun vært tilsatt som stipendiat ved Institutt for informatikk, Universitetet i Bergen for å arbeide med avhandlingen sin.