next up previous
Next: About this document Up: No Title Previous: No Title

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 tex2html_wrap_inline781 määritellään:

    displaymath779

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

    1. Jos syötteinä on käytettävissä sekä muuttujat tex2html_wrap_inline791 että niiden negaatiot tex2html_wrap_inline793 , niin mikä tahansa muuttujien tex2html_wrap_inline791 monomi (literaalien konjunktio) voidaan laskea yhdellä kynnysportilla tex2html_wrap_inline787 , tex2html_wrap_inline799 .
    2. Mikä tahansa n muuttujan Boolen funktio f voidaan laskea tex2html_wrap_inline805 -porttisella kynnyspiirillä. (Vihje: Laske ensin kaikki muuttujien tex2html_wrap_inline807 monomit. Tarkastele sitten funktion f dnf-esitystä ja eri monomien esiintymistä siinä.)
    3. Melkein kaikkien n muuttujan Boolen funktioiden laskeminen kynnyspiireillä vaatii tex2html_wrap_inline813 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. tex2html_wrap_inline819 , tex2html_wrap_inline821 riippumattomasti kaikilla tex2html_wrap_inline823 , tex2html_wrap_inline825 . 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 tex2html_wrap_inline831 , tex2html_wrap_inline833 , jos sillä on polynomisessa ajassa toimivan probabilistisen varmentajakoneen V ja k toisistaan riippumattoman todistusoraakkelin tex2html_wrap_inline839 muodostama monitodistusjärjestelmä (engl. multiprover interactive proof system), joka kaikilla tex2html_wrap_inline841 täyttää ehdot:

    eqnarray446

    KÄÄNNÄ

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

    1. tex2html_wrap_inline855 . (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. tex2html_wrap_inline859 . (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 tex2html_wrap_inline861 . Edelleen voidaan osoittaa (Babai, Fortnow, Lund 1991), että itse asiassa on tex2html_wrap_inline863 .
  4. Tarkastellaan oheisen kuvan esittämällä laudalla pelattavaa yksinkertaistettua Monopoli-peliä: tex2html_wrap865

    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).


next up previous
Next: About this document Up: No Title Previous: No Title

Pekka Orponen
Thu Apr 20 01:10:00 EET DST 2000