| dc.date.accessioned |
2014-04-17T05:53:53Z |
und |
| dc.date.accessioned |
2017-10-24T12:24:40Z |
|
| dc.date.available |
2014-04-17T05:53:53Z |
und |
| dc.date.available |
2017-10-24T12:24:40Z |
|
| dc.date.issued |
2014-04-17T05:53:53Z |
|
| dc.identifier.uri |
http://radr.hulib.helsinki.fi/handle/10138.1/3633 |
und |
| dc.identifier.uri |
http://hdl.handle.net/10138.1/3633 |
|
| dc.title |
Pienen dominoivan joukon etsiminen tasoverkossa hajautetusti |
fi |
| ethesis.department.URI |
http://data.hulib.helsinki.fi/id/225405e8-3362-4197-a7fd-6e7b79e52d14 |
|
| ethesis.department |
Institutionen för datavetenskap |
sv |
| ethesis.department |
Department of Computer Science |
en |
| ethesis.department |
Tietojenkäsittelytieteen laitos |
fi |
| ethesis.faculty |
Matematisk-naturvetenskapliga fakulteten |
sv |
| ethesis.faculty |
Matemaattis-luonnontieteellinen tiedekunta |
fi |
| ethesis.faculty |
Faculty of Science |
en |
| ethesis.faculty.URI |
http://data.hulib.helsinki.fi/id/8d59209f-6614-4edd-9744-1ebdaf1d13ca |
|
| ethesis.university.URI |
http://data.hulib.helsinki.fi/id/50ae46d8-7ba9-4821-877c-c994c78b0d97 |
|
| ethesis.university |
Helsingfors universitet |
sv |
| ethesis.university |
University of Helsinki |
en |
| ethesis.university |
Helsingin yliopisto |
fi |
| dct.creator |
Hilke, Miikka |
|
| dct.issued |
2014 |
|
| dct.language.ISO639-2 |
fin |
|
| dct.abstract |
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. |
fi |
| dct.language |
fi |
|
| ethesis.language.URI |
http://data.hulib.helsinki.fi/id/languages/fin |
|
| ethesis.language |
Finnish |
en |
| ethesis.language |
suomi |
fi |
| ethesis.language |
finska |
sv |
| ethesis.thesistype |
pro gradu-avhandlingar |
sv |
| ethesis.thesistype |
pro gradu -tutkielmat |
fi |
| ethesis.thesistype |
master's thesis |
en |
| ethesis.thesistype.URI |
http://data.hulib.helsinki.fi/id/thesistypes/mastersthesis |
|
| ethesis.degreeprogram |
Algorithms and Machine Learning |
en |
| dct.identifier.urn |
URN:NBN:fi-fe2017112252162 |
|
| dc.type.dcmitype |
Text |
|
