Kahden merkkijonon pisimmän yhteisen alijonon ongelma ja sen ratkaiseminen

Tämä tutkielma kuuluu merkkijonoalgoritmiikan piiriin. Merkkijono S on merkkijonojen X[1..m] ja Y[1..n] yhteinen alijono, mikäli se voidaan muodostaa poistamalla X:stä 0..m ja Y:stä 0..n kappaletta merkkejä mielivaltaisista paikoista. Jos yksikään X:n ja Y:n yhteinen alijono ei ole S:ää pidempi, sanotaan, että S on X:n ja Y:n pisin yhteinen alijono (lyh. PYA). Tässä työssä keskitytään kahden merkkijonon PYAn ratkaisemiseen, mutta ongelma on yleistettävissä myös useammalle jonolle. PYA-ongelmalle on sovelluskohteita – paitsi tietojenkäsittelytieteen niin myös bioinformatiikan osa-alueilla. Tunnetuimpia niistä ovat tekstin ja kuvien tiivistäminen, tiedostojen versionhallinta, hahmontunnistus sekä DNA- ja proteiiniketjujen rakennetta vertaileva tutkimus. Ongelman ratkaisemisen tekee hankalaksi ratkaisualgoritmien riippuvuus syötejonojen useista eri parametreista. Näitä ovat syötejonojen pituuden lisäksi mm. syöttöaakkoston koko, syötteiden merkkijakauma, PYAn suhteellinen osuus lyhyemmän syötejonon pituudesta ja täsmäävien merkkiparien lukumäärä. Täten on vaikeaa kehittää algoritmia, joka toimisi tehokkaasti kaikille ongelman esiintymille. Tutkielman on määrä toimia yhtäältä käsikirjana, jossa esitellään ongelman peruskäsitteiden kuvauksen jälkeen jo aikaisemmin kehitettyjä tarkkoja PYAalgoritmeja. Niiden tarkastelu on ryhmitelty algoritmin toimintamallin mukaan joko rivi, korkeuskäyrä tai diagonaali kerrallaan sekä monisuuntaisesti prosessoiviin. Tarkkojen menetelmien lisäksi esitellään PYAn pituuden ylä- tai alarajan laskevia heuristisia menetelmiä, joiden laskemia tuloksia voidaan hyödyntää joko sellaisinaan tai ohjaamaan tarkan algoritmin suoritusta. Tämä osuus perustuu tutkimusryhmämme julkaisemiin artikkeleihin. Niissä käsitellään ensimmäistä kertaa heuristiikoilla tehostettuja tarkkoja menetelmiä. Toisaalta työ sisältää laajahkon empiirisen tutkimusosuuden, jonka tavoitteena on ollut tehostaa olemassa olevien tarkkojen algoritmien ajoaikaa ja muistinkäyttöä. Kyseiseen tavoitteeseen on pyritty ohjelmointiteknisesti esittelemällä algoritmien toimintamallia hyvin tukevia tietorakenteita ja rajoittamalla algoritmien suorittamaa tuloksetonta laskentaa parantamalla niiden kykyä havainnoida suorituksen aikana saavutettuja välituloksia ja hyödyntää niitä. Tutkielman johtopäätöksinä voidaan yleisesti todeta tarkkojen PYA-algoritmien heuristisen esiprosessoinnin lähes systemaattisesti pienentävän niiden suoritusaikaa ja erityisesti muistintarvetta. Lisäksi algoritmin käyttämällä tietorakenteella on ratkaiseva vaikutus laskennan tehokkuuteen: mitä paikallisempia haku- ja päivitysoperaatiot ovat, sitä tehokkaampaa algoritmin suorittama laskenta on.

Ristikkorakenteisen hihnakuljetinsillan mitoitustyökalun kehittäminen

Hihnakuljettimia käytetään muun muassa voimalaitos- ja sellutehdasympäristöissä kuljettamaan kiinteää polttoainetta tai haketta pitkiä matkoja. Pitkät hihnakuljettimet asennetaan yleensä teräsristikoista rakennettujen kuljetinsiltojen sisään. Kuljetinsilta toimii siis hihnakuljettimen ja hoitokäytävän runkona sekä suojaa kuljetinta ja kuljetettavaa materiaalia säältä. Tässä diplomityössä on laadittu mitoitustyökalu, jolla voidaan nopeasti mitoittaa ristikkorakenteisen hihnakuljetinsillan sauvat sekä määrittää rakenteen massa. Laskentaohjelma on toteutettu Microsoft Excel -taulukkolaskentana. Sillan poikkileikkaus voi olla suljettu symmetrinen umpirakenne tai avorakenne, jossa on ulokkeellinen hoitotaso. Ristikon sauvat ovat RHS-putkia. Rakenteeseen voi vaikuttaa jatkuvia kuormia, pistekuormia sekä näistä johdetut, ekvivalenttiin staattiseen voimaan perustuvat maanjäristyskuormat. Diplomityössä on perehdytty mitoitustyökalussa sovellettuihin teorioihin. Voimasuureiden laskenta perustuu 2-tukisina palkkeina käsiteltävien siltalohkojen ratkaisuun ja palkkianalogiaan, jossa ristikon sauvavoimat ratkaistaan käsittelemällä ristikkoa palkkina. Sauvojen kestävyyden laskenta perustuu SFS-EN 1993-1-1 -normiin, joka on osa Eurocode -rakennesuunnittelunormistoa. Lisäksi työssä on käsitelty ristikkoliitosten mitoitusta SFS-EN 1993-1-8 mukaan. Mitoitusohjelman toimivuutta on testattu tarkastelemalla esimerkkisiltaa laaditulla mitoituspohjalla ja Autodesk Robot Professional 2013 -FE-analyysiohjelmisuolla. Tulosten perusteella mitoitustyökalua voidaan käyttää ainakin tarjousvaiheen nopeisiin tarkasteluihin ja omamassan määritykseen, mutta myös lopulliseen mitoitukseen, mikäli hyväksytään konservatiivinen mitoitus.