Pienen dominoivan joukon etsiminen tasoverkossa hajautetusti

Näytä kaikki kuvailutiedot

Permalink

http://urn.fi/URN:NBN:fi-fe2017112252162
Julkaisun nimi: Pienen dominoivan joukon etsiminen tasoverkossa hajautetusti
Tekijä: Hilke, Miikka
Muu tekijä: Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta, Tietojenkäsittelytieteen laitos
Opinnäytteen taso: pro gradu -tutkielmat
Tiivistelmä: Dominoiva joukko D on jonkin verkon solmujen osajoukko siten, että verkon jokainen solmu joko kuuluu D:hen tai on siihen kuuluvan solmun naapuri. Verkon pienimmän dominoivan joukon löytäminen verkossa on NP-kova ongelma. Mikäli algoritmi etsii pienintä joukkoa, jonka koko on x, mutta sen voidaan taata löytävän vain joukon, jonka koko on enintään ax jollakin vakiolla a, kutsutaan tulosjoukkoa oikean ratkaisun a-approksimaatioksi. Rajoitetussa verkossa voidaan löytää pienimmän dominoivan joukon approksimaatioita nopeasti. Hajautetussa laskennassa verkon solmut ovat rinnakkaisesti toimivia prosessoreita, jotka suorittavat kaikki samaa algoritmia. Vakioaikaisuudella tarkoitetaan hajautetun laskennan kontekstissa sitä, että prosessorit saavat vaihtaa naapuriprosessoriensa kanssa vain vakiomäärän viestejä. Algoritmi palauttaa valmistuttuaan jokaiselle solmulle tulosteen, esimerkiksi tiedon siitä, kuuluuko solmu dominoivaan joukkoon. Tässä tutkielmassa tarkastellaan pienimmän dominoivan joukon vakioaikaisia approksimaatioita tasoverkossa hajautetun laskennan näkökulmasta. Ensiksi tutkielmassa esitellään todistus, että ei ole olemassa hajautettua algoritmia, joka löytäisi (5 − epsilon)-approksimaation pienimmästä dominoivasta joukosta, kun epsilon > 0. Tämän jälkeen todistetaan, että myös tiukempi (7 − epsilon)-approksimaatioalaraja pätee. Lopuksi esitellään hajautettu algoritmi joka löytää ainakin 52-approksimaation pienimmästä dominoivasta joukosta tasoverkossa. Algoritmi käyttää uniikkeja tunnisteita eikä prosessorien välisten viestien kokoja ole rajoitettu. Algoritmin analyysissä yhdistetään Lenzenin et al. (2010) esittämä alkuperäinen analyysi ja Wawrzyniakin (2013) esittämä analyysin toisen osan parannus.
URI: URN:NBN:fi-fe2017112252162
http://hdl.handle.net/10138/44925
Päiväys: 2014
Oppiaine: Algorithms and Machine Learning
Algorithms and Machine Learning
Algorithms and Machine Learning


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
gradu.pdf 1019.KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot