Igor Podsechin
1:a plats, internationella kategorin
Igor Podsechin, gymnasiet Tampereen lyseon lukio
Hela arbete
Comparing Minimum Spanning Trees
(En jämförelse av algoritmer för minsta uppspännande träd)
Igor Podsechin, 18 år, bedrev sommaren 2008 självständiga studier i diskret matematik. I sin matematikbok läste han då om två algoritmer med hjälp av vilka man konstruerar ett uppspännande träd. Inget mer sades dock om dessa algoritmer, inte heller vilken av dem som är bättre. Igor blev inspirerad att utreda frågan närmare och beslöt att delta med sitt ämne i Viksu.
I sitt arbete som faller inom grafteorins område gör Igor en jämförelse mellan tre algoritmer – Prims, Kruskals och Boruvkas algoritm – i syfte att finna det minsta möjliga uppspännande trädet. Han presenterar hur de tre algoritmerna kan realiseras med programmeringsspråket Java. I sin studie konstaterar Igor att Prims algoritm är långsammast, även om alla algoritmerna relativt väl följer komplexitetsklassen. Kruskals och Boruvkas algoritmer ligger mycket nära varandra med avseende på prestationsförmågan.
Igors utmärkta arbete ansågs vetenskapligt sett vara mycket ambitiöst och i synnerhet dess experimentella del var förtjänstfull. Hela arbetet var välskrivet och höll språkligt en osedvanligt hög nivå. Igors problemformulering är tydlig och ger en sammanhängande presentation av såväl teorin bakom problemet som algoritmernas funktion. Igor har i sitt arbete använt sig av aktuell litteratur på ett vederbörligt sätt. Enligt utvärderarna har Igors studie visat sig vara mycket fruktbar: Igor drog slutsatser på basis av de undersökta algoritmerna, men presenterade också utifrån sina resultat en ny idé om vilken slags algoritm som kunde lösa problemet ännu mer effektivt än de nuvarande. Igor visar att han behärskar sitt ämne mycket väl och är också medveten om vilka utmaningar som är förknippade med arbetet. Arbetet visar att skribenten har en klar fallenhet för en forskarkarriär.
På sin fritid ägnar Igor sig åt programmering. Till hans intressen hör också att läsa och spela piano.
Igors arbete handleddes av läraren Tero Taubert.