Otsikkokuva

Tietokonepalsta: Kuinka Fibonaccin lukuja lasketaan

Solmun tietokonepalstalla tutkitaan, mitä tekemistä matematiikalla ja tietotekniikalla on keskenään. Ensimmäisenä tulee varmaan mieleen tietokoneiden käyttö laskennassa ja visualisoinnissa, siis tietotekniikan soveltaminen matematiikkaan. Alojen syvempää yhteyttä valottaa se, miten matematiikkaa käytetään tietotekniikassa. Sitä esittelee tämä ensimmäinen osa.

Algoritmi

Tällä kertaa tutkitaan yhden esimerkin avulla algoritmin käsitettä sekä hieman siihen liittyvää matematiikkaa. Algoritmi on lyhyesti sanottuna "resepti", jonka avulla tietokone osaa suorittaa jonkin tehtävän, esimerkiksi järjestää joukon lukuja tai valita tekstikappaleen rivinvaihdot niin, että tulos on jonkin kriteerin mielessä optimaalinen. Algoritmin toteuttaa yleensä tietokoneohjelma tai ohjelman osa, mutta ei millainen tahansa: vaadimme, että ohjelma pysähtyy ja antaa oikean tuloksen. (Tämän määritelmän mukaan esimerkiksi ydinvoimalan valvontaohjelma ei välttämättä toteuta mitään algoritmia, sillä sen ei kuulu pysähtyä eikä tuottaa mitään lopputulosta vaan vastata ärsykkeisiin järkevällä tavalla. Kuitenkin se luultavasti sisältää algoritmeja: esimerkiksi yksi sen aliohjelma saattaisi tutkia, antavatko reaktorista saadut mittaukset aihetta hälytykseen.)

Tämän artikkelin ymmärtämiseksi lukijan täytyy tuntea ohjelmoinnin alkeet ja jokin lausekieli, esimerkiksi Ada, Java (Java on Sunin rekisteröity tavaramerkki) tai C. Emme tässä kirjoita algoritmeja millään tällaisella kielellä, vaan esitämme ne eräänlaisella pseudokielellä, jollaista jokainen perusteet tunteva osaa toivottavasti lukea. Merkinnöistä on syytä huomata, että ilmaisemme lohkorakenteen pelkästään sisennyksellä (Pythonin tapaan) ja sijoituksen symbolilla :=

Algoritmien vertailuperusteita

Saman tehtävän voi yleensä ratkaista usealla erilaisella algoritmilla, mutta mikä tahansa algoritmi ei sovi käytännön ratkaisuksi. Hyvä algoritmi ei tuhlaa aikaa eikä tilaa.

Tärkein algoritmin aikavaatimukseen vaikuttava seikka on tietysti syöte, joka tiivistetään nopeustarkasteluissa yleensä yhteen lukuun. Tavallisesti tarkastellaan syötteen kokoa, mutta joskus jokin muu sen monimutkaisuuden tunnusluku voi olla olennaisempi. Suoritusaika riippuu tietysti myös käytetystä tietokoneesta, ohjelmointikielestä, muista ajossa olevista ohjelmista ja niin edelleen. Koska tällaiset tekijät vaikeuttaisivat analyysiä tarpeettomasti, ne "abstrahoidaan pois" tekemällä yksinkertaistavia oletuksia.

Tärkein oletus on, että algoritmi suoritetaan peräkkäisten alkeisoperaatioiden sarjana, ja että jokainen alkeisoperaatio vie vakioajan. Kertolasku voi olla kymmenen kertaa hitaampi kuin yhteenlasku, mutta tästä ei välitetä - tärkeää on, että alkeisoperaatioiden aikavaatimukselle on jokin yläraja.

Edelleen unohdetaan jopa alkeisoperaatioiden tarkka lukumäärä ja lasketaan asymptoottinen aikavaatimus. Jos syötteen koolla n tarvitaan 3n2+5n-1 alkeisoperaatiota, sanotaan vain, että aikavaatimus on luokkaa n2, sillä molemmat n:n funktiot kasvavat suunnilleen yhtä nopeasti. Kirjoitamme tämän kaavana 3n2+5n-1=Theeta(n2).

