Tag Archives: programmering

Juleferiekos?

Savner du matematikken i juleferien? Her er noen tips til matematisk julekos.

  • Lær å programmere! Dette er gøy, og i tillegg har du enormt stor nytte av det uansett hva du skal jobbe med i fremtiden. En veldig god plass å starte på er Khan Academy’s Hour of Code – på kun én time lærer du ganske mye! Hvis du vil ha mer enn dette, gå direkte til Khan Academy Computer Programming eller til Codecademy. På Codecademy kan du lære mange forskjellige språk, og hvis du er interessert i matte ville jeg begynt med Python.
  • Last ned et spill til mobilen/nettbrettet! Det finnes massevis av spill som bygger på kreativ matematisk tenking, men to av de aller beste er DragonBox (koster noen kroner) og det enda mer utfordrende Wuzzit Trouble (gratis!).
  • Kan du litt om funksjoner og grafer allerede? Prøv å finne funksjonsuttrykkene som svarer til forskjellige grafer på Daily Desmos. Dette er en annerledes form for julenøtter, som gir veldig god trening og forståelse i funksjonsteori.
  • Løs noen “julenøtter” fra Abelkonkurransen! Her er en samling med oppgaver som ikke krever noen spesielle forkunnskaper utover ungdomsskolematematikk:

Abel 2013 Runde 1: Løs oppgavene 1, 2, 3, 5, 7, 9 og 12

Abel 2012 Runde 1: Løs oppgavene 1, 4, 5, 6, 8, 9, 11, 12, 15

Abel 2011 Runde 1: Løs oppgavene 1, 2, 4, 11

Abel 2012 Runde 2: Løs oppgavene 1, 2, 3

Abel 1992 Runde 1: Løs oppgavene 1, 2, 4, 6, 7, 8, 11, 14, 20

Er disse oppgavene for lette? Utforsk noen av de andre bloggpostene her, for eksempel denne, som handler om høyere versjoner av kvadratsetningene.

God Jul 😀

 

Advertisements

Algoritmer for faktorisering av store tall

En av mine elever spurte om hvordan man programmerer en egen algoritme i Java for faktorisering av store tall. Her er mitt svar, som kanskje noen andre kan ha nytte av:

Hei!
Det finnes enormt mange ulike algoritmer for faktorisering av heltall, fra den aller enkleste (trekk ut alle 2-tall, så 3-tall, så 5-tall, …), som du sikkert kan forstå og programmere selv nå med en gang, til veldig avanserte metoder, som “quadratic sieve”, “elliptic curve factorization”, og “number field sieve”. For å forstå detaljene i de mest avanserte metodene trenger du flere år av studier, men hvis du er interessert så kan jeg gi deg ganske mye tips og veiledning på veien. Her er litt referenser, fra veldig enkle til veldig avanserte. Setter tall på linkene i tilfelle vi skal referere til dem senere.
Her er en ferdig superenkel faktoriseringsalgoritme i Java:
Her finner du en introduksjon/oversikt over mer moderne algoritmer. Les gjerne hele denne, selv om du ikke forstår alt med en gang.
En annen oversikt over ulike algoritmer finner du på Wikipedia:
(se også de ulike linkene til diverse algoritmer nederst på siden)
Hvis du vil begynne å forstå mer om disse mer avanserte algoritmene må du brette opp ermene og begynne å lære om tallteori. Her nedenfor er noen steder å begynne. Til å begynne med bør du lære om begrepene kongruente tall, største felles divisor (GCD på engelsk), minste felles multiplum (LCD på engelsk) og teori rundt kongruenser inkludert Euler’s teorem, Fermat’s lille teorem og “Chinese Remainder Theorem”. Deretter kan du evt. prøve deg på å forstå og programmere noen halv-avanserte faktoriseringsalgoritmer som Pollard’s rho method, og Pollard’s (p-1) method.
En del forklaring finner du på Wikipedia (klikk deg videre fra disse to sidene til andre)
Og her er litt teori fra Khan Academy:
Disse notatene skrev jeg selv når jeg underviste på universitetet i Nairobi.
Jeg ville begynt her, eller evt. i læreboken for faget Matematikk X. Evt. kan jeg kopiere litt fra denne boken og sende til deg per post – minn meg på dette hvis du er interessert i å ha en tekst som er på norsk.
Her er en liten “bok” av William Chen, som også har mange andre veldig gode ressurser på sin hjemmeside innenfor Calculus m.m. Disse notatene er veldig bra, men det er en utfordring å bli vant med å “lese” matte. Mye av dette stoffet er ikke så vanskelig egentlig, men å lese det på egen hånd, uten noen som forklarer, er ikke helt lett.
Hjemmesiden til William Stein finner du her:
Den inneholder enormt mye spennende stoff. Her er et utvalg:
William Stein er en av personene bak programmeringsspråket SAGE, som er utviklet spesielt for teoretisk matematikk, blant annet for å studere elliptiske kurver, som brukes i noen av de mest avanserte faktoriseringsalgoritmene vi kjenner til.
Her er en annen link som kan være interessant. Den beskriver den berømte “PRIMES is in P”-artikkelen som kom ut for noen år siden.
Nå har jeg prøvd å velge ut noen av de aller beste referansene på området, men selvfølgelig finnes det utrolig mye mere på nettet og i ulike bøker. Å surfe rundt på nettet kan være til stor inspirasjon, men for å virkelig lære ting skikkelig må du sette deg ned med en eller to bøker, lese teorien nøye og arbeide med oppgavene.
Mvh Andreas