Algoritminen ajattelu
Algoritmi
Algoritmi on yksityiskohtainen, jollain kielellä esitetty kuvaus tai ohje, jota seuraamalla voidaan haluttu tehtävä tai prosessi suorittaa onnistuneesti. Matematiikassa ja tietojenkäsittelytieteessä algoritmi määritellään äärelliseksi joukoksi hyvin määriteltyjä ohjeita, jotka ovat tietokoneen luettavissa. Erinomainen esimerkki algoritmista on aivan tavallinen keittokirjan perunoiden keitto-ohje.
Perunoiden keitto-ohje
1. Pese huolellisesti tuoreet perunat. Pane perunat tyhjään kattilaan.
2. Keitä vesi keittimessä tai toisessa kattilassa. Kaada perunakattilaan vettä sen verran, että perunat peittyvät. Lisää suolaa makusi mukaan 1-3 teelusikallista.
3. Kaada vesi pois ja laita kansi kattilan päälle. Anna höyryn tasaantua muutaman minuutin.
4. Tarjoile.
Toinen hyvä esimerkki arkipäivän algoritmista on ihan tavallinen kauppalista. Voidaan ajatella, että jokainen kauppalistan tuote ikään kuin käskee kaupassakävijää ostamaan ko. tuotteen.
Algoritmi on siis vaiheittainen menetelmä halutun ongelman ratkaisemiseksi. Algoritmeja ovat muun muassa
• yhteen-, vähennys-, kerto- ja jakolaskun laskeminen allekkain
• yhtälöiden ratkaisumenetelmät
• janan keskinormaalin ja kolmion kulmanpuolittajan piirtäminen harppia ja viivainta käyttäen
• derivointi- ja integrointisäännöt.
Riittävän tarkasti kuvailtuna algoritmi voidaan suorittaa rutiininomaisesti. Tässä materiaalissa tutustutaan algoritmeihin, jotka voidaan koodata tietokoneohjelmiksi ja suorittaa automaattisesti.
Algoritmi on alkujaan matemaattinen käsite. Useimmiten ensimmäiset matemaattiset algoritmit, joita ihmiset kohtaavat elämässään ovat alakoulun allekkain kertominen ja jakaminen. Niiden avulla mitkä tahansa luvut voidaan kertoa tai jakaa keskenään. Toisinaan algoritmitermillä on tarkoitettu nimenomaan Eukleideen algoritmia kahden kokonaisluvun suurimman yhteisen tekijän (syt) löytämiseksi.
Eukleideen algoritmi on hyvä perusesimerkki matemaattisesta algoritmista. Se perustuu jakoyhtälön perättäiseen käyttöön.
Eukleideen algoritmi
1. Ensin kirjoitetaan jakoyhtälö luvuilla a ja b.
2. Seuraavaksi kirjoitetaan jakoyhtälö luvulle b ja edellisen jakoyhtälön jakojäännökselle.
3. Toistetaan niin usein, että jakojäännökseksi saadaan nolla.
4. Lukujen a ja b suurin yhteinen tekijä on viimeisin nollasta eroava jakojäännös.
Etsitään lukujen 84 ja 60 suurin yhteinen tekijä (syt).
84 = 1 · 60 + 24
60 = 2 · 24 + 12
24 = 2 · 12 + 0
Eli syt on 12
Esimerkki kahden luvun suurimman yhteisen tekijän etsimisalgoritmistä. Etsitään lukujen 255 ja 55 suurin yhteinen tekijä jakoyhtälöiden avulla.
Eli lukujen 2555 ja 55 suurin yhteinen tekijä on 5.
Termin matemaattisesta alkuperästä huolimatta, tai siitä johtuen, algoritmin käsite kuitenkin liittyy tänä päivänä ennen kaikkea tietojenkäsittelyyn ja tietokoneiden ohjelmointiin.
Algoritmisen ajattelun peruskäsitteet: peräkkäisyys, valinta ja toisto
Tutustu myös ohjelmointi-kappaleen teoriaosuuteen. Siellä muun muassa opastetaan miten ohjelmointiin tarvittava ohjelma asennetaan. Ohjelmointi.
Tässä luvussa tutustutaan algoritmeihin liittyviin peruskäsitteisiin ja säännönmukaisuuksiin. Näiden avulla lukijan on tarkoitus pystyä ymmärtämään algoritmeihin ja niiden rakentamiseen liittyvää kieltä ja sanastoa. Seuraavassa siis perehdytään käsitteisiin peräkkäisyys, valinta ja toisto.
Peräkkäisyys
Miltein yksioikoisesti voi todeta, että algoritmin oletussuoritusjärjestys on aina peräkkäinen. Toisin sanoen peräkkäin kirjoitetut operaatiot suoritetaan siinä järjestyksessä kuin ne ovat ohjelmaan ohjelmoitu. Tämä tarkoittaa siis sitä, että kun algoritmi on kirjoitettu kielen muodossa tekstiksi niin sitä luetaan vasemmalta oikealle ja ylhäältä alaspäin.
Esimerkiksi kun tarkastellaan teen keittoa algoritmisesti tulee ymmärtää, että teen keittoon liittyvässä prosessissa edetään tietyssä järjestyksessä. Ohjeen muotoilijan, ohjelmoijan, on ymmärrettävä kirjoittaa ohjelmansa niin, että prosessin vaiheet tulevat oikeassa järjestyksessä. Teenkeitossa on esimerkiksi oleellista täyttää kattila vedellä ennen liedelle laittamista ja lisätä teelehdet vasta kun vesi on tarpeeksi kuumaa. Tarkastele seuraavaa esimerkkkiä teen valmistamiseen liittyvästä algoritmista. Päästäisiinkö haluttuun lopputulokseen muuten kuin noudattamalla ns. peräkkäisyyttä?
Esimerkki algoritmin peräkkäisyydestä
1. Lisää vesi kattilaan.
2. Laita kattila kuumalle liedelle.
3. Odota kunnes vesi on tarpeeksi kuumaa.
4. Kaada kuuma vesi teepannuun.
5. Lisää pannuun valitsemasi teelaatu.
6. Odota 5-10 minuuttia kunnes tee on hautunut.
7. Nauti.
Ohjelman suoritusjärjestystä voidaan ohjailla erilaisilla rakenteilla. Tyypillisimpiä suoritusjärjestystä ohjaavia rakenteita ovat valinta- ja toistorakenne.
Valinta
Usein algoritmeja suunnitellessa huomataan, että vain tietyt olosuhteet tai tilanteet sopivat algoritmin tiettyyn prosessiosana. Algoritmin tulee tunnistaa tälläinen erikoistilanne. Näin algoritmista tulee usein tehokkaampi ja myös vältetään mahdollisia virhetilanteita.
Valinnassa käydään läpi erilaisia vaihtoehtoja tai kriteerejä, joiden perusteella prosessia jatketaan tiettyyn suuntaan. Kun tietty valintakriteeri täyttyy, tehdään vaihtoehdon alle määriteltyjä toimintoja.
Esimerkki algoritmin valinnasta
1. Jos mieleni tekee teetä keitän teetä
2. Jos mieleni tekee kahvia keitän kahvia
3. Muuten juon vettä.
Valintaa varten voidaan myös määritellä ennakkoon tietty joukko vaihtoehtoja sekä tietyt kriteerit näille vaihtoehdoille. Seuraavassa esimerkissä kriteerinä on käyttäjä teemieltymys.
Esimerkki algoritmin valinnasta, jossa käyttäjä valitsee ennakkoon määritellystä joukosta
1. Valitse jokin vaihtoehdoista a., b. tai c.
a. Musta tee
b. Vihreä tee
c. Valkoinen tee.
2. Keitä valitsemasi teelaatu.
3. Nauti.
Toisto
Usein algoritmiin liittyy toiston tarvetta. Toistossa tiettyä käskyä eli prosessin vaihetta toistetaan etukäteen määritellyn määrän kertoja tai niin kauan, että päästään haluttuun lopputulokseen.
Esimerkki algoritmin toistosta, jossa toistomäärä on etukäteen määritelty
1. Toista seuraava prosessi 8 kertaa.
Kaada kattilaan 1 dl vettä.
2. Aseta kattila hellalle kuumalle levylle.
Esimerkki algoritmin toistosta, jossa toistot jatkuu kunnes haluttu lopputulos saavutetaan
1. Tarkasta onko kattilassa 8 dl vettä.
2. Jos pannussa on alle 8 dl vettä
lisää 1 dl vettä ja siirry kohtaan 1.
Muuten
siirry seuraavaan vaiheeseen.
3. Aseta kattila hellalle kuumalle levylle.
Kumpikin toistorakenne tuottaa halutun lopputuloksen; 8 dl vettä on hellalla kuumalla levyllä lämpiämässä.
Valinta-rakenne ohjelmointikielellä ilmaistuna
Seuraavassa käydään läpi miten edelliset valinta-rakenteet näyttäisivät ohjelmointikielellä ilmaistuna.
Ensimmäisessä rakenteessa ns. valintakriteerit tarkastetaan ifehtolauseen avulla. Jos if-sanan jälkeinen ehto täyttyy (eli on totta) suoritetaan if-rakenteen alla oleva prosessi. Jos ehto ei täyty (eli ei ole totta) siirrytään seuraavaan if-haaraan. Jos algoritmin mikään ifsanan jälkeinen valintakriteeri ei täyty, edetään else-haaraan. Pythonohjemointikielellä ensimmäisen if-haaran jälkeisen if-haarat toteutetaan usein elif-komennolla. Ohjemoija voi valita kumpaa käyttää. Seuraavassa pseudo-koodin pätkässä on käytetty vain if-komentoja vaikka rivien 4 ja 7 if-komennot olisi voinut korvata elif-komennolla.
Python Online Compilerilla kirjoitettu ns. pseudokoodi, jonka on tarkoitus esitellä if- ja else-haaroilla rakennettu valintarakenne.
On hyvä huomatta, että tässä luvussa esitellyt Python-koodit eivät ole ns. ajettavissa. Niiden on vain tarkoitus esitellä lukijalle uusia käsitteitä. Tähän viittaa käsite pseudo-koodi.
Toisessa valinta-rakenteessa teelaatu valitaan etukäteen. Toisin sanoen vaihtoehdot ovat tiedossa jo etukäteen. Käyttäjälle siis esitellään vaihtoehtolista, josta käyttäjä valitsee haluamansa vaihtoehdon. Python-ohjelmointikielellä tämä toteutetaan esimerkiksi tallentamalla muuttujaan käyttäjän valinta input-komennolla.
Python Online Compilerilla kirjoitettu ns. pseudokoodi, jossa käyttäjä valitsee ennalta määritellyltä listalta.
Toistorakenne ohjelmointikielellä
Käydään sitten läpi, miltä toistorakenteet näyttävät ohjelmointikielellä ilmaistuna. Jos toistojen määrä on etukäteen tiedossa voidaan komentojen toisto toteuttaa for-rakenteella. For-rakenteessa määritellään muuttuja (esim. x) ja toistojenmäärä (range). Kaksoispisteen jälkeen määritellään haluttu käsky uudelle riville.
Python Online Compilerilla kirjoitettu ns. pseudokoodi, jonka on tarkoitus esitellä for-rakenteella toteutettu toisto.
Toinen tässä esiteltävä toiston toteuttava rakenne on while-rakenne. While-rakenteessä määritellään ensin ”muuttujalaskuri” (count) ja sille aloitusluku (kuten vaikka 0 tai 1.) Huomaa, että muuttujan nimi (count) voi olla mikä vain (esim. ”i”) Sen jälkeen määritellään whilesilmukka, jonka sisään mennään jos while-silmukan ehto toteutuu. While-rakenteessa suoritettava komento kirjoitetaan kaksoispisteen jälkeen seuraavalle riville. Komennon jälkeen seuraavalla rivillä kasvatetaan ”muuttujalaskurin” arvoa yhdellä, minkä jälkeen koodia aletaan lukea ensimmäiseltä riviltä uudestaan. Silmukka pyörii niin kauan, kuin while-rakenteen ehto on tosi.
Python Online Compilerilla kirjoitettu ns. pseudokoodi, jonka on tarkoitus esitellä while-rakenteella toteutettu toisto.
Harjoituksia
Selitä käsite algoritmi. Anna esimerkki algoritmista.
2. Selitä käsite peräkkäisyys.
3. Kirjoita kitaran viritysohje ystävälläsi, joka ei ole ennen virittänyt kitaraa. Kiinnitä huomiota, että ohje tai algoritmi noudattaa peräkkäisyyden sääntöä. Ota selvää internetin avulla jos et tiedä kuinka kitara viritetään.
4. Selitä algoritmeihin liittyvä käsite valinta.
5. Anna esimerkki valinta-algoritmistä, jossa valitaan käyttäjän mieleiset sukat. Käytä mielikuvitusta ja ota mallia materiaalista.
6. Anna esimerkki valinta-algoritmistä, jossa valitaan käyttäjälle mieleinen auto.
7. Tarkastele tehtävää 5. Millä tavalla käsite peräkkäisyys on oleellinen kun kirjoitetaan valinta-algoritmia vastaamaan käyttäjän mieltymyksiä?
8. Tarkastele tehtävän 6 malliratkaisua. Preferoiko ko. algoritmin kirjoittaja punaista autoa, jossa ei ole nahkasisustus vai satunnaisen väristä autoa, jossa on nahkasisustus? Perustele.
9. Ajatellaan, että pidät pyöreistä, keltaisista, pienistä ja pehmeistä esineistä. Ajatellaan, että jokainen edellämainituista adjektiiveista nostaa esineen arvostusta mielessäsi yhdellä pisteellä. Näin ollen esineellä voi olla 0-4 pistettä. Kirjoita nyt algoritmi, joka arvottaa ympärilläsi olevat esineet.
10. Yritä kirjoittaa edellinen tehtävä Python-ohjelmointikielellä, niin että ohjelma lopulta printtaa esineen pisteytyksen.
11. Kirjoita Python-ohjemointikielellä ohjelma, joka alustaa listan etukäteen määritellyn listan ja vertaa listan lukuja lukuihin 10, 15 ja 100. Listalla tulee olla luvut -2, 3, 5, 9, 15, 99, ja 14. Määrää ohjelma niin, että
• jos käyttäjän listalta valitsema luku on suurempi kuin 10 ohjelma tulostaa lauseen ”Valitsemasi numero (luku) on suurempi kuin 10.”
• jos käyttäjän listalta valitsema luku on suurempi kuin 15 ohjelma tulostaa lauseen ”Valitsemasi numero (luku) on suurempi kuin 15.”
• jos käyttäjän listalta valitsema luku on pienempi kuin 100 ohjelma tulostaa lauseen ”Valitsemasi numero (luku) on pienempi kuin 100.”
12. Selitä käsite toisto.
13. Kirjoita Python-ohjelma, joka laskee kattilaan lisätyt jauhot kun käytössäsi on 2,5 desilitran mittakuppi. Ohjelman tulee siis laskea kattilaan lisätty jauhomäärä kun siihen lisätään 2,5 desilitran mittakupilla tietty kertamäärä jauhoja. Toteuta ohjelma for-rakenteella.
14. Kirjoita Python-ohjelma. Ohjelman käyttäjän tulee valita listalta, joko 25, 50 tai 775 litran kattila. Käytössä on 1,25 desilitran mittakuppi. Ohjelman tulee kertoa käyttäjälle kuinka monta kertaa 1,25 desilitran mittakupilla valittuun kattilaan tulee kertamääräisesti lisätä vettä, että ko. kattila tulee täyteen. Voit käyttää esimerkiksi while-rakennetta.