Matemaatikon täytyy tietysti määritellä, mitä "suunnilleen yhtä nopeasti" tarkoittaa. Kun g on funktio luonnollisilta luvuilta ei-negatiivisille reaaliluvuille, merkitsemme Theeta(g(n)):llä niiden funktioiden f luokkaa, jotka eroavat g:stä vain vakiokertoimella:

Theeta(g(n)) = {f:N->R+ | on olemassa positiiviset vakiot c1, c2, joille c1*g(n) <= f(n) <= c2*g(n) suurilla n}
Sanonta "suurilla n" tarkoittaa, että epäyhtälöparin ei tarvitse olla tosi aivan kaikilla n, vaan vain kaikilla n>n0, missä n0 on jokin luonnollinen luku. (Tavallisesti f tarkoittaa funktiota ja f(n) funktion f arvoa luvulla n. Tietojenkäsittelytieteessä on kuitenkin vakiintunut käytäntö kirjoittaa Theeta(f(n)) kuten yllä. Merkinnän etu nähdään, kun f:n paikalla on konkreettinen funktio: voidaan puhua vaikkapa luokasta Theeta(2n) ilman monimutkaisia kiertoteitä.)

Silloin kun Theeta-merkintä esiintyy yhtälön oikealla puolella, sovitaan että =-merkki tarkoittaakin merkkiä "kuuluu joukkoon". Siis f(n)=Theeta(g(n)) tarkoittaa, että f(n) voidaan "puristaa" c1g(n):n ja c2g(n):n väliin, kunhan n:n annetaan kasvaa tarpeeksi suureksi. Voidaan myös ajatella, että Theeta(g(n)) tarkoittaa jotain edellä määritellyn joukon funktiota, jota ei vain nimetä tarkkaan.

Theeta:n määritelmä sisältää kaksi epäyhtälöä. Jos jommastakummasta luovutaan, merkitään O tai Oomega:

O(g(n)) = { f:N->R+ | on olemassa positiivinen vakio c, jolle c*g(n) <= f(n) suurilla n }
ja
Oomega(g(n)) = { f:N->R+ | on olemassa positiivinen vakio c, jolle f(n) <= c*g(n) suurilla n }
Niitä käytetään samalla tavalla kuin Theeta:aa. Siinä missä Theeta vastaa suunnilleen merkkiä "likimain yhtäsuuri kuin". O on <= ja Oomega on >=.

Algoritmin tilavaatimus tarkoittaa sen tarvitsemien tietokoneen muistipaikkojen lukumäärää. Sitä voidaan myös tutkia asymptoottisesti, mutta se on monesti kiinnostava tarkemminkin - muistin käyttäminen on tyypillisesti melko hidasta, varsinkin jos tilaa kuluu niin paljon että joudutaan turvautumaan levymuistiin.

Harjoitustehtäviä

  1. Osoita, että
    1. 5n+8 = Theeta(n),
    2. 0,000001n2 = Theeta(100n2+10000n),
    3. 10 = Theeta(1) ja
    4. log2(n) = Theeta(log1998(n)).
    (Yllä 10 ja 1 tarkoittavat oikeastaan vakiofunktioita, jotka kuvaavat n:n aina samalle luvulle.) Käytännössä Theeta:n "sisään" kirjoitettava funktio pyritään valitsemaan mahdollisimman yksinkertaiseksi, ja esimerkiksi logaritmin kantalukua ei merkitä.
  2. Osoita, että
    1. f(n) = Theeta(f(n)),
    2. f(n) = Theeta(g(n)) jos ja vain jos g(n) = Theeta(f(n)) ja
    3. jos f(n) = Theeta(g(n)), g(n) = Theeta(h(n)), niin f(n) = Theeta(h(n))
    kaikilla funktioilla f, g ja h.
  3. Osoita, että
    1. 10000 = O(n),
    2. n = O(n5),
    3. log n = O(n) ja
    4. n = O(nlog n).
    (Tässäkään logaritmin kantaluvulla ei ole väliä.)
  4. Osoita, että f(n) = O(g(n)) jos ja vain jos g(n) = Oomega(f(n)).
  5. * Etsi sellaiset funktiot f ja g, että ei päde f(n)=O(g(n)) eikä f(n)=Oomega(g(n)).

