Tehtävä:
Luvun 1.2 ohjelmat helppo ja nopea
Lyhyt
MathCheck-ohje (uuteen välilehteen)
Tässä tehtävässä tarkastellaan luentojen luvun 1.2 ohjelmia
helppo ja nopea .
Merkitsemme niiden muuttujan nn arvoa symbolilla `n`.
Muuttuja `n` voi saada arvokseen nollan tai positiivisen kokonaisluvun.
Kuinka monta paria `(i,j)`, missä `0 <= i < n` ja `0 <= j < n`,
on kaiken kaikkiaan olemassa?
Vihje
Mikä on neliön ala, jos sivun pituus on `x`?
Entä jos sivun pituus on `n`?
ok_text
Oikein!
hide_expr n^2 =
tai
Kuinka monessa edellä mainituista pareista `i=j` eli alkukohta on sama kuin
loppukohta?
ok_text
Oikein tämäkin!
hide_expr n =
tai
Kuinka monessa parissa alkukohta on eri kuin loppukohta?
Vihje
Muodosta vastaus edellisten kohtien vastausten
avulla.
ok_text
Näin on!
hide_expr n^2 - n =
tai
Kuinka monessa parissa alkukohta on aikaisemmin kuin loppukohta?
Vihje
Sellaisia pareja on yhtä paljon kuin sellaisia, joissa
alkukohta on myöhemmin kuin loppukohta.
Tiedät jo, paljonko näitä molempia on yhteensä.
ok_text
Hyvin sujuu!
hide_expr (n^2-n)/2 =
tai
Kuinka monta paria helppo kokeilee?
Vihje
for -silmukassa `i <= j < n`.
Siksi tulos on summa kahdesta aikaisemmin saamastasi tuloksesta.
ok_text
Niin kokeilee! Eikös ole aika paljon.
hide_expr (n^2+n)/2 =
tai
Luentojen mittauksissa käytetty tietokone kokeilee noin 215 miljoonaa paria
sekunnissa ajaessaan ohjelmaa helppo .
Miksi helppo käyttää useita sekunteja, kun `n >=`30 000?
Valitse seuraavista vaihtoehdoista.
only_no_yes_on hide_expr ok_text
Oikein arvasit. Tai tiesit ☺!
tai
Ohjelmien helppo ja nopea ajan kulutus riippuu
muustakin kuin kokeiltavien parien määrästä.
Silloin kun tavoitteena on osoittaa, että ohjelma on hidas, ei ole
välttämätöntä tarkastella kaikkea mitä se tekee.
Riittää, että osoitetaan, että ohjelma tekee ainakin nääääin paljon
asioita, joten aikaa kuluu ainakin nooooin paljon.
Siksi ohjelman helppo tarkastelu edellä on pätevä.
Mutta kun tavoitteena on osoittaa, että ohjelma on nopea, on tarkasteltava
kaikkea mitä se tekee.
Kattava tarkastelu on niin monimutkaista, että emme tee sitä tällä kertaa.
Opettaja on tehnyt kattavan tarkastelun ja lupaa, että ohjelmien
helppo ja nopea tapauksessa kokeiltavien parien määrän
tarkasteleminen antaa oikean yleiskäsityksen.
only_no_yes_on hide_expr ok_text
Vastauksesi kelpaa kyllä demotilaisuudessa!
tai
Ohjelman nopea ensimmäinen vaihe etsii takahuiput.
Kuinka monta paria se kokeilee?
Vihje
Se kokeilee `i`:n arvot `n-1`, `n-2`, …, `1`, `0`.
Jokaisella niistä se tekee yhden korkeusvertailun.
ok_text
Eikös ole aika vähän!
hide_expr n =
tai
ok_text
Ensimmäinen oikein, toista jännitetään …
hide_expr assume n>0;
n-1 =
Ensimmäinen vaihe kokeilee yhden parin turhaan.
Siinä `i =`
end_of_answer ok_text
Taidat olla ohjelmointiguru!
arithmetic
hide_expr assume n>0;
n-1 =
ja `th =` .
tai
Merkitään takahuippujen määrää symbolilla `m`.
Kuinka monta paria nopea :n toinen vaihe kokeilee enintään, jos
`m=1`?
ok_text
Olikohan tämä liian helppo?
hide_expr n =
tai
Kuinka monta paria nopea :n toinen vaihe kokeilee enintään, jos
`m=2`?
ok_text
Muuttuu hiljalleen vaikeammaksi …
hide_expr n+1 =
tai
Kuinka monta paria nopea :n toinen vaihe kokeilee enintään, jos
`m=5`?
ok_text
Vielä pysyt mukana!
hide_expr n+4 =
tai
Kuinka monta paria nopea :n toinen vaihe kokeilee enintään?
Nyt vastaus riippuu sekä `n`:stä että `m`:stä.
ok_text
Hyvin mietitty!
hide_expr assume 0 < m <= n; n+m-1 =
tai
Takahuippujen määrää ei välttämättä tiedetä etukäteen.
Siksi haluamme kokeiltavien parien määrälle ylälikiarvon, joka ei riipu
`m`:stä.
Milloin takahuippujen määrä on suurimmillaan?
only_no_yes_on hide_expr ok_text
Osaamisesi meneekin ylämäkeä!
tai
Kuinka monta takahuippua on enintään, eli kuinka suuri `m` voi enintään
olla?
Ilmaise vastaus `n`:n avulla.
Vihje
Kuinka monta takahuippua on silloin, kun reitti on
kokonaisuudessaan alamäkeä?
ok_text
Joo, niin on!
hide_expr assume 0 < m <= n; n =
tai
Kuinka monta paria nopea :n toinen vaihe kokeilee enintään?
Anna vastaus, joka voi riippua `n`:stä mutta ei riipu `m`:stä.
Vihje
Valitse `m`:lle se `n`:n avulla ilmaistu arvo, joka
maksimoi kokeiltavien parien määrän.
Sijoita se aikaisempaan lausekkeeseen, jossa esiintyvät sekä `n` että
`m`.
ok_text
Oliko vaikeaa?
hide_expr assume 0 < m <= n; 2n-1 =
tai
Kuinka monta paria nopea kokeilee enintään?
Anna vastaus, joka voi riippua `n`:stä mutta ei riipu `m`:stä.
Vihje
Tulos on summa parista aikaisemmasta vastauksesta.
ok_text
Olet ihan huippu!
hide_expr f_nodes 5 assume 0 < m <= n; 3n-1 =
tai
Ei ole mitattu, kuinka monta paria nopea kokeilee sekunnissa.
Koska nopea on monimutkaisempi kuin helppo , oletamme
tässä, että nopea kokeilee vain 100 miljoonaa paria sekunnissa.
Millä `n`:n arvolla nopea käyttää aikaa tasan yhden sekunnin?
Anna vastaus likiarvona, jossa on ensin kaksi muuta numeroa ja sitten nollia,
esim. 99000.
ok_text
Hyvin meni likiarvot!
hide_expr only_no_yes_on 33000000 =
tai
Kuinka paljon helppo käyttää aikaa, kun korkeusarvoja on
edellisen vastauksesi mukainen määrä?
Ilmoita vastaus vuorokausina pyöristettynä kahteen merkitsevään numeroon.
Vihje
Edellä ilmoitettiin, kuinka monta paria helppo
kokeilee sekunnissa.
Edellä olet johtanut kaavan, joka kertoo, kuinka monta paria tarvitsee
kokeilla.
Näistä saat tarvittavien sekuntien määrän.
Vuorokaudessa on 86400 sekuntia.
ok_text
Loistavaa! Sait tämänkin ratkaistua!
hide_expr only_no_yes_on 29 =
tai
Toivottavasti mieleesi jäi, että ei ole yhdentekevää, minkälaista
algoritmia ohjelma käyttää.
Suoritusaika voi riippua siitä valtavasti.
On paljon kivempi odotella vastausta yksi sekunti kuin monta vuorokautta.
Toivottavasti mieleesi jäi myös, miten päättelimme suoritusajasta.
Päättelytaidon harjoittelemiseksi kannattaa nähdä vaivaa.
Hyvästä päättelytaidosta on todella paljon hyötyä sekä opinnoissa että töissä.