Väitös tietojenkäsittelytieteen alalta, M.Sc. Wanchote Jiamjitrak

Vastaväittäjä: apulaisprofessori László Kozma, Freie Universität Berlin, Saksa
Kustos: apulaisprofessori Parinya Chalermsook, Aalto-yliopiston perustieteiden korkeakoulu, Tietotekniikan laitos

Väitöskirja on julkisesti nähtävillä 10 päivää ennen väitöstä Aalto-yliopiston julkaisuarkiston verkkoriiputussivulla.

Elektroninen väitöskirja

Väitöstiedote:

Kuvittele, että sinulla on rivi laatikoita, joiden sisällä on numeroita, jotka ovat lajiteltuina pienimmästä luvusta suurimpaan. Tarkoituksena on löytää jokin tietty numero yhdestä laatikosta avaamalla mahdollisimman vähän laatikoita. Yksi keinoista löytää numero on avata jokainen laatikko yksitellen ja manuaalisesti tarkastamalla, mutta tämä tapa saattaa viedä paljon aikaa. On olemassa toinen älykkäämpi ja tehokkaampi tapa, jota kutsutaan binäärihauksi. Binäärihaku aloitetaan avaamalla keskimmäinen laatikko. Mikäli haettu numero on pienempi kuin keskimmäisen laatikon numero, niin laatikoita on lähettävä avaamaan vasemmalta puolelta. Jos numero sen sijaan on isompi, niin laatikoita on lähdettävä avaamaan oikealta puolelta. Tätä prosessia toistetaan niin kauan ennen kuin haluttu numero löydetään, sillä binäärisessä haussa hyödynnetään numeroiden järjestystä. Binäärihakua voidaan luonnehtia puumaiseksi rakenteeksi, jota kutsutaan binäärihakupuuuksi (Binary Search Tree BST). On olemassa pitkäaikainen hypoteesi, joka viittaa optimaalisen BST-algoritmin olemassaoloon, joka toimii samalla tavalla kuin kaikki muut algoritmit. Tässä opinnäytetyössä tutkitaan kahta lähestymistapaa, eli potentiaalifunktioita ja äärimmäistä kombinatoriikkaa, optimaalisimman binaarihakupuun tunnistamiseksi. Näiden menetelmien avulla pyrimme yhtenäistämään, vahvistamaan ja luomaan uusia rajoja BST:ille.

Väittelijän yhteystiedot: [email protected]