MAT340 Tietojenkäsittelyteoria (5 ov)
2. välikoe (kotikoe), 20.4.2000
Kuulustelija: Pekka Orponen

Tehtävien ratkaisemisen apuna saa käyttää mitä tahansa lähdemateriaalia; ratkaisut tulee kuitenkin laatia henkilökohtaisesti. Vastaukset palautetaan kuulustelijalle henkilökohtaisesti tai suljetussa kirjekuoressa huoneen MaD307 viereiseen postilaatikkoon tiistaihin 9.5. klo 14 mennessä.

1. Tarkastellaan Boolen funktioiden laskemista kynnysporttien (engl. threshold gate, perceptron) avulla. Kynnysfunktio määritellään:

   

   Kynnyspiiri (engl. threshold circuit, multilayer perceptron) on kombinaatiopiiri, jonka portteina voi olla mielivaltaisia kynnysfunktioita , . Todista seuraavat tulokset:

   1. Jos syötteinä on käytettävissä sekä muuttujat että niiden negaatiot , niin mikä tahansa muuttujien monomi (literaalien konjunktio) voidaan laskea yhdellä kynnysportilla , .
   2. Mikä tahansa n muuttujan Boolen funktio f voidaan laskea -porttisella kynnyspiirillä. (Vihje: Laske ensin kaikki muuttujien monomit. Tarkastele sitten funktion f dnf-esitystä ja eri monomien esiintymistä siinä.)
   3. Melkein kaikkien n muuttujan Boolen funktioiden laskeminen kynnyspiireillä vaatii porttia. (Vrt. Shannonin lause; täsmennä itse, mitä ``melkein kaikki'' tarkoittaa tässä yhteydessä.)
2. Olkoon G = (V, E) tasaisen kaarijakauman mukaan generoitu n solmun satunnaisverkko, so. , riippumattomasti kaikilla , . Todista Kolmogorov-kompleksisuutta käyttäen mahdollisimman tiukka ``suuren todennäköisyyden'' yläraja verkon G maksimaalisen klikin koolle.
3. Tarkastellaan seuraavaa vuorovaikutteisten todistussysteemien yleistystä. Kieli L kuuluu luokkaan , , jos sillä on polynomisessa ajassa toimivan probabilistisen varmentajakoneen V ja k toisistaan riippumattoman todistusoraakkelin muodostama monitodistusjärjestelmä (engl. multiprover interactive proof system), joka kaikilla täyttää ehdot:

   

   KÄÄNNÄ

   Näillä merkinnöillä on siis ja . Merkitään edelleen . Todista seuraavat luokkien MIP ja suhdetta koskevat väitteet:

   1. . (Ohje: Oraakkelien määrän lisäksi MIP- ja PCP-systeemeillä on se ero, että MIP-oraakkelit voivat ``muistaa'' aiemmat vastauksensa ja mukauttaa myöhemmän toimintansa niiden mukaan, kun taas PCP-oraakkelin vastaukset on kiinnitetty ennalta. Tämän tehtävän ideana on siis suunnitella koodaus, jolla k adaptiivisen oraakkelin kysymys/vastausjonot voidaan koodata yhteen kiinteään oraakkeliin.)
   2. . (Vihje: Käytä toista MIP-oraakkelia PCP-oraakkelin koodaukseen ja toista oraakkelia sen varmistamiseen, että ensimmäinen oraakkeli ei muuttele vastauksiaan.)
   Lisätieto: Edellisten tulosten nojalla on siis . Edelleen voidaan osoittaa (Babai, Fortnow, Lund 1991), että itse asiassa on .
4. Tarkastellaan oheisen kuvan esittämällä laudalla pelattavaa yksinkertaistettua Monopoli-peliä:

   Peliä pelataan noppien sijaan rahaa heittämällä siten, että kun rahanheiton tulos on ``kruuna'', pelaaja siirtyy yhden ruudun eteenpäin, ja kun tulos on klaava, hän siirtyy kaksi ruutua eteenpäin. Mallinna peli Markovin ketjuna ja määritä pelaajan eri ruuduille sijoittumistodennäköisyyksien tasapainojakauma äärettömän pitkässä pelissä. Määritä tämän jakauman ja lautaan merkittyjen eri ruutujen ``vuokrien'' perusteella, mikä on laudan paras ruutu (so. se, josta vastapelaaja pitkän ajan kuluessa joutuu odotusarvoisesti maksamaan eniten vuokraa).