Algoritmien perusteet – määritelmä, rakenne ja esimerkit
Algoritmi on selkeä, vaiheittainen menetelmä ongelman ratkaisemiseksi. Algoritmit ovat keskeisiä matematiikassa ja tietojenkäsittelytieteessä, ja ne kuvaavat, miten tehtävä voidaan suorittaa järjestelmällisesti. Tämä aihe kuuluu lukion pitkän matematiikan opetussuunnitelmaan (LOPS21) ja käsitellään erityisesti kurssissa MAA11: Algoritmit ja lukuteoria. Tällä sivulla opit algoritmien perusteet, niiden rakenteen ja esimerkkejä algoritmeista matematiikassa.
Määritelmä
Algoritmi on äärellinen joukko selkeitä, yksiselitteisiä ohjeita, jotka kuvaavat, miten tehtävä voidaan suorittaa vaihe vaiheelta. Algoritmin tulee olla: 1) Selkeä ja yksiselitteinen, 2) Äärellinen (päättyvä), 3) Tehokas (suoritettavissa), 4) Yleinen (toimii useille syötteille).Kaavat
Algoritmin rakenne:
Pseudokoodi:
Aikakompleksisuus: kuvaa algoritmin suoritusaikaa syötteen koon funktiona
Säännöt
Algoritmin perusrakenne
Ehtolauseet
Toistorakenteet
Muuttujat
Esimerkit
Esimerkki 1: Kahden luvun summa
HelppoKirjoita algoritmi kahden luvun summan laskemiseksi.
- Alku: Algoritmi alkaa.Jokainen algoritmi alkaa selkeästi määritellystä alusta.
- Lue kaksi lukua: ja .Algoritmi lukee syötteen, tässä tapauksessa kaksi lukua.
- Laske summa: .Suoritetaan laskutoimitus ja tallennetaan tulos muuttujaan .
- Tulosta summa .Algoritmi tulostaa lopputuloksen.
- Loppu: Algoritmi päättyy.Algoritmi päättyy selkeästi määriteltyyn loppuun.
Esimerkki 2: Suurimman luvun etsiminen kolmesta luvusta
KeskitasoKirjoita algoritmi kolmen luvun suurimman löytämiseksi.
- Alku: Algoritmi alkaa.Algoritmi alkaa selkeästi määritellystä alusta.
- Lue kolme lukua: , ja .Algoritmi lukee syötteen, tässä tapauksessa kolme lukua.
- Jos ja , niin suurin on .Tarkistetaan, onko suurin luku vertaamalla sitä muihin lukuihin.
- Muuten, jos , niin suurin on .Jos ei ole suurin, tarkistetaan, onko suurin.
- Muuten suurin on .Jos ja eivät ole suurimpia, niin on suurin.
- Tulosta suurin luku.Algoritmi tulostaa lopputuloksen.
- Loppu: Algoritmi päättyy.Algoritmi päättyy selkeästi määriteltyyn loppuun.
Esimerkki 3: Eukleideen algoritmi (suurin yhteinen tekijä)
VaikeaKirjoita algoritmi kahden luvun suurimman yhteisen tekijän löytämiseksi Eukleideen algoritmilla.
- Alku: Algoritmi alkaa.Algoritmi alkaa selkeästi määritellystä alusta.
- Lue kaksi positiivista lukua: ja (oletetaan ).Eukleideen algoritmi vaatii kaksi positiivista lukua.
- Toista, kunnes :Algoritmi käyttää toistorakennetta, joka päättyy, kun on nolla.
- - Laske jakojäännös: (jakojäännös, kun jaetaan :llä).Jakojäännös lasketaan jakojäännösoperaatiolla .
- - Aseta ja .Pienempi luku siirretään isommaksi ja jakojäännös pienemmäksi.
- Suurin yhteinen tekijä on .Kun on nolla, on suurin yhteinen tekijä.
- Tulosta suurin yhteinen tekijä.Algoritmi tulostaa lopputuloksen.
- Loppu: Algoritmi päättyy.Algoritmi päättyy selkeästi määriteltyyn loppuun.
Esimerkki 4: Alkuluvun tarkistaminen
VaikeaKirjoita algoritmi, joka tarkistaa, onko annettu luku alkuluku.
- Alku: Algoritmi alkaa.Algoritmi alkaa selkeästi määritellystä alusta.
- Lue luku: (oletetaan ).Alkuluku on suurempi kuin 1, joten tarkistetaan vain luvut .
- Jos , niin luku on alkuluku. Päätä algoritmi.Luku 2 on ainoa parillinen alkuluku.
- Jos on parillinen, niin luku ei ole alkuluku. Päätä algoritmi.Kaikki muut parilliset luvut ovat jaollisia kahdella.
- Tarkista, onko jaollinen millään parittomalla luvulla välillä ja :Riittää tarkistaa jakajat aina luvun neliöjuureen asti.
- - Jos , niin luku ei ole alkuluku. Päätä algoritmi.Jos jakojäännös on nolla, luku on jaollinen ja ei ole alkuluku.
- Jos mikään jakaja ei löytynyt, niin luku on alkuluku.Jos luku ei ole jaollinen millään pienemmällä luvulla, se on alkuluku.
- Tulosta tulos.Algoritmi tulostaa, onko luku alkuluku vai ei.
- Loppu: Algoritmi päättyy.Algoritmi päättyy selkeästi määriteltyyn loppuun.
Esimerkki 5: Lukujen järjestäminen (kuplalajittelu)
VaikeaKirjoita algoritmi, joka järjestää luvut nousevaan järjestykseen kuplalajittelulla.
- Alku: Algoritmi alkaa.Algoritmi alkaa selkeästi määritellystä alusta.
- Lue lukujen määrä ja luvut taulukkoon .Algoritmi lukee syötteen, tässä tapauksessa lukujen määrän ja luvut taulukkoon.
- Toista kertaa (ulompi silmukka):Kuplalajittelu vaatii kierrosta.
- - Toista kertaa (sisempi silmukka):Jokaisella kierroksella verrataan vierekkäisiä alkioita.
- - Jos , niin vaihda ja keskenään.Jos alkio on suurempi kuin seuraava, ne vaihdetaan keskenään.
- Tulosta järjestetty taulukko .Algoritmi tulostaa järjestetyn taulukon.
- Loppu: Algoritmi päättyy.Algoritmi päättyy selkeästi määriteltyyn loppuun.
Esimerkki
Kirjoita algoritmi kahden luvun suurimman löytämiseksi.
- Alku: Algoritmi alkaa.
- Lue kaksi lukua: ja .
- Vertaa lukuja: Jos , niin suurin on , muuten suurin on .
- Tulosta suurempi luku.
- Loppu: Algoritmi päättyy.
Sovellukset
- Matematiikassa algoritmeja käytetään laskutoimituksissa, kuten jakolaskussa, neliöjuuren laskemisessa ja yhtälöiden ratkaisemisessa. Esimerkiksi jakolasku voidaan suorittaa algoritmisesti jakoalgoritmilla.
- Tietojenkäsittelytieteessä algoritmit ovat perusta kaikelle ohjelmoinnille. Jokainen tietokoneohjelma on olennaisesti algoritmin toteutus.
- Kryptografiassa algoritmeja käytetään salauksessa ja salauksen purkamisessa. Esimerkiksi RSA-salaus käyttää algoritmeja alkulukujen löytämiseen ja modulaariaritmetiikkaan.
- Tehokkuusanalyysissä algoritmien aikakompleksisuutta analysoidaan, jotta voidaan valita tehokkain menetelmä ongelman ratkaisemiseksi.
Yleisiä virheitä
Algoritmin vaiheiden epäselvyys
Monet unohtavat, että algoritmin vaiheiden tulee olla täysin selkeät ja yksiselitteiset. Epäselvät ohjeet eivät ole algoritmi.
Oikein: Varmista, että jokainen vaihe on selkeä ja yksiselitteinen. Käytä tarvittaessa pseudokoodia tai kaavioita selventämään algoritmin rakennetta.
Lopettamattomuus (äärettömät silmukat)
Monet unohtavat varmistaa, että algoritmi päättyy. Jos toistorakenne ei koskaan päätty, algoritmi ei ole käyttökelpoinen.
Oikein: Varmista aina, että toistorakenteet päättyvät. Tarkista, että ehto muuttuu jokaisella kierroksella ja että se lopulta täyttyy.
Reunatapauksien unohtaminen
Monet unohtavat käsitellä reunatapauksia, kuten tyhjää syötettä, negatiivisia lukuja tai nollaa.
Oikein: Tarkista aina reunatapaukset. Esimerkiksi, jos algoritmi käsittelee lukuja, tarkista, mitä tapahtuu, jos luku on nolla tai negatiivinen.
Muuttujien alustamattomuus
Monet unohtavat alustaa muuttujat ennen niiden käyttöä, mikä voi johtaa virheellisiin tuloksiin.
Oikein: Alusta aina muuttujat ennen niiden käyttöä. Esimerkiksi, jos käytät summaa, alusta se nollaksi: .
Usein kysyttyä
- Mikä on algoritmi?
- Algoritmi on äärellinen joukko selkeitä, yksiselitteisiä ohjeita, jotka kuvaavat, miten tehtävä voidaan suorittaa vaihe vaiheelta. Algoritmin tulee olla selkeä, äärellinen, tehokas ja yleinen.
- Mitä eroa on algoritmilla ja ohjelmalla?
- Algoritmi on käsitteellinen kuva ongelman ratkaisusta, kun taas ohjelma on algoritmin toteutus tietokoneella. Algoritmi voidaan kirjoittaa pseudokoodina tai luonnollisella kielellä, kun taas ohjelma on kirjoitettu ohjelmointikielellä.
- Mikä on pseudokoodi?
- Pseudokoodi on algoritmin kuvaaminen luonnollisella kielellä ja matemaattisilla merkinnöillä. Se on välimuoto algoritmin ja ohjelman välillä, ja se auttaa ymmärtämään algoritmin rakennetta ilman ohjelmointikielen syntaksia.
- Miten tarkistan, että algoritmi on oikea?
- Tarkista algoritmi seuraavilla kriteereillä: 1) Onko se selkeä ja yksiselitteinen? 2) Päättyykö se aina? 3) Antaako se oikean tuloksen? 4) Toimiiko se kaikilla sallituilla syötteillä? Testaa algoritmia useilla eri syötteillä, mukaan lukien reunatapaukset.
- Mikä on algoritmin aikakompleksisuus?
- Algoritmin aikakompleksisuus kuvaa, miten algoritmin suoritusaika kasvaa syötteen koon kasvaessa. Se ilmaistaan usein O-merkinnällä (iso O), esimerkiksi tarkoittaa, että suoritusaika kasvaa lineaarisesti syötteen koon kanssa.
- Miten kirjoitan algoritmin?
- Aloita määrittelemällä ongelma selkeästi. Sitten hajota ongelma pienempiin osiin ja kirjoita vaiheet järjestyksessä. Käytä ehtolauseita ja toistorakenteita tarvittaessa. Varmista, että algoritmi päättyy ja antaa oikean tuloksen.
- Mitä ovat algoritmin perusrakenteet?
- Algoritmin perusrakenteet ovat: 1) Järjestys (vaiheet suoritetaan peräkkäin), 2) Valinta (ehtolauseet, kuten "jos-muuten"), 3) Toisto (silmukat, kuten "toista-kunnes"). Näillä rakenteilla voidaan toteuttaa mikä tahansa algoritmi.
- Mikä on Eukleideen algoritmi?
- Eukleideen algoritmi on menetelmä kahden luvun suurimman yhteisen tekijän löytämiseksi. Se perustuu siihen, että , ja se toistetaan, kunnes . Tällöin on suurin yhteinen tekijä.
- Miten tarkistan, onko luku alkuluku?
- Tarkista, onko luku jaollinen millään luvulla välillä 2 ja . Jos luku ei ole jaollinen millään näistä luvuista, se on alkuluku. Tämä on tehokkain menetelmä pienille luvuille.
- Mitä eroa on eri lajittelualgoritmeilla?
- Eri lajittelualgoritmit eroavat toisistaan tehokkuudeltaan ja monimutkaisuudeltaan. Esimerkiksi kuplalajittelu on yksinkertainen mutta hidas (), kun taas quicksort on nopeampi () mutta monimutkaisempi.
Lähteet ja lisämateriaali
- LOPS21: MAA11 Algoritmit ja lukuteoria
Lukion pitkän matematiikan kurssi (LOPS21), joka käsittelee algoritmeja ja lukuteoriaa. Tämä kurssi on osa lukion opetussuunnitelmaa.
- Ylioppilaskokeiden tehtävät
Aiemmat ylioppilaskokeiden tehtävät ja malliratkaisut algoritmeista ja lukuteoriasta.
- TIM - Pitkän matematiikan kertauskurssi
Jyväskylän yliopiston kertauskurssi, joka sisältää harjoitustehtäviä ja teoriaa algoritmeista.