Esimerkki: Fibonaccin luvut

Tässä artikkelissa tutkitaan esimerkkinä muutamaa algoritmia, joilla lasketaan Fibonaccin lukuja. Ongelma on yksinkertainen: on annettu luku n, ja on laskettava F(n), missä F(n) määritellään palautuskaavalla

F(n+2) = F(n) + F(n+1), kun n >= 0,
ja alkuehdoilla
F(0) = 0, F(1) = 1.

Algoritmien aikavaatimuksia on luonnollista tarkastella n:n funktioina.

Harjoitustehtävä

  1. Laske kymmenen ensimmäistä Fibonaccin lukua F(0), ..., F(9).

Naiivi algoritmi

Ensimmäinen algoritmimme naiivi-fibonacci perustuu suoraan määritelmään: jos n on 0 tai 1, palautetaan määritelmästä saatava arvo, muuten lasketaan rekursiivisesti F(n-1) ja F(n-2) ja summataan tulokset.

On tärkeää varmistua, että algoritmin suoritus päättyy. Tämä nähdään induktiolla: Jos n <= 1, asia on selvä. Muussa tapauksessa nojataan siihen, että suoritus päättyy parametrin arvoilla n-2 ja n-1.

Tämä algoritmi on siinä mielessä elegantti, että se muistuttaa Fibonaccin lukujen määritelmää. Se kuvaa, mitä lasketaan, eikä siitä edes näe aivan helposti, miten laskenta tapahtuu. Kuten kohta huomaamme, algoritmi on toivottoman hidas - tämä on liian korkean tason ohjelmointia tavalliselle lausekielelle. (On ohjelmointikieliä, esimerkiksi Prolog, joilla ohjelmoidaan juuri tällä tavalla.)

Merkitään algoritmin aikavaatimusta T(n):llä. Jos n <= 1, T(n) on vakio; muuten T(n) = T(n-2)+T(n-1)+vakio. Ilmeisesti T(n)=Oomega(F(n)). Myöhemmin nähdään, että F(n)=Theeta(fiin), missä fii > 1, joten tämän algoritmin aikavaatimus on vähintään eksponentiaalinen! (Itse asiassa T(n)=Theeta(F(n)), mutta toisen suunnan todistaminen on hieman työläämpää, eikä se ole kovin kiinnostavaa - jos aikavaatimus on eksponentiaalinen, algoritmi on käytännössä aivan liian hidas.)

Harjoitustehtäviä

  1. Kokeile algoritmin naiivi-fibonacci toimintaa paperilla. Kuinka suurilla n sen saa laskettua järkevässä ajassa?
  2. Toteuta algoritmi naiivi-fibonacci jollain tuntemallasi lausekielellä. Kuinka suurilla n jaksat odottaa ohjelman suorituksen loppumista?
  3. * Mikä on tämän algoritmin asymptoottinen tilavaatimus? (Montako lukua joudut pitämään yhtä aikaa paperilla, kun kokeilet algoritmin toimintaa?)

Silmukka

Rekursiivisen algoritmin vika on, että se "unohtaa" tietoa. Kokeilepa laskea vaikka F(10): todennäköisesti kirjoitat paperille peräkkäisiä Fibonaccin lukuja, niin että et joudu laskemaan samoja lukuja uudestaan. Itse asiassa riittää muistaa kaksi edellistä lukua: aloitetaan F(0):sta ja F(1):stä, lasketaan F(2), sitten F(1):n ja F(2):n avulla F(3) jne.

Olkoon aluksi a=F(0)=0 ja b=F(1)=1. Silmukan k:nnen kierroksen jälkeen haluamme muuttujien arvoiksi a=F(k) ja b=F(k+1). Muuttujan a uusi arvo on suoraan b:n vanha arvo, ja b:n uusi arvo on a:n ja b:n vanhojen arvojen summa.

Alkutoimenpiteisiin kuluu vakion verran aikaa, samoin silmukan yhdellä kierroksella. Kierroksia on n-1, joten algoritmin aikavaatimus on

vakio + (n-1)vakio = Theeta(n).
Tilaakin kuluu vain vakiomäärä.

Harjoitustehtäviä

  1. Kokeile algoritmin silmukka-fibonacci toimintaa paperilla. Vastaako tämä sitä, miten lasket Fibonaccin lukuja käsin?
  2. Toteuta algoritmi silmukka-fibonacci jollain lausekielellä. Onko tämä algoritmi havaittavasti nopeampi kuin naiivi-fibonacci?

Matriisien laskutoimituksiin perustuva algoritmi

Nyt pääsemme lopulta käyttämään apuna matematiikkaa. Seuraavan algoritmin ymmärtäminen vaatii lineaarialgebran perustietoja sen verran, että matriisien kertolasku on tuttu asia.

Edellisessä algoritmissa on kaksi muuttujaa, joita päivitetään joka kierroksella. Jos muuttujat ajatellaan 2-vektorin alkioiksi, päivitys on lineaarimuunnos: jos ohjelmointikielessämme voisi käyttää matriisioperaatioita, päivityksen voisi kirjoittaa sijoituksena

[a; b] := M [a; b], missä M = [0 1; 1 1].
Toisin sanoen peräkkäisistä Fibonaccin luvuista muodostetuille 2-vektoreille pätee sääntö
[F(k+1); F(k+2)] = M [F(k); F(k+1)]
ja algoritmi käyttää tämän säännön induktiivista yleistystä
[F(n-1); F(n)] = M^(n-1) [F(0); F(1)].

Jos matriisin M voisi korottaa potenssiin n-1 nopeammin kuin kertomalla se itsellään n-2 kertaa, olisi ongelmaamme löydetty nopeampi ratkaisu. Tietysti matriisit pitää esittää jonakin tietorakenteena, ja niiden kertolasku pitää toteuttaa, mutta tämä on 2*2-matriisien tapauksessa helppoa, emmekä keskity tähän seikkaan enempää vaan käytämme pseudokielessämme vapaasti matriisimuuttujia. (Suurten matriisien esittäminen ja kertolasku ei sen sijaan ole triviaalia.) Merkitsemme matriisien kertolaskua tavalliseen tapaan kirjoittamalla kerrottavat vierekkäin.

Potenssilasku

Tässä aliluvussa yritämme löytää nopean tavan laskea matriisien potensseja. Tavoite on laskea Mn-1, mutta koska potenssilaskualgoritmi voi olla hyödyllinen muutenkin, muotoilemme tehtävän siistimmin: on laskettava Ak, missä A on matriisi ja k >= 0 kokonaisluku.

Voisiko matriisipotenssin laskea nopeammin kuin k-1 kertolaskulla? Kokeile: Laske M2, M4 ja M8. Montako matriisikertolaskua tarvitsit? Entä montako tavallisten lukujen kertolaskua tarvitset laskiessasi lukua 78?

Seuraavassa esityksessä ei oikeastaan ole mitään merkitystä sillä, että potenssiin korotettavat oliot ovat matriiseita - algoritmi toimii myös luvuille. (Oikeastaan tarkastelu pätee minkä tahansa ryhmän alkioille - olennaista on kertolaskun assosiatiivisuus, s.o. laki (AB)C=A(BC). Ilman tätä ominaisuutta potenssimerkintäkään ei ole järkevä.)

Luultavasti huomasit, että M8:n laskemiseen tarvitaan vain kolme kertolaskua:

M^8 = [1 1; 1 2]^4 = [2 3; 3 5]^2 = [13 21; 21 34]
Samalla tavalla saadaan laskettua Ak helposti, jos k on kahden potenssi. Muussa tapauksessa tilanne on monimutkaisempi, mutta ratkaisun voi yleistää.

Yritetään induktiivista lähestymistapaa: Kuvitellaan, että Aj osataan laskea, kun j<k, ja mietitään Ak:n laskemista. Jos k on parillinen, voidaan soveltaa edellisen kappaleen ideaa: lasketaan Ak/2 ja kerrotaan se itsellään. Jos taas k on pariton, niin varmasti k-1 on parillinen, ja Ak = A Ak-1. Saadaan algoritmi rekursiivinen-potenssi.

Aikavaatimuksen laskemiseksi kirjoitetaan k binäärilukuna. Jokaisella kerralla aliohjelman kutsuessa itseään k:n binääriesityksen lopusta joko katoaa nolla (jos k on parillinen, se jaetaan kahdella) tai muuttuu ykkönen nollaksi (jos k on pariton, siitä vähennetään 1). Kutsuja on siis yhteensä

(k:n binääriesityksen numeroiden määrä-1) + (k:n binääriesityksen ykkösten määrä-1) + 1 = Theeta(log k).

Algoritmin tilavaatimus on myös Theeta(log k) rekursiivisten kutsujen takia. Tilan kulutus on "piilossa", mutta jokainen rekursiivinen kutsu jättää muistiin tiedon siitä, mitkä ovat muuttujien arvot kutsuvassa aliohjelmassa. Tässä tapauksessa rekursio voidaan muuntaa silmukaksi, joka tekee aivan samat laskutoimitukset mutta aloittaa suoraan pienimmistä A:n potensseista ja kokoaa niistä Ak:n. Ei ole aivan ilmiselvää, miten tämä tehdään, ja ohjelmoinnin harrastajan kannattaakin jäädä miettimään asiaa hetkeksi ennen kuin jatkaa lukemista.

Seuraavassa ratkaisussa käytämme apuna invariantin käsitettä. Nimensä mukaisesti invariantti on jokin muuttumaton asia - tässä tarkoitamme sillä erästä lauseketta, jonka arvo on sama ennen silmukan kutakin "kierrosta" ja sen jälkeen. Käytämme apumuuttujaa X, jonka arvona on aluksi identiteettimatriisi, ja pyrimme säilyttämään invarianttina lausekkeen X Ak. Tavoitteemme on muuttaa jokaisella kierroksella X:n, A:n ja k:n arvoa niin, että k:n arvo pienenee aina ja invariantti pysyy samana. Lopulta k=0, ja silloin X on haluttu vastaus. Jos merkitsemme Ai:llä, Xi:llä ja ki:llä muuttujien arvoja silmukan i:nnen kierroksen lopussa, invarianssiehdosta seuraa yhtäsuuruuksien ketju

X0 A0k0 = X1 A1k1 = ... = Xt Atkt,
missä X0 on identiteettimatriisi ja kt=0.

Lähdetään siis muodostamaan algoritmia. Jotta se toimii samalla tavalla kuin rekursiivinen-potenssi, valitsemme silmukan kierroksella suoritettavat operaatiot k:n parillisuuden mukaan, ja joko jaamme k:n kahdella tai vähennämme siitä ykkösen. Jos k on parillinen, invarianssiehto voidaan nyt kirjoittaa muotoon

Xi Aiki = Xi+1 Ai+1ki/2,
ja se saadaan voimaan asettamalla Ai+1 = Ai2 ja Xi+1 = Xi. Jos taas k on pariton, ehto on muotoa
Xi Aiki = Xi+1 Ai+1ki-1,
minkä toteuttamiseksi valitaan Ai+1=Ai ja Xi+1=XiAi.

Siinä olikin jo kaikki! Kun invariantti oli valittu hyvin, algoritmia kirjoittaessa meille ei jäänyt juurikaan vaihtoehtoja. Ensi katsomalta iteratiivinen-potenssi voi olla vaikea ymmärtää; avain on invariantti X Ak.

Harjoitustehtäviä

  1. Kirjoita aliohjelma matriisipotenssi-fibonacci, joka laskee Fibonaccin lukuja käyttämällä apuna aliohjelmaa iteratiivinen-potenssi. Joudut antamaan matriisimuuttujille alkuarvoja tavallisten skalaarimuuttujien avulla; kirjoita yksinkertaisesti tyyliin
    A := [x y; z w]
    äläkä murehdi siitä, miltä tämä näyttäisi todellisessa ohjelmointikielessä.
  2. Toteuta äskeinen algoritmi jollain lausekielellä. Pidä matriiseja joko tietorakenteissa tai neljässä muuttujassa, mutta tee yleiskäyttöiset aliohjelmat 2*2-matriisien kerto- ja potenssilaskua varten. Vinkki: 2*1-matriisia ei tarvitse toteuttaa erikseen, vaan voit käyttää 2*2-matriisia, jonka toinen pystyvektori sisältää vain nollia. Testaa aliohjelmiasi helpoilla matriisilaskuilla ja kokeile myös pääohjelman toimintaa. Huomaatko nopeuseroa algoritmiin silmukka-fibonacci?
  3. * Jos sinulla on käytössäsi sellaisen kielen tulkki tai kääntäjä, jossa voi laskea mielivaltaisen suurilla kokonaisluvuilla, tai jos osaat toteuttaa vastaavat toiminnot itse, kirjoita algoritmit silmukka-fibonacci ja matriisipotenssi-fibonacci niin että ne toimivat mielivaltaisilla n. Kuinka suurilla n huomaat nopeuseron? Miksi asymptoottisen aikavaatimuksen laskeminen muuttuukin vaikeammaksi tässä tapauksessa?
  4. Kuvitellaan, että ohjelmointikielessämme kokonaisluvuille on vain kolme laskutoimitusta: kahden luvun yhteenlasku, luvun kertominen kahdella ja parillisen luvun jakaminen kahdella. Lisäksi voidaan testata, onko luku parillinen vai ei. Kirjoita logaritmisessa ajassa toimiva ohjelma, joka kertoo kaksi kokonaislukua keskenään.
  5. Osoita, että matriisin
    M = [0 1; 1 1]
    potenssit ovat muotoa
    [p q; q p+q]
    Kirjoita algoritmi uudestaan sellaiseen muotoon, että se ei pidä muistissa koko matriisia vaan vain luvut p ja q.
  6. * (Lineaarialgebran tuntijoille) Mitkä ovat matriisin M ominaisarvot ja -vektorit? Miten niitä voi hyödyntää matriisipotenssin laskemisessa vielä nopeammin?

Differenssiyhtälö

Vielä nopeamman algoritmin löytämiseksi jatkamme Fibonaccin lukujonon ominaisuuksen tutkimista. Jonon määrittelevät differenssiyhtälö

F(n+2) = F(n+1) + F(n)
sekä alkuehdot F(0)=0, F(1)=1. Yritetään löytää F(n):lle lauseke

Tehdään nyt rohkea arvaus, että Fibonaccin luvut saadaan jonkin luvun r potensseina: F(n)=rn. Jos näin on, r:lle saadaan differenssiyhtälöstä ehto

rn+2 - rn+1 - rn = rn(r2-r-1) = 0.
Siis r:n on oltava joko 0 tai toisen asteen yhtälön r2-r-1=0 ratkaisu. Nämä ratkaisut ovat fii = (1 + sqrt(5))/2 ja psii = (1 - sqrt(5))/2. Valitettavasti kumpikaan näistä ei tuota Fibonaccin lukuja, joten arvauksemme oli väärä.

Olemme silti havainneet tärkeän asian: n:n funktiot fiin ja psiin toteuttavat differenssiyhtälön. Nyt voimme nimittäin konstruoida niiden avulla lisää ratkaisuja. Ensinnäkin, jos G(n) on differenssiyhtälön ratkaisu, niin on myös C G(n) jokaisella vakiolla C. Toiseksi kahden ratkaisun summa on myös ratkaisu. Nämä tiedot yhdistämällä saamme parametroidun ratkaisun

C1 fiin + C2 psiin.

Jos nyt saadaan määrättyä sellaiset vakiot C1 ja C2, että alkuehdot F(0)=0, F(1)=1 toteutuvat, on löydetty lauseke F(n):lle. Saadaan yhtälöpari

C1 + C2 = 0,
C1fii + C2psii = 1,
jonka ratkaiseminen on helppoa: C1 = 1/sqrt(5), C2 = -1/sqrt(5).

Koska |psii|<1, toisen termin vaikutus johtamassamme lausekkeessa pienenee nopeasti n:n kasvaessa. Kun n >= 0,

|C2psiin| < 1/2,
joten riittää laskea vain merkitsevämpi termi C1fiin ja pyöristää se lähimpään kokonaislukuun.

Nyt olemme siis löytäneet hyvin yksinkertaisen algoritmin potenssilasku-fibonacci, joka toimii vakioajassa kaikilla n; sen aikavaatimus on siis Theeta(1).

Tällä algoritmilla on kuitenkin se rajoitus, että sen suorittamiseksi täytyy laskea reaaliluvuilla. Useimmat ohjelmointikielet ja tietokoneet tukevat ns. liukulukuja, joilla voi tehdä reaalilukujen laskutoimituksia likimääräisesti. Algoritmimme voi hyödyntää liukulukulaskentaa melko hyvin, koska siinä joka tapauksessa tehdään lopuksi pyöristys: voimme toivoa, että laskennassa tapahtuvat virheet ovat niin pieniä, että ne eivät vaikuta lopputulokseen. Tällaisia asioita ei ole kuitenkaan aivan helppo todistaa.

Harjoitustehtäviä

  1. Toteuta algoritmi potenssilasku-fibonacci jollain lausekielellä. Tutki, miten suurilla n:n arvoilla saat vielä oikeita kokonaislukuja vastaukseksi.
  2. *
    1. Ratkaise differentiaaliyhtälöt
      1. f''(x) + f'(x) - f(x) = 0,
      2. f''(x) + f'(x) - f(x) = 1,
      3. f''(x) + f'(x) - f(x) = x,
      4. f''(x) + 2f'(x)+ f(x) = 0 ja
      5. f''(x) + f'(x) + f(x) = 0.

      Etsi sekä yleiset ratkaisut että ratkaisut alkuehdoilla f(0)=1, f'(0)=2.

    2. Ratkaise differenssiyhtälöt
      1. F(n+2) + F(n+1) - F(n) = 0,
      2. F(n+2) + F(n+1) - F(n) = 1,
      3. F(n+2) + F(n+1) - F(n) = n,
      4. F(n+2) + 2F(n+1)+ F(n) = 0 ja
      5. F(n+2) + F(n+1) + F(n) = 0.

      Etsi sekä yleiset ratkaisut että ratkaisut alkuehdoilla F(0)=1, F(1)=2.

Loppusanat

Olemme nähneet, että tietokoneohjelmaa voi nopeuttaa paljon suunnittelemalla sen hyvin. Aina ei tietenkään saavuteta näin dramaattista tulosta: aikavaatimus parani toivottomasta eksponentiaalisesta varsin hyvään logaritmiseen, tai eräillä ehdoilla vakioksi. Toivottavasti lukija on huomannut, että matematiikka ei ole tietojenkäsittelijälle lainkaan turha tieteenala.

Kirjallisuutta

Abelson, Harold; Sussman, Gerald Jay: Structure and Interpretation of Computer Programs, MIT Press 1996.
Tämä kirja esittelee ohjelmoinnin alkeita monipuolisesti Scheme-kielellä ja etenee varsin pitkälle. Suosittelen innokkaalle harrastajalle: jos olet tottunut tavallisiin lausekieliin, Scheme voi olla vaikea omaksua, mutta silloinhan se avartaa maailmankuvaasi.
Cormen, Thomas; Leiserson, Charles; Rivest, Ronald: Introduction to Algorithms, MIT Press 1990.
Jos ymmärrät ohjelmoinnin ja tietorakenteiden alkeet (esimerkiksi linkitetyt listat) ja matematiikkaa sen verran, että selviät induktiotodistuksista, suosittelen. Tämä on laaja yleisteos, josta on iloa myöhemminkin.
Kaldewaij, Anne: Programming: The Derivation of Algorithms, Prentice-Hall 1990.
Varsin erilainen lähtökohta algoritmien suunnitteluun on niiden johtaminen vaatimuksista, mistä nähtiin pieni vilaus algoritmin iteratiivinen-potenssi yhteydessä. Tätä kirjaa voi suositella logiikan harrastajalle, joka tuntee ohjelmointia enemmän kuin aivan alkeiden verran, tai ohjelmoijalle, joka on kiinnostunut logiikasta.

Jouni Seppänen
[email protected]


Solmu 1/1998-1999
Viimeksi muutettu: 5. marraskuuta 1998 klo 23:51:24