Kommunikaatiokompleksisuus
351.31 KB
avoin
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Lataukset228
Pysyvä osoite
Verkkojulkaisu
DOI
Tiivistelmä
LuK-Tutkielmassa tutustutaan kommunikaatiokompleksisuuteen, eli siihen miten ongelmia, joiden ratkaiseminen edellyttää kahden eri tahon välistä viestintää voidaan tutkia. Tutkielmassa esitellään kommunikaatioprotokollat, ongelmasta riippuva yläraja protokollille, kaksi eri alarajatekniikkaa protokollan kompleksisuudelle ja sivutaan epädeterministisiä kommunikaatioprotokollia ja niihin liittyvää avointa ongelmaa deterministisen- ja epädeterministisen kommunikaatiokompleksisuuden välisestä yhteydestä. Tutkielma seuraa Kushilevitzin ja Nisanin Communication Complexity (1997) kahta ensimmäistä lukua.