Väitös informaatioteorian alalta, Ville Pettersson
Väitöksen nimi on Graafialgoritmeja syklien ja niihin liittyvien rakenteiden konstruointiin ja enumerointiin
Map © OpenStreetMap. Some rights reserved.
Graafi on matemaattinen olio joka koostuu solmuista ja solmujen välillä olevista kaarista. Yksinkertaisesta määritelmästä huolimatta graafit ovat hyvin monipuolisia; sen lisäksi että graafit ovat kiinnostavia teoreettisesta näkökulmasta, niillä on suuri määrä sovelluksia monella tieteen ja teknologian alalla, kuten fysiikassa, biologiassa ja tietoliikennetekniikassa.
Tässä väitöskirjassa tutkitaan tietokoneiden avulla eräitä graafien ominaisuuksia.
Väitöskirjassa keskitytään sellaisten laskennallisten menetelmien eli algoritmien kehittämiseen, joilla voidaan etsiä graafeista niin sanottuja syklejä ja laskea syklien lukumääriä.
Väitöskirjassa esitetään ratkaisuja kuuteen avoimeen tutkimusongelmaan. Ongelmien aiheina on Hamiltonin syklien lukumäärän laskeminen, täydellisten paritusten lukumäärän laskeminen hyperkuutiossa, pitkien indusoitujen syklien ja polkujen haku hyperkuutiossa, pienet hypohamitoniset tasograafit ja Toeplitzin konjektuuri.
Osa väitöskirjan tutkimustuloksista voidaan luokitella teoreettiseksi perustutkimukseksi. Osalla tuloksista taas on melko suoria sovelluksia. Esimerkiksi indusoituja syklejä hyperkuutiossa voidaan käyttää virheen tunnistavina koodeina tiedon välityksessä.
Vastaväittäjänä toimii professori Gary McGuire, University College Dublin, Ireland
Valvojana on professori Patric Östergård, Aalto-yliopiston sähkötekniikan korkeakoulu, tietoliikenne- ja tietoverkkotekniikan laitos
Väitöskirjan verkko-osoite
Väittelijän yhteystiedot
Ville Pettersson
p. 050 4626499
ville.pettersson@aalto.fi