Joel Rybickin gradu "Exact bounds for distributed graph colouring" hyväksyttiin laitosneuvostossa 31.5.2011 arvosanalla laudatur. Laudaturin on saanut vain 1% laitoksen graduista, joten kyse on poikkeuksellisen ansiokkaasta työstä.

Millainen sitten on laudaturin gradu? Alla Joel kertoo itse gradun sisällöstä ja sen jälkeen ohjaajat sen ansioista.

Joel:

Pro gradu -tutkielma käsittelee hajautetun laskennan teoriaa. Aiheena oli niin sanottu hajautettu verkon väritysongelma ja sen laskennallinen vaativuus. Aihe liittyy läheisesti New Paradigms in Computing -ryhmässä tehtävään hajautettujen algoritmien tutkimukseen.

Hajautettu järjestelmä esitetään verkkona, jossa solmut vastaavat laskentayksiköitä ja kaaret laskentayksiköiden välisiä kommunikaatioyhteyksiä. Hajautetun laskennan teoriassa tutkitaan erityisesti verkko-ongelmia. Hajautetun järjestelmän rakennetta kuvaava verkko toimii tällöin syötteenä ja hajautetun algoritmin on tarkoitus ratkoa jokin laskennallinen ongelma tässä verkossa. Yksi esimerkki tällaisestä ongelmasta on niin sanottu verkon väritysongelma.

Verkon väritysngelman tavoitteena on "värittää" verkon solmut siten, että kaarella yhdistetyt solmut ovat erivärisiä, Yleensä värit esitetään kokonaislukuina ja käytettyjen värien määrä halutaan pitää pienenä. Ongelma on tunnetusti vaikea, sillä on NP-täydellistä päättää onko annettu verkko väritettävissä korkeintaan k:lla eri värillä. Väritysongelma ja sen variantit liittyvät läheisesti useisiin aikataulutus- ja resurssienjako-ongelmiin.

Hajautetun laskennan näkökulmasta ongelman vaativuutta voidaan kuvata tutkimalla, kuinka paljon kommunikaatiota tarvitaan ongelman ratkaisemiseksi, eli kuinka paljon informaatiota prosessorien täytyy kerätä naapurustostaan. Tutkielmassa käsitellään väritysongelman ja vaativuutta erityisesti suunnatuissa sykleissä ja puissa. Työn päätulos tarkentaa tunnettuja ala- ja ylärajoja suunnattujen syklien ja puiden hajautetulle 3-värittämiselle.

Keskeisenä tekniikkana työssä käytettiin laskennallista analyysia, sillä hajautettujen väritysalgoritmien olemassaolo voidaan palauttaa niin sanottujen naapurustoverkkojen väritysongelmaan. Oleellisesti hajauttettujen väritysalgoritmien olemassaolo voidaan todistaa ratkomalla kombinatorisia ongelmia tietokoneavusteisesti. Vastaavasti voidaan myös todistaa, että tietyt ehdot täyttävää hajautettua väritysalgoritmia ei voi olla olemassa.

Laskennallisessa osuudessa hyödynnettiin pääasiassa SAT-ratkaisimia (http://en.wikipedia.org/wiki/Boolean_satisfiability_problem) sekä Ukko-klusteria. Väritysongelmien lisäksi työssä tutkittiin tapoja soveltaa vastaavia laskennallisia menetelmiä muiden hajautettujen verkko-ongelmien, kuten maksimaalisten pariutusten, laskennallisen vaativuuden analysointiin.

Ohjaajat Jukka Suomela ja Petteri Kaski:

Joel Rybickin gradu "Exact bounds for distributed graph colouring" on monella tapaa poikkeuksellisen ansiokas opinnäytetyö. Työssä on saavutettu uusia tieteellisiä tutkimustuloksia, jotka liittyvät hajautetun laskennan alan peruskysymyksiin. Gradu on huolella kirjoitettu ja osoittaa syvällistä perehtymistä hajautettujen algoritmien alaan sekä alan tutkimusmenetelmien hyvin monipuolista hallintaa.

Teoreettisen tietojenkäsittelytieteen tutkimuksessa uusien algoritmien suunnittelu ja ongelmien laskennallisen vaativuuden analysointi on perinteisesti ollut ihmistyötä. Rybickin gradussa käytetään matemaattisten todistusten etsimiseen perinteisen lähestymistavan lisäksi tietokoneavusteisia menetelmiä. Laitoksen uusi laskentaklusteri Ukko [1] on tarjonnut tällaisessa työssä tarvittavaa suurta laskentakapasiteettia.

Joel Rybicki työskentelee tällä hetkellä tutkimusavustajana prof. Petteri Kasken johtamassa "Uudet laskentaparadigmat" -tutkimusryhmässä [2]. Eräs ryhmän tutkimusteemoista keskittyy hajautettujen algoritmien tutkimukseen ja erityisesti ns. paikallisten algoritmien [3] tutkimukseen; tällä alalla keskeinen tavoite on ymmärtää, mitä tietoverkkoihin liittyviä laskennallisia tehtäviä voidaan ratkaista tehokkaasti. Joel Rybickin työssä on selvitetty täsmällisiä rajoja sille, kuinka tehokkaasti tietoverkon koordinointiin liittyviä tehtäviä voidaan ratkaista, ja työssä käytettyjä menetelmiä voidaan mahdollisesti hyödyntää alan tutkimuksessa laajemminkin.

[1] http://www.cs.helsinki.fi/tietotekniikka/laskentaklusteri-ukko
[2] http://www.cs.helsinki.fi/group/parac/
[3] http://www.cs.helsinki.fi/jukka.suomela/paikallinen-laskettavuus

Tilastoja

Laudaturia käytetään laitoksella hyvin harvoin, ei edes läheskään joka vuosi. Edelliset laudaturin gradut ovatkin vuosilta 2010 ja 2006.

Laitoksen gradukannan mukaan ennen Joelia laudaturin graduja on hyväksytty vuodesta 1988 lähtien yhteensä 15 kappaletta. Saman kannan mukaan hyväksyttyjä graduja on 1480, joten laudaturin on saanut graduista jokseenkin täsmälleen vain 1%. Eximian on saanut 246 gradua, joten silläkin pääsee reilusti gradujen parhaaseen viidennekseen.

Arvostelussa on aidosti käytössä koko skaala approbaturista alkaen. Niitäkin on nimittäin annettu neljä kappaletta, lubenterejakin 45 kappaletta.

Toimittaja: Hannu Toivonen
Grafiikat: Joel Rybicki
Valokuva: Tuomas Puikkonen