Hyppää sisältöön
    • Suomeksi
    • In English
Trepo
  • Suomeksi
  • In English
  • Kirjaudu
Näytä viite 
  •   Etusivu
  • Trepo
  • Opinnäytteet - ylempi korkeakoulututkinto
  • Näytä viite
  •   Etusivu
  • Trepo
  • Opinnäytteet - ylempi korkeakoulututkinto
  • Näytä viite
JavaScript is disabled for your browser. Some features of this site may not work without it.

Polyominojen pakkaaminen tasossa

Sahlberg, Jon (2014)

 
Avaa tiedosto
gradu07220.pdf (400.8Kt)
Lataukset: 



Sahlberg, Jon
2014

Tietojenkäsittelyoppi - Computer Science
Tietojenkäsittelyopin maisteriopinnot - Master's Programme in Computer Science
Informaatiotieteiden yksikkö - School of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2014-10-14
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:uta-201412302550
Tiivistelmä
Polyominot ovat kaksiulotteisia kappaleita, jotka muodostuvat yhdestä tai useammasta, särmistään toisiinsa liitetyistä, samankokoisista neliöstä. Tason täyttäminen valitulla polyominojoukolla on NP-täydellinen ongelma. Tässä tutkielmassa esitetään uusi tarkistussummiin perustuvan menetelmä, joilla polyominojen pakkaamista tasolle pyritään tehostamaan aiempiin vastaaviin pakkausmenetelmiin verrattuna. Kutsun kehittämääni menetelmää moduloidun bittikentän menetelmäksi. Moduloidun bittikentän menetelmässä täytettävälle alueelle sekä polyominoille etsitään sopiva jakaja. Jakajan perusteella täytettävälle alueelle ja polyominoille lasketaan tarkistussummat. Sopivalla jakajan valinnalla tarkistussummat saadaan kuvaamaan samanaikaisesti sekä polyominon muotoa että sijaintia täytettävällä alueella. Kaikki mahdolliset ratkaisuvaihtoehdot alueen täyttämiseksi voidaan löytää alueen ja kappaleiden yhteenlaskettuja tarkistussummia vertailemalla. Moduloidun bittikentän menetelmällä alkuperäinen vaikea tehtävä jakautuu useammaksi pienemmäksi tehtäväksi, joiden ratkaiseminen voi usein olla huomattavasti alkuperäistä tehtävää helpompaa. Tutkielmassa esitetään myös muutokset, jotka mahdollistavat hajota ja hallitse -menetelmän käytön moduloidun bittikentän menetelmän yhteydessä. Hajota ja hallitse -menetelmään soveltamiseksi tarkistussummat muunnetaan sopivaan binääriseen kantalukuesitykseen. Sopivalla binäärisellä kantaluvulla kappaleille voidaan muodostaa tarkistussummat aiempaa pienemmällä jakajalla säilyttäen tieto kappaleen muodosta ja sijainnista. Huomattavan nopeusedun ansiosta moduloidun bittikentän menetelmä mahdollistaa huomattavasti suurempien alueiden pakkaamisen kuin vastaavat bittikenttiin perustuvat menetelmät. Hajota ja hallitse -menetelmän ansiosta moduloidun bittikentän algoritmi on myös erittäin tehokkaasti rinnakkaistettavissa.
Kokoelmat
  • Opinnäytteet - ylempi korkeakoulututkinto [40481]
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste
 

 

Selaa kokoelmaa

TekijätNimekkeetTiedekunta (2019 -)Tiedekunta (- 2018)Tutkinto-ohjelmat ja opintosuunnatAvainsanatJulkaisuajatKokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste