Tunnin tarkoituksena on näyttää leikin avulla miten hakualgoritmi voi toimia. Ohjeiden tulee tulla yksinkertaisina ja niitä seuraamalla tulee aina onnistua.
| Oppiaine | matematiikka, tietotekniikka |
| Pituus | 45 minuuttia |
| Pedagoginen lähestymistapa | tekemällä oppiminen |
| Kompetenssit | algoritmit |
| Luokka-aste | 3.-6.lk |
| Teknologiat | ei teknologiaa |
Muut tarvittavat materiaalit
Kynä ja paperia.
Harjoituksen kohdekompetenssit
- Oppilaat oppivat mitä algoritmi tarkoittaa
- Oppilaat oppivat, että on olemassa erilaisia tapoja hakea tiettyä numeroa ja toiset tavat ovat huomattavasti nopeampia kuin toiset.
- Oppilaat oppivat yksinkertaisia algoritmien periaatteita
- Oppilaat oppivat käyttämään ohjelmoinnin ehtolausetta käytännössä
Kuvaus
Valitaan leikkiin parillinen määrä oppilaita. Toinen päättää numeron sovitulta väliltä ja toinen yrittää arvata sen kysymällä kysymyksiä. Numeron päättänyt saa vastata vain “kyllä” tai “ei”. Mikä on nopein tapa löytää haluttu numero?
Johdanto:
Oppilaille kerrotaan taas algoritmien periaatteesta (Liite 1) ja kuinka ne tiettyjä ohjeita noudattamalla tuottavat aina ratkaisun riippumatta millainen aineisto niille annetaan. Oppilaita voidaan muistuttaa ihmisrobotti-harjoituksesta ja heitä neuvotaan seuraamaan ohjeita tarkasti.
Harjoitus 1:
Opettaja jakaa oppilaat pareiksi. Ensin toinen on etsijä ja toinen vastaaja. Vastaaja valitsee numeron väliltä 1-50 ja kirjoittaa sen lapulle ylös. Sitten toinen saa alkaa kysellä kysymyksiä ja vastaaja vastaa niihin vain “kyllä” tai “ei”. Aluksi joku voi kysellä yksittäisiä numeroita “onko se 2, onko se 3”. Jos he eivät hoksaa mahdollisuutta kysyä “onko se suurempi kuin 10”, heitä voi ohjeistaa oikeaan suuntaan. Kun numero on löytynyt, voidaan vaihtaa rooleja. Idea selviää alla olevalta videolta.
Keskustelu:
Apukysymyksiä: Montako arvausta piti tehdä, ennenkuin oikea luku löytyi? Millaisia taktiikoita oppilailla oli? Miten arvausten määrä eri taktiikoilla muuttuisi, jos luku olisikin välillä 1-1000?
Opettaja kertoo binäärihaun periaatteen: Jos hakuväli on 1-1000, kysytään ensin onko haettu luku suurempi kuin 500 (hakuvälin puoliväli). Sen jälkeen kysytään onko haettu luku suurempi kuin jäljellä olevien lukujen puoliväli ja jatketaan haettavien lukujen puolittamista kunnes ollaan löydetty haettu luku.
Harjoitus 2:
Aloitetaan hakuvälillä 1-1000. Oppilaat harjoittelevat binäärihakua ja voivat halutessaan yrittää jotain muuta tapaa löytää haluttu luku. Oppilaat laskevat montako arvausta tarvitaan haetun luvun löytämiseksi. Mitä tapahtuu, jos hakuväli on 1 – 10 000? Entä yhdestä miljoonaan? Entä yhdestä miljardiin?
Keskustelu:
Mitä oppilaat huomasivat hakukysymysten lukumäärästä?
Apukysymyksiä: Miksi tarvittavien kysymysten määrä ei kasvanut kovin nopeasti? Kuinka monta kysymystä tarvittiin löytämään haettu luku, kun haettiin lukua yhden ja miljoonan välillä?
Vanhemmille oppilaille voi kertoa kahden potenssista ja siitä miten nopeasti se kasvaa. Jokainen haku puolittaa mahdollisten lukujen määrän. Toisin sanoen, haettavien lukujen lukumäärän kaksinkertaistuessa tarvitaan vain yksi kysymys enemmän. Kuvassa 1 on kuvattu kahden potensseja. Luku kaksi kerrotaan itsellään eksponentissa olevan luvun verran. Kuvasta löytyy myös binäärihaun hakujen lukumäärien vastauksia. Jos haettavia lukuja on 128, löytyy haettava luku korkeintaan seitsemällä kysymyksellä. (2 potenssiin 7 on 128). Kahden potenssi kertoo sen kuinka monta kysymystä tarvitaan korkeintaan halutun luvun löytämiseen.
Harjoitus 3:
Jos on aikaa, oppilaat voivat vielä kokeilla pitääkö äskeinen väite paikkaansa.
Liite 1
Algoritmit ovat ohjejoukkoja, joita noudattamalla saadaan haluttu lopputulos. Se voi olla periaatteessa mikä tahansa ohje, vaikka perunannosto-ohje. Tavallisesti algoritmeista puhuttaessa tarkoitetaan jotain matemaattista ohjetta tai tietokoneen ohjeistoa. Esimerkiksi tässä harjoiteltu binäärihaku on hakualgoritmi. Tietotekniikassa käytetään monia hakualgoritmeja ja järjestysalgoritmeja, mutta niitä käytetään myös mainosten suuntaamisessa internetissä.