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 kongruent 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 kongruent B + C (mod N)
AD kongruent 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
 

1.6 Mer matematikk

Mer matematikk finner du her.