MAA11 Algoritmit ja lukuteoria — kertaus yo-kokeeseen

Mitä sensori odottaa tästä moduulista

MAA11 on valinnainen moduuli, jonka tehtävät ovat yo-kokeessa usein todistustehtäviä: jaollisuusväite, kongruenssipäättely tai induktio. Siksi pisteet tulevat kirjoitetusta päättelyketjusta, eivät luvusta. Sensori odottaa, että määritelmiä käytetään täsmällisesti — "b jakaa a:n" tarkoittaa, että on olemassa kokonaisluku k, jolle a = k * b, ja tämä k kirjoitetaan näkyviin. Induktiossa on oltava sekä alkuaskel että induktioaskel, ja induktio-oletusta pitää käyttää näkyvästi askeleessa; pelkkä "oletetaan väite todeksi" ilman sen hyödyntämistä ei anna pisteitä. Algoritmitehtävässä odotetaan, että suoritus kirjataan askel kerrallaan taulukkona, ei vain lopputuloksena.

Ydinkäsitteet

• Jaollisuus — b | a tarkoittaa, että on olemassa kokonaisluku k, jolle a = k * b. Huomaa suunta: pystyviiva luetaan "jakaa".
• Jakoyhtälö — jokaiselle a ja b > 0 on yksikäsitteiset q ja r, joille a = q * b + r ja 0 <= r < b. Luku r on jakojäännös.
• Alkuluku — luku p > 1, jonka ainoat positiiviset tekijät ovat 1 ja p. Luku 1 ei ole alkuluku eikä yhdistetty luku.
• Aritmetiikan peruslause — jokainen kokonaisluku n > 1 hajoaa alkulukujen tuloksi, ja hajotelma on tekijöiden järjestystä lukuun ottamatta yksikäsitteinen.
• Suurin yhteinen tekijä (syt) — suurin luku, joka jakaa molemmat luvut; löytyy Eukleideen algoritmilla. Jos syt(a,b) = 1, luvut ovat keskenään jaottomat.
• Pienin yhteinen jaettava (pyj) — pienin positiivinen luku, jonka molemmat jakavat; yhteys syt(a,b) * pyj(a,b) = a * b.
• Kongruenssi — a = b (mod n) tarkoittaa, että n | a - b eli luvuilla on sama jakojäännös luvulla n jaettaessa.
• Iteraatio ja rekursio — iteraatio toistaa saman askeleen silmukassa; rekursio määrittelee arvon aiempien arvojen avulla ja tarvitsee aina alkuarvon (kantatapauksen).
• Induktio — todistusmenetelmä, jossa alkuaskel ja induktioaskel yhdessä kattavat kaikki positiiviset kokonaisluvut.