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

Tietojenkäsittelyteoria, kevät 2000
Harjoitus 8, to 16.3. klo 10-12 sali MaD381

  1. Sanotaan, että Monte Carlo -tyyppinen satunnaisalgoritmi A on luotettava, jos se annetulla syötteellä antaa oikean vastauksen todennäköisyydellä p > 0, ja todennäköisyydellä q = 1-p vastaa ``en tiedä''. Mikä on oikean vastauksen todennäköisyys, kun algoritmi A suoritetaan k kertaa peräkkäin? (Oletetaan, että suorituskerrat ovat toisistaan riippumattomia, ja toisto lopetetaan heti kun oikea vastaus on saatu.) Montako kertaa algoritmia tarvitsee enintään toistaa, jotta oikean vastauksen todennäköisyys saataisiin suuremmaksi kuin tex2html_wrap_inline730 , jollakin annetulla tex2html_wrap_inline732 ?

  2. Muodostetaan edellisen tehtävän algoritmin A pohjalta Las Vegas -tyyppinen algoritmi B, joka toistaa A:ta, kunnes saa oikean vastauksen (so. A vastaa jotakin muuta kuin ``en tiedä''). Mikä on tarvittavien toistojen määrän odotusarvo?
  3. Olkoon A jonkin päätösongelman ratkaiseva (so. 0/1-arvoinen) Monte Carlo -algoritmi, joka antaa oikean vastauksen todennäköisyydellä p > 1/2 ja väärän vastauksen todennäköisyydellä q = 1-p. (Tällä kertaa algoritmi ei siis vastaa luotettavasti ``en tiedä'', vaan saattaa suorastaan valehdella.) Muodostetaan algoritmista A algoritmi B, joka toistaa A:ta k = 2t-1 kertaa ja valitsee vastaukseksi sen, jonka A antoi useammin, so. vähintään t kertaa. Arvioi todennäkoisyyttä, että B antaa väärän vastauksen, kun A:n eri suorituskerrat ovat toisistaan riippumattomia. Erityisesti: monellako A:n toistolla saadaan väärän vastauksen todennäköisyys pienemmäksi kuin jokin annettu tex2html_wrap_inline732 ?
  4. Todista seuraavat hyppylistojen ominaisuudet:
    1. n alkion hyppylistan alkioiden maksimikorkeus on ``suurella todennäköisyydellä'' enintään tex2html_wrap_inline770 .
    2. Kahden korkeutta h olevan alkion välissä on odotusarvoisesti O(1) korkeutta h-1 olevaa alkiota. (Vihje: Huomaa, että jos alkion x korkeus on vähintään h-1, niin todennäköisyydellä 1/2 sen korkeus on itse asiassa h tai suurempi.)
  5. Todista binomijakauman ``alahäntää'' koskeva Chernoffin raja: kun tex2html_wrap_inline786 ja tex2html_wrap_inline788 , niin

    displaymath714

  6. Lausekalkyylin kaava tex2html_wrap_inline790 on disjunktiivisessa normaalimuodossa (dnf), jos se on muotoa

    displaymath715

    missä kukin termi tex2html_wrap_inline792 on literaalien konjunktio

    displaymath716

    (Tässä siis kukin tex2html_wrap_inline794 on joko muuttuja tai sellaisen negaatio.) Laadi satunnaisalgoritmi, joka arvioi monellako muuttujien totuusarvoasetuksella annettu dnf-muotoinen kaava tex2html_wrap_inline790 tulee todeksi. (Vihje: Kukin kaavan termi tex2html_wrap_inline792 määrittelee tietyn toteuttavien totuusarvoasetusten joukon tex2html_wrap_inline800 , ja koko kaavan tex2html_wrap_inline790 toteuttavien asetusten joukko on näiden tex2html_wrap_inline800 -joukkojen yhdiste.) Lisätieto: Toteuttavien asetusten tarkan määrän laskeminen on ns. #P-täydellinen ongelma, siis luultavasti ei tehtävissä polynomisessa ajassa. (Funktio tex2html_wrap_inline806 kuuluu luokkaan #P, jos jollakin epädeterministisellä polynomisessa ajassa toimivalla Turingin koneella M on f(x) = M:n syötteellä x hyväksyvien laskentojen määrä.)


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

Pekka Orponen
Thu Mar 9 21:25:16 EET 2000