Browsing by Subject "Lukuteoria"

Lukuteoria tutkii kokonaislukujen ominaisuuksia, kuten jaollisuutta. Sekä kiinnostavaa että käytän-nöllistä on löytää keinoja selvittää onko jokin kokonaisluku jaettavissa millään toisella kokonais-luvulla. Näitä keinoja tai algoritmeja kutsutaan alkulukutesteiksi ja ne esiintyvät merkittävässäroolissa nykyaikaisessa tietoturvassa ja salaamisessa.Tässä työssä esitellään alkeellisia alkulukutestejä kuten Eratostheneen seula, Wilsonin lause ja Fer-mat’n testi, sekä suurten alkulukujen testaamiseen käytettyjä tehokkaampia menetelmiä. Alkulu-kutestit jaotellaan deterministisiin sekä probabilistisiin testeihin sen mukaan, antavatko ne var-man oikean tuloksen vai jollain tunnetulla todennäköisyydellä epävarman tuloksen. Epävarmempiprobabilistinen testi on kuitenkin determinististä käytännölisempi, sillä se voidaan ajaa riittävänmonta kertaa luotettavan tuloksen saamiseksi ja silti suoriutua determinististä testiä nopeammin.Erityisesti työssä keskitytään Miller-Rabinin probabilistiseen eli satunnaistettuun alkulukutestiin,joka on algoritmina nopea eli tehokas suuria lukuja testatessa. Työssä esitellään myös ensimmäi-nen polynomisessa ajassa suoriutuva deterministinen alkulukutesti AKS, jonka suoritumisaika elilaskutoimitusten lukumäärä on polynominen testattavan luvun numeroiden määrän suhteen.Työssä käydään läpi lukuteoreettista taustaa siinä määrin, kuin on alkulukutestien ymmärtämi-sen osalta oleellista, sekä katsastetaan myös lukuteorian sisältöjä ja opetusta lukiossa. Oleellinentaustateoria sisältää muun muassa kogruenssin, kiinalaisen jäännöslauseen, sekä Fermat’n pienenlauseen. Työssä esitellään myös Mersenneen alkuluvut ja näihin liittyvä yksinkertainen ja tehokasLucas-Lehmerin deterministinen alkulukutesti.Lukuteoriaa opetetaan vain vähän tai ei laisinkaan perusopetuksessa niin Suomessa kuin maail-mallakin. Lukion valinnainen kurssi Algoritmit ja lukuteoria antaa riittävät valmiudet tutustua it-senäisesti alkulukutesteihin tarvittavaan pohjateoriaan, kuten Fermat’n pieneen lauseeseen, muttakurssin varsinaiseen sisältöön alkulukujen testaus ei kuulu alkeellisimpia menetelmiä lukuunotta-matta.Lukuteoreettisten ongelmien pohtiminen ja lukuteorian käsitteiden opiskelu edistää opiskelijoidensuhtautumista matematiikkaan, vaikuttaa positiivisesti näiden metakogniitiivisiin kykyihin, sekäedistää ongelmanratkaisun ja todistamisen taitoja.

Tutkielman tavoitteina on tarkastella lukuteoriaa ja sen soveltuvuutta lukio-opetukseen sekä kirjallisuuteen perustuen selvittää, mitä hyötyä lukuteorian ja ohjelmoinnin yhdistämisessä opetuksessa voisi olla. Motivaationa taustalla toimii lukion uusi opetussuunnitelma 2019 ja erityisesti pitkän matematiikan valtakunnallinen syventävä kurssi MAA11 – Algoritmit ja lukuteoria, jonka keskeisiin sisältöihin sekä lukuteoria että ohjelmointi kuuluvat. Pääasiallisena osana tutkielmaa esitellään konkreettisia ohjelmointiharjoituksia ja -kokonaisuuksia, joiden avulla lukuteorian eri aihealueita voitaisiin lukio-opetuksessa käsitellä ohjelmoinnin kautta. Matematiikan ja ohjelmoinnin yhdistämistä opetuksessa on tutkittu jo entuudestaankin paljon. Tähän liittyen usein puhutaan laskennallisen ajattelun käsitteestä. Laskennalliseen ajatteluun sisältyy valikoima erilaisia ajatuksellisia työkaluja, joiden avulla ongelmia voidaan ratkaista ja jäsentää. Laskennallisen ajattelun taidoista on todettu olevan hyötyä monella osa-alueella, esimerkiksi matematiikassa. Yksi luontainen tapa laskennallisen ajattelun kehittämiseen on ohjelmointi. Toisaalta puolestaan tietojenkäsittelytieteen juuret ovat matematiikassa, joten näillä kahdella tieteenalalla on paljon yhteistä. Myös kontekstilähtöisen opettamisen on huomattu parantavan opiskelijoiden motivaatiota, oppimistuloksia sekä ymmärrystä tieteen yhteydestä arkeen ja ympäröivään maailmaan. Yksi lukuteorian tärkeitä sovelluskohteita on erilaiset kryptografian salausmenetelmät, joten ohjelmointi tarjoaa myös mahdollisuuksia tuoda kontekstuaalisuutta ja relevanssia osaksi lukuteorian opetusta. Sekä laskennallisen ajattelun että kontekstilähtöisen opettamisen haasteiksi on koettu konkreettisten välineiden ja menetelmien puute. Tämän tutkielman tarkoitus on vastata näihin haasteisiin esittelemällä joitakin mahdollisia tapoja lukuteorian ja ohjelmoinnin yhdistämiseen ikään kuin pedagogisena tuotteena. Laaditut ohjelmalliset tehtävät tarjoavat toisaalta matalan kynnyksen lähteä tutkimaan lukuteorian aiheita, mutta myös haastavat kartuttamaan syvempää ymmärrystä pohdinnan ja lisätehtävien kautta. Tutkielmassa esitellään myös lukuteorian keskeistä matemaattista perustaa niin lukion opetussuunnitelmaan sisältyviltä osin, kuin sen ulkopuoleltakin. Pelkästään lukion opetussuunnitelman lukuteoriaan liittyvien sisältöjen puitteissa mahdollisia ohjelmallisia tehtäviä tai käsiteltäviä aihealueita on paljon, ja tämä tutkielma laajuudessaan pystyy vasta raapaisemaan pintaa kaikkien mahdollisuuksien suhteen. Ohjelmallisten harjoitteiden ja ohjelmointia ja lukuteoriaa yhdistelevien tehtävien osalta tutkielma antaa kuitenkin jo ideoita ja luo pohjaa näitä menetelmiä arvioivalle tai kehittävälle jatkotutkimukselle, sillä tämän tutkielman osalta niitä käsiteltiin vasta teoreettisella tasolla.