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

Algoritmiteorian jatkokurssi, kevät 1999
Harjoitus 2, 12.4. klo 10-12 sali MaD380

  1. Palautetaan mieleen, että funktio tex2html_wrap_inline651 on tilakonstruoituva, jos jollakin deterministisellä moninauhaisella Turingin koneella M on voimassa: tex2html_wrap_inline655 kaikilla syötejonoilla x. Todista seuraavat väitteet:
    1. Funktiot s(n) = k (vakio), s(n) = n ja tex2html_wrap_inline663 ovat tilakonstruoituvia.
    2. Jos tex2html_wrap_inline665 ja tex2html_wrap_inline667 ovat tilakonstruoituvia, niin myös tex2html_wrap_inline669 , tex2html_wrap_inline671 ja tex2html_wrap_inline673 ovat tilakonstruoituvia.
    3. Jokaisella rekursiivisella funktiolla r(n) on olemassa tilakonstruoituva tex2html_wrap_inline677 .
  2. Todista, että jokaisella tilakonstruoituvalla tex2html_wrap_inline679 on voimassa sisältyvyys

    displaymath649

    (Vihje: Muodosta verkko, jonka solmut ovat simuloitavan epädeterministisen koneen tilannekuvauksia.)

  3. Todista seuraava väite: Olkoon tex2html_wrap_inline681 ( tex2html_wrap_inline683 ), missä q on polynomi ja tex2html_wrap_inline687 ( tex2html_wrap_inline689 ), tex2html_wrap_inline691 . Olkoon tex2html_wrap_inline693 toinen polynomi. Tällöin on olemassa tex2html_wrap_inline695 ( tex2html_wrap_inline689 ), jolla tex2html_wrap_inline699 ( tex2html_wrap_inline701 ).
  4. Todista, että polynomisen aikavaativuushierarkian luokilla tex2html_wrap_inline689 , tex2html_wrap_inline705 , tex2html_wrap_inline691 on seuraavat sulkeumaominaisuudet (luentomuistiinpanojen Lause 2.8, s. 13):
    1. Jos tex2html_wrap_inline709 ( tex2html_wrap_inline705 ), niin tex2html_wrap_inline713 , tex2html_wrap_inline715 ( tex2html_wrap_inline705 ).
    2. Jos tex2html_wrap_inline719 ( tex2html_wrap_inline705 ) ja tex2html_wrap_inline723 , niin tex2html_wrap_inline725 ( tex2html_wrap_inline705 ).
    3. Jos tex2html_wrap_inline719 ( tex2html_wrap_inline705 ), tex2html_wrap_inline733 , ja tex2html_wrap_inline735 ( tex2html_wrap_inline737 ), q polynomi, niin tex2html_wrap_inline725 ( tex2html_wrap_inline705 ).
    (Sovitaan täsmällisyyden vuoksi, että polynomisen hierarkian luokkien määrittelyssä käytetään parikoodausfunktiota tex2html_wrap_inline745 , missä tex2html_wrap_inline747 , ja tästä edelleen johdettua jonokoodausfunktiota tex2html_wrap_inline749 .)

Huom.: Pääsiäisloman takia kurssilla ei ole ohjelmaa 5.4. eikä 7.4. Seuraavat demot ja luennot ovat maanantaina 12.4.



Pekka Orponen
Thu Apr 1 19:47:38 EET DST 1999