3:e plats, internationella kategorin:

Ville Syrjänen

Extending the Dijkstra Algorithm for the Dynamic Shortest Path Problem

(Utvidgande av Dijkstras algoritm för problemet med den dynamiskt kortaste vägen)

Ville Syrjänen, 18, studerar vid gymnasiet Helsingin Suomalainen Yhteiskoulu.

I sitt tävlingsarbete behandlar Ville problemet med den kortaste vägen, känt från klassisk nätverksteori, och utvecklar en ny lösningsalgoritm för det. Ville har undersökt vad som händer när bågarnas vikter i den kända Dijkstra-algoritmen istället för konstanter är funktioner av tid och har tillämpat detta på problemet med den dynamiskt kortaste vägen. Dijkstras algoritm är en klassisk algoritm, som utgör basen för många olika algoritmer. Den letar fram den kortaste rutten från en nod till alla andra noder i en graf, och den används bland annat i ruttningen av datatrafiknät. 

”Det var en rätt lustig slump som fick mig att undersöka just detta ämne. Jag såg vad som hände om vikterna för nätets bågar i Dijkstras algoritm är funktioner istället för konstanter. Först därefter hittade jag namnet på ämnet på biblioteket. Egentligen utvecklade jag alltså algoritmen redan innan jag ens visste att det fanns ett problem känt som den dynamiskt kortaste vägen”, berättar Ville.

Lösningsalgoritmen kan utnyttjas exempelvis i trafikruttning

Som källa för undersökningen har Ville använt Dijkstras originalpublikation, vetenskapliga artiklar och läroböcker i nätverksteori. De bevis och analyser som Ville presenterar i sitt arbete har han utfört självständigt. Handledaren för arbetet, matematikläraren Jarmo Hurri, hjälpte honom att specificera ämnet, definiera begreppen och göra texten klarare.

Den lösningsalgoritm som Ville utvecklat i sitt arbete kan tillämpas rent praktiskt, t.ex. för ruttning av trafik. När man på förhand vet hur mycket tid som går åt, t.ex. för olika delar av ens arbetsresa vid olika tidpunkter, visar algoritmen den snabbaste rutten till arbetet beroende på starttidpunkten.

Utvärderarnas kommentarer

Enligt utvärderarna är Villes ämne mycket krävande. Behandlingen av ämnet är rent teoretisk och kräver en avsevärd matematisk begåvning av forskaren. Utvecklandet av en ny, innovativ lösningsalgoritm vittnar om skribentens kreativitet. Den nya algoritmen är omsorgsfullt härledd och dess funktion har åskådliggjorts med hjälp av ett enkelt exempel. Den algoritm som Ville utvecklat har flera betydelsefulla praktiska tillämpningar, exempelvis när man planerar datatrafik- eller vägnät.

Till sin utformning påminner tävlingsarbetet om en artikel skriven av professionell forskare.  Forskningsmetoderna är valda med omsorg, arbetet är välskrivet och sammanfattningen ger en noggrann beskrivning av arbetets innehåll och mål. Skribenten har också haft förmåga till kritisk granskning av de metoder han utvecklat.  Ville har ett professionellt grepp om forskningsarbetet och behärskar matematisk bevisning utmärkt väl.

Villes intressen: schack, gå på gym