Hyppää sisältöön
    • Suomeksi
    • In English
Trepo
  • Suomeksi
  • In English
  • Kirjaudu
Näytä viite 
  •   Etusivu
  • Trepo
  • Opinnäytteet - ylempi korkeakoulututkinto
  • Näytä viite
  •   Etusivu
  • Trepo
  • Opinnäytteet - ylempi korkeakoulututkinto
  • Näytä viite
JavaScript is disabled for your browser. Some features of this site may not work without it.

Modaalilogiikka ja lokaalit algoritmit

Heiman, Damian (2020)

 
Avaa tiedosto
HeimanDamian.pdf (340.4Kt)
Lataukset: 



Heiman, Damian
2020

Matematiikan maisteriohjelma - Master´s Programme in Mathematics
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2020-05-18
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202005135291
Tiivistelmä
Tässä tutkielmassa tutkitaan modaalilogiikan yhteyksiä lokaaleihin algoritmeihin. Modaalilogiikka on lauselogiikan laajennus, jossa kaavojen totuutta tutkitaan mahdollisia maailmoja mallintavissa Kripke-malleissa. Lokaalit algoritmit ovat graafeissa ajettavia algoritmeja, jotka päättyvät vakioajassa. Algoritmeilla ratkaistaan graafiongelmia, joille esitetään luokittelu sen mukaan, voidaanko ne ratkaista vakioajassa ja miten paljon informaatiota algoritmit tarvitsevat niiden ratkaisemiseksi. Vakioaikaiset graafiongelmaluokat karakterisoidaan modaalilogiikoiden avulla samaistamalla syötegraafit sopiviin Kripke-malleihin. Tutkielma keskittyy heikkoihin hajautetun laskennan malleihin, jotka hyödyntävät graafeihin lisättäviä porttinumerointeja, ja laajentaa aiempia niitä koskevia tuloksia tarkastelemalla, miten tulokset yleistyvät yksinkertaisista graafeista suunnattuihin graafeihin. Tuloksien todistamiseen käytetään bisimulaatiota, joka liittää toisiinsa Kripke-mallit, joita modaalilogiikka ei erota toisistaan. Erityisesti osoitetaan, että graafiongelmaluokkien välinen hierarkia on suunnattujen graafien tapauksessa heikompi kuin yksinkertaisten graafien tapauksessa. Osa luokkien välisistä inkluusioista ei päde, kun rajoitus yksinkertaisiin graafeihin poistetaan.
Kokoelmat
  • Opinnäytteet - ylempi korkeakoulututkinto [40001]
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste
 

 

Selaa kokoelmaa

TekijätNimekkeetTiedekunta (2019 -)Tiedekunta (- 2018)Tutkinto-ohjelmat ja opintosuunnatAvainsanatJulkaisuajatKokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste