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

Algoritmien teoria, kevät 1999
Harjoitus 1, 25.1. klo 10-12 sali MaD302

  1. Määritä rekursioyhtälön

    eqnarray15

    tarkka ratkaisu, kun n on neljän potenssi.

  2. Eräissä ``hajota ja hallitse''-tyyppisissä algoritmeissa voidaan n:n kokoinen ongelman tapaus osittaa tasaisesti tex2html_wrap_inline55 :n kokoisiin osatapauksiin niin, että algoritmin aikavaativuutta T(n) tulee kuvaamaan rekursiokaava:

    displaymath47

    Määrää tex2html_wrap_inline63 -yläraja funktiolle T(n). (Vihje: Tee muuttujanvaihto tex2html_wrap_inline67 .)

  3. Ratkaise generoivia funktioita käyttäen rekursioyhtälö

    displaymath48

    (Vihje: Kun olet määrittänyt jonon tex2html_wrap_inline69 generoivan funktion, yritä kirjoittaa sen nimittäjänä oleva lauseke muotoon (1-az)(1-bz) ja sovella sitten osamurtolukuhajotelmaa.)

  4. Tiedetään (Anal. pk/jk), että nollan ympäristössä suppeneva potenssisarja voidaan derivoida termeittäin, so. jos tex2html_wrap_inline73 niin tex2html_wrap_inline75 .
    1. Johda tämän tiedon avulla jonon tex2html_wrap_inline77 generoiva funktio jonon tex2html_wrap_inline79 generoivasta funktiosta.
    2. Oletetaan, että jonon tex2html_wrap_inline81 arvot ovat jonkin diskreetin todennäköisyysjakauman pistetodennäköisyyksiä, siis esim. `` tex2html_wrap_inline83 = todennäköisyys, että algoritmin suoritus vaatii tasan k askelta''. Mitä on tällöin G(1)? Entä mikä on arvon G'(1) tulkinta?
  5. Ohjelma käsittelee kahta pinoa S ja T, joihin voidaan tavallisten pino-operaatioiden (push, pop) lisäksi kohdistaa kopiointi-operaatioita copy(S,T) ja copy(T,S). Suunnittele pinoille taulukkototeutus, jossa kopiointi-operaation yhteydessä ainoastaan edellisen kopioinnin jälkeen tapahtuneet muutokset päivitetään pinosta toiseen. Osoita, että tässä toteutuksessa minkä tahansa aluksi samansisältöisiin pinoihin kohdistuvan n operaation jonon kokonaissuoritusaika on vain O(n).



Pekka Orponen
Thu Jan 21 11:57:19 EET 1999