Polyominojen laskeminen
Vainio-Kaila, Joni (2021-04-13)
Polyominojen laskeminen
(13.04.2021)
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
avoin
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2021042611892
https://urn.fi/URN:NBN:fi-fe2021042611892
Tiivistelmä
Tässä tutkielmassa tutkitaan samankokoisista neliöistä koostuvia yhtenäisiä tason kuvioita, polyominoja. Tutkielmassa tutkitaan erityisesti polyominojen laskemiseen liittyviä ongelmia. Tutkimusongelmia ovat polyominojen lukumäärien laskeminen algoritmisesti, polyominojen lukumäärien ylä- ja alarajat sekä polyominojen lukumääriä generoivat funktiot.
Tutkielmassa esitetään ensin taustatietona generoiviin funktioihin ja rekursiivisiin lukujonoihin liittyviä tuloksia. Tämän jälkeen polyominoille ja tietynlaisista polyominoista muodostetuille osajoukoille annetaan tarkat matemaattiset määritelmät sekä johdetaan niille joitakin perustuloksia. Tässä tutkielmassa tutkittavia polyominoja ovat kiinnitetyt, kiraaliset, vapaat, suunnatut ja rivikonveksit polyominot.
Tutkielman alussa esitettyjen määritelmien ja tulosten avulla annetaan eräs algoritmi polyominojen laskemiseksi sekä johdetaan ylä- ja alarajat erilaisten polyominojen lukumäärille ja Klarnerin vakiolle, jonka suuruus kuvastaa polyominojen lukumäärän asymptoottista kasvuvauhtia. Tutkielman lopussa annetaan vielä kaksi generoivaa funktiota, joiden avulla rivikonveksien ja suunnattujen polyominojen lukumäärät voidaan laskea.
Tutkielmassa esitetään ensin taustatietona generoiviin funktioihin ja rekursiivisiin lukujonoihin liittyviä tuloksia. Tämän jälkeen polyominoille ja tietynlaisista polyominoista muodostetuille osajoukoille annetaan tarkat matemaattiset määritelmät sekä johdetaan niille joitakin perustuloksia. Tässä tutkielmassa tutkittavia polyominoja ovat kiinnitetyt, kiraaliset, vapaat, suunnatut ja rivikonveksit polyominot.
Tutkielman alussa esitettyjen määritelmien ja tulosten avulla annetaan eräs algoritmi polyominojen laskemiseksi sekä johdetaan ylä- ja alarajat erilaisten polyominojen lukumäärille ja Klarnerin vakiolle, jonka suuruus kuvastaa polyominojen lukumäärän asymptoottista kasvuvauhtia. Tutkielman lopussa annetaan vielä kaksi generoivaa funktiota, joiden avulla rivikonveksien ja suunnattujen polyominojen lukumäärät voidaan laskea.