Väitös tietotekniikan alalta, M.Sc. Nidia Obscura Acosta

Väitöskirjan nimi: On the connectivity interdiction problem, the geometry of data structures and Eulerian circuits

Tohtoriopiskelija: Nidia Obscura Acosta
Vastaväittäjä: professori Guy Even, Tel Aviv University, Israel
Kustos: professori Parinya Chalermsook, Aalto-yliopiston perustieteiden korkeakoulu, tietotekniikan laitos

Optimointialgoritmien tutkimuksesta on viime vuosisadan aikana käytännön tietokoneiden kehityttyä tullut yksi teoreettisen tietojenkäsittelytieteen tärkeimmistä tutkimusaloista. Tietokonealgoritmit ovat nykyään läsnä kaikkialla teknologiassamme ja yhteiskunnassamme, auttaen meitä lisäämään tuottavuutta, kehittämään viestintäämme ja kaiken kaikkiaan luomaan innovaatioita. Tehokkaat tietokonealgoritmit näyttelevät tärkeää roolia suunniteltaessa ja toteutettaessa ratkaisuja optimointiongelmiin, joilla on lukuisia yhteiskunnallisia, teollisia ja hallinnollisia sovelluksia esimerkiksi ruoan tuotannossa, äänestysjärjestelmissä, reittisuunnittelussa, kuljetuksessa, pelisuunnittelussa, proteiinisynteesissä, tarttumatautien hallinnassa, opiskelupaikkojen jaossa, geeniperimän kokoamisessa ja lääkkeiden annostelussa.

Tämän alan kehitys on kuitenkin kohdannut suuria teoreettisia ja käytännöllisiä haasteita, kuten laskentaresurssien puute, datan kasvava määrä suurissa verkostoissa, sekä muita teoreettisia ja rakenteellisia esteitä, kuten NP-vaikeus. 
Näiden teoreettisten vaikeuksien ohittamiseksi tämä väitöskirja tarkastelee kolmea pääasiallista ongelmaa graafien ja kombinatorisen optimoinnin aloilla: Eulerin kierros -ongelmaa, konnektiivisuuden esto-ongelmaa ja binääristen hakupuiden tietorakenteen geometriaa.

Tuloksemme kehittävät viimeisintä ymmärrystä kaikkien näiden ongelmien osalta osoittamalla uusia tuloksia rakenteellisessa graafiteoriassa ja käyttämällä tekniikoita approksimaatioalgoritmeista, ekstremaalinen kombinatoriikasta ja geometrisistä metodeista, minkä avulla pystymme todistamaan sekä parempia algoritmisia tuloksia, että uusia laskennallisen kompleksisuuden määrittelyä näille ongelmille. Näitä tuloksia voidaan soveltaa erityisesti geeniperimän kokoamisessa ja verkostosuunnitteluongelmissa, kuten kuljetus- ja reititysjärjestelmissä.

Avainsanat: tehokkaat algoritmit, Eulerin kierros, tietorakenteet, konnektiivisuus, approksimaatioalgoritmit

Linkki väitöskirjan sähköiseen esittelykappaleeseen (esillä 10 päivää ennen väitöstä): https://aaltodoc.aalto.fi/doc_public/eonly/riiputus/ 

Yhteystiedot:

Perustieteiden korkeakoulun väitöskirjat: https://aaltodoc.aalto.fi/handle/123456789/52 

Zoom pikaopas: https://www.aalto.fi/fi/palvelut/zoom-pikaopas