Algebrallinen näkökulma peittokoodeihin
Heikkilä, Elias (2020-06-11)
Heikkilä, Elias
11.06.2020
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Julkaisun pysyvä osoite on:
http://urn.fi/URN:NBN:fi-fe2020070146549
http://urn.fi/URN:NBN:fi-fe2020070146549
Tiivistelmä
Tässä tutkielmassa käsitellään algebrallista symbolidynamiikkaa ja sovelletaan sitä peittokoodien tutkimiseen. Algebrallisessa symbolidynamiikassa kombinatoriset ja topologiset ongelmat muutetaan polynomeja koskeviksi kysymyksiksi, jolloin ongelmaan saadaan algebrallinen näkökulma. Algebrallisella lähestymistavalla saadaan helppoja todistuksia neliöhilan ja kuningasgraafin peittokoodituloksille.
Tutkielma alkaa symbolidynamiikan perinteisten käsitteiden määrittelyllä ja perustulosten esittelyllä. Tämän jälkeen määritellään kommutatiivisen algebran ja algebrallisen geometrian peruskäsitteet, joilla saadaan uusi näkökulman symbolidynamiikan tutkimukseen. Näin saadaan perinteisen topologisen rakenteen lisäksi myös algebrallista rakennetta käyttöön. Perustietojen jälkeen esitellään työkaluiksi erilaisia polynomihajotelmia ja todistetaan tutkielman kannalta olennaisten ihanteiden rakennetuloksia. Tutkielmassa pyritään rakentamaan tarvittava teoria mahdollisimman suppeilla esitietovaatimuksilla.
Kun teoriapohja on rakennettu, sovelletaan polynomihajotelmia peittokooditulosten todistamiseen. Lopuksi annetaan vielä algoritmi peittokoodien etsimiseen tietyssä erikoistapauksessa.
Tutkielma alkaa symbolidynamiikan perinteisten käsitteiden määrittelyllä ja perustulosten esittelyllä. Tämän jälkeen määritellään kommutatiivisen algebran ja algebrallisen geometrian peruskäsitteet, joilla saadaan uusi näkökulman symbolidynamiikan tutkimukseen. Näin saadaan perinteisen topologisen rakenteen lisäksi myös algebrallista rakennetta käyttöön. Perustietojen jälkeen esitellään työkaluiksi erilaisia polynomihajotelmia ja todistetaan tutkielman kannalta olennaisten ihanteiden rakennetuloksia. Tutkielmassa pyritään rakentamaan tarvittava teoria mahdollisimman suppeilla esitietovaatimuksilla.
Kun teoriapohja on rakennettu, sovelletaan polynomihajotelmia peittokooditulosten todistamiseen. Lopuksi annetaan vielä algoritmi peittokoodien etsimiseen tietyssä erikoistapauksessa.