Tarkvarateaduse instituudi doktorant Elena Di Lavore kaitseb 17. novembril 2023. a. algusega kell 14:00 oma doktoritööd „Monoidal Width“ („Monoidiline laius“). Kaitsmine toimub Tallinna Tehnikaülikooli infotehnoloogia maja ruumis ICT-638 (Akadeemia tee 15a) ning on jälgitav veebirakenduse Zoom vahendusel.
Kompositsioonilisus on abstraktsiooni juures tsentraalne: ülesande mõistmise osade kaupa saab kokku panna selle tervikuna mõistmiseks; mudeleid ja koodi saab arendada nii, et nende osi on võimalik asendada või taaskasutada tervikut rikkumata; ülesande terviklahendus on leitav osalahendusi kombineerides. Kompositsioonilisus võib anda ka algoritmilisi eeliseid. Nii on näiteks jaga-ja-valitse algoritmidega, mille puhul ülesande efektiivseks lahendamiseks kasutatakse ära selle kompositsioonilist struktuuri. Üheks väljapaistvaks näiteks sellest on Courcelle'i teoreemid. Need põhinevad jaga-ja-valitse algoritmil ning näitavad, et monaadiliste teist järku valemite kontroll on praktiliselt arvutatav nendel graafidel, mille puu- või klikilaius on tõkestatud.
Taoliste fikseeritud parameetritega praktilise arvutatavuse tulemuste aluseks on asjaolu, et jaga-ja-valitse algoritmid on tõhusad struktuurselt lihtsate sisendite korral. Graafi puu- ja klikilaius mõõdavad selle struktuurset keerukust ning kui graafi laius on väike, on osalahenduste kombineerimine praktiliselt arvutatav. Siinne töö üritab tuua parametriseeritud keerukuses kasutatavad võtted monoidilisse kategooriateooriasse.
Käesolev doktoritöö toob sisse monoidilise laiuse mõiste, et mõõta morfismide struktuurset keerukust monoidilistes kategooriates, ning uurib mõningaid selle omadusi. Valides sobiva kategoorsed algebrad, on monoidiline laius puu- ja klikilaiuse vasteks. Monoidiline laius põhineb monoidilistel dekompositsioonidel samal viisil, nagu graafilaiused põhinevad graafi-dekompositsioonidel ning graafiavaldistel. Monoidilised dekompositsioonid on termid monoidiliste kategooriate keeles, mis kirjeldavad jaga-ja-valitse algoritmidele vajaliku kompositsioonilise struktuuri. Üldine strateegia monoidiliste kategooriate ülesannetel fikseeritud parameetritega praktilise arvutatavuse tulemuste saamiseks toob esile monoidilise laiuse kontseptuaalse olulisuse: kompositsioonilised algoritmid muudavad funktoriaalsed ülesanded praktiliselt arvutatavaks tõkestatud monoidilise laiusega morfismidel.
Doktoritöö on avaldatud Tehnikaülikooli raamatukogu digikogus.
Juhendaja: prof Pawel Maria Sobocinski.
Oponendid:
- prof Samson Abramsky, University College London, Suurbritannia;
- prof Dan Marsden, University of Nottingham, Suurbitannia.
Jälgi avalikku kaitsmist Zoomis
Meeting ID: 914 2400 2350
Passcode: 284140