Algoritmer og datastrukturer
En del av tegnene i dette avsnittet (f.eks. tegnet for integrasjon) kan bli vist feil i noen nettlesere på noen plattformer. Tegnene krever fontene fra Microsoft Office-pakken.
1. Litt matematikk
1.1 Notasjonen (gjelder også for Kalkulus-sidene)
(i=x, y)
x er nedre grense, y er øvre (i litteraturen er det vanlig å skrive nedre grense under sigma-tegnet, og øvre over).
^ betyr "opphøyd i" .
ca= brukes istedenfor det buede lik-tegnet, og betyr "cirka lik".
log(x) er en logaritme med grunntal (base) x.
!= står for "ikke lik".
Disse benyttes bare på Kalkulus-sidene:
ò
[a,b] f(x) dx er integralet av f(x) over intervallet [a, b]
conj(x) betyr den konjugerte av x. Hvis x er et komplekst tall,
betyr conj(x) den komplekskonjugerte av x.
sup står for supremum, minste øvre skranke
inf står for infimun, største nedre skranke
1.2 Serier
(sigma) betyr å summere.
Du skal summere resultatene av uttrykket som følger etter sigma-tegnet med verdier innsatt for 'i'.
Aritmetiske rekker
(i=1,10) i = 1 + 2 + 3 + 4 + 5
+ 6 + 7 + 8 + 9 + 10 = (1+10)+(2+9)+(3+8)+(4+7)+(5+6)=5*11=55
dvs. at
(i=1, N) i = (N+1) * (N/2) ca=
N^2/2 (hvis N er stor)
Geometriske rekker
(i=1,10) 2^i = 2 + 4 + 8 + ...
+ 1024 = ...
(i=0, 
)
(1/2)^i = 2, fordi (1/2)^0 + (1/2)^1 + (1/2)^2 + (1/2)^3 ... = 1 + 1/2
+ 1/4 + 1/8 ... går mot 2. Skulle vi faktisk fortsatt rekken i
det uendelige, ville vi nådd tallet 2.
En geometrisk rekke, der hvert tall er mindre enn det foregående,
vil konvergere
0 < A < 1, (i=0,)
A^i = 1 / (1-A)
1.2.1 Om ikke "telleren" er med i summen
(i=1,10) 2+3 = 10(2+3) = 50
dvs. at
(i=1,N) f(x) = N * f(x)
1.3 Eksponenter
X^A * X^B = X^(A+B)X^A / X^B = X^(A-B)
(X^A)^B = X^(AB)
X^N + X^N = 2X^N
2^N + 2^N = 2^(N+1)
1.4 Logaritmer
I computer-vitenskap bruker vi 2 som grunntall i alle logaritmer når ikke annet er spesifisert.Definisjon: X^A = B, iff log(X) B = A. Her er X grunntallet (basen).
En logaritmisk funksjon øker med 1 når argumentet dobles.
Oppgave: hvor mange ganger må vi halvere en mengde på 1024
gjenstander før vi har tilbake 1?
Svar: 10, fordi log 1024 = 10. Legg merke til: hvis vi har dobbelt
så mange gjenstander, må vi bare halvere en gang til.
log 0 = eksisterer ikke
log 1 = 0
log 2 = 1
log 1,024 = 10
Teorem: log(A) B = log(C) B / log(C) A , A,
B, C > 0, A != 1
Bevis:
X = log(C) B
Y = log(C) A
Z = log(A) B
Definisjonen gir:
C^X = B
C^Y = A
A^Z = B
som gir oss
B = C^X = (C^Y)^Z
derfor er X = YZ, som gir Z = X/Y, som beviser teoremet.
Flere teoremer:
log AB = log A + log B , A, B > 0
log A/B = log A - log B
log (A^B) = B log A
log X < X for alle X > 0
1.5 Modulær aritmetikk
A er kongruent til B modulo N (A
B (mod N), hvis N deler A-B (dvs. at resten er den samme uansett om det
er A eller B som blir delt på N.)
A + C
B + C (mod N)
AD
BD (mod N)
Modulær aritmetikk er kommutativ, assosiativ og distributiv:
(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a - b) mod n = ((a mod n) - (b mod n)) mod n
(a * b) mod n = ((a mod n) * (b mod n)) mod n
(a * (b + c)) mod n = (((a * b) mod n) + ((a * c) mod n)) mod n