luku01.tex

\chapter{Johdanto}

Kisakoodauksessa yhdistyy kaksi asiaa:
(1) algoritmien suunnittelu ja
(2) algoritmien toteutus.

\key{Algoritmien suunnittelu} on loogista ongelmanratkaisua,
joka on lähellä matematiikkaa.
Se vaatii kykyä analysoida ongelmia ja
ratkaista niitä luovasti.
Tehtävän ratkaisevan algoritmin tulee olla sekä
toimiva että tehokas,
ja usein nimenomaan tehokkaan algoritmin
keksiminen on tehtävän ydin.

Teoreettiset tiedot algoritmiikasta
ovat kisakoodarille kullanarvoisia.
Tyypillisesti tehtävän ratkaisu on yhdistelmä tunnettuja
tekniikoita sekä omia oivalluksia.
Kisakoodauksessa esiintyvät menetelmät ovat myös
algoritmiikan tieteellisen tutkimuksen perusta.

\key{Algoritmien toteutus} edellyttää hyvää ohjelmointitaitoa.
Kisakoodauksessa tehtävän ratkaisun arvostelu tapahtuu
testaamalla toteutettua algoritmia
joukolla testisyötteitä.
Ei siis riitä, että algoritmin idea on oikea,
vaan algoritmi pitää myös onnistua toteuttamaan virheettömästi.

Hyvä kisakoodi on suoraviivaista ja tiivistä.
Ratkaisu täytyy pystyä kirjoittamaan nopeasti,
koska kisoissa on vain vähän aikaa.
Toisin kuin tavallisessa ohjelmistokehityksessä,
ratkaisut ovat lyhyitä
(yleensä enintään joitakin satoja rivejä)
eikä koodia tarvitse ylläpitää kilpailun jälkeen.

\section{Ohjelmointikielet}

\index{ohjelmointikieli@ohjelmointikieli}

Tällä hetkellä yleisimmät koodauskisoissa
käytetyt ohjelmointikielet ovat C++, Python ja Java.
Esimerkiksi vuoden 2016 Google Code Jamissa
3000 parhaan osallistujan joukossa
73 \% käytti C++:aa,
15 \% käytti Pythonia ja
10 \% käytti Javaa\footnote{\url{https://www.go-hero.net/jam/16}}.
Jotkut osallistujat käyttivät myös useita näistä kielistä.

Monen mielestä C++ on paras
valinta kisakoodauksen kieleksi,
ja se on yleensä aina käytettävissä
kisajärjestelmissä.
C++:n etuja ovat, että sillä
toteutettu koodi on hyvin tehokasta
ja kielen standardikirjastoon
kuuluu kattava valikoima valmiita
tietorakenteita ja algoritmeja.

Toisaalta on hyvä hallita useita kieliä
ja tuntea niiden edut.
Esimerkiksi jos tehtävässä esiintyy
suuria kokonaislukuja,
Python voi olla hyvä valinta,
koska kielessä on sisäänrakennettuna
suurten kokonaislukujen käsittely.
Toisaalta tehtävät yritetään yleensä laatia niin,
ettei tietyn kielen ominaisuuksista
ole kohtuutonta etua tehtävän ratkaisussa.

Kaikki tämän kirjan esimerkit on kirjoitettu C++:lla,
ja niissä on käytetty runsaasti C++:n valmiita 
tietorakenteita ja algoritmeja.
Käytössä on C++:n standardi C++11,
jota voi nykyään käyttää useimmissa kisoissa.
Jos et vielä osaa ohjelmoida C++:lla,
nyt on hyvä hetki alkaa opetella.

\subsubsection{C++-koodipohja}

Tyypillinen C++-koodin pohja kisakoodausta varten
näyttää seuraavalta:

\begin{lstlisting}
#include <bits/stdc++.h>

using namespace std;

int main() {
    // koodi tulee tähän
}
\end{lstlisting}

Koodin alussa oleva \texttt{\#include}-rivi
on \texttt{g++}-kääntäjän tarjoama tapa
ottaa mukaan kaikki standardikirjaston sisältö.
Tämän ansiosta koodissa ei tarvitse ottaa
erikseen mukaan kirjastoja \texttt{iostream},
\texttt{vector}, \texttt{algorithm}, jne.,
vaan ne kaikki ovat käytettävissä automaattisesti.

Seuraavana oleva \texttt{using}-rivi määrittää,
että standardikirjaston sisältöä voi käyttää
suoraan koodissa.
Ilman \texttt{using}-riviä koodissa pitäisi
kirjoittaa esimerkiksi \texttt{std::cout},
mutta \texttt{using}-rivin ansiosta riittää
kirjoittaa \texttt{cout}.

Koodin voi kääntää esimerkiksi
seuraavalla komennolla:

\begin{lstlisting}
g++ -std=c++11 -O2 -Wall koodi.cpp -o koodi
\end{lstlisting}

Komento tuottaa kooditiedostosta \texttt{koodi.cpp}
binääritiedoston \texttt{koodi}.
Kääntäjä noudattaa C++11-standardia
(\texttt{-std=c++11}),
optimoi koodia käännöksen aikana (\texttt{-O2})
ja näyttää varoituksia
mahdollisista virheistä (\texttt{-Wall}).

\section{Syöte ja tuloste}

\index{syxte ja tuloste@syöte ja tuloste}

Useimmissa kisoissa käytetään
standardivirtoja syötteen lukemiseen ja tulosteen
kirjoittamiseen.
C++:ssa standardivirrat ovat \texttt{cin}
lukemiseen
ja \texttt{cout} tulostamiseen. Lisäksi voi käyttää
C:n funktioita \texttt{scanf} ja \texttt{printf}.

Ohjelmalle tuleva syöte muodostuu yleensä
luvuista ja merkkijonoista,
joiden välissä on välilyöntejä ja rivinvaihtoja.
Niitä voi lukea \texttt{cin}-virrasta näin:

\begin{lstlisting}
int a, b;
string x;
cin >> a >> b >> x;
\end{lstlisting}

Tällainen koodi toimii aina,
kunhan jokaisen luettavan alkion välissä
on ainakin yksi rivinvaihto tai välilyönti.
Esimerkiksi yllä oleva koodi hyväksyy
molemmat seuraavat syötteet:
\begin{lstlisting}
123 456 apina
\end{lstlisting}
\begin{lstlisting}
123    456
apina
\end{lstlisting}
Tulostaminen tapahtuu puolestaan
\texttt{cout}-virran kautta:
\begin{lstlisting}
int a = 123, b = 456;
string x = "apina";
cout << a << " " << b << " " << x << "\n";
\end{lstlisting}

Syötteen ja tulosteen käsittely on joskus
pullonkaula ohjelmassa.
Seuraavat rivit koodin alussa tehostavat
syötteen ja tulosteen käsittelyä:

\begin{lstlisting}
ios_base::sync_with_stdio(0);
cin.tie(0);
\end{lstlisting}

Huomaa myös, että rivinvaihto \texttt{"\textbackslash n"}
toimii tulostuksessa nopeammin kuin \texttt{endl},
koska \texttt{endl} aiheuttaa
aina flush-operaation.

C:n funktiot \texttt{scanf}
ja \texttt{printf} ovat vaihtoehto
C++:n standardivirroille.
Ne ovat yleensä hieman nopeampia,
mutta toisaalta vaikeakäyttöisempiä.
Seuraava koodi lukee kaksi kokonaislukua syötteestä:
\begin{lstlisting}
int a, b;
scanf("%d %d", &a, &b);
\end{lstlisting}
Seuraava koodi taas tulostaa kaksi kokonaislukua:
\begin{lstlisting}
int a = 123, b = 456;
printf("%d %d\n", a, b);
\end{lstlisting}

Joskus ohjelman täytyy lukea syötteestä
kokonainen rivi tietoa
välittämättä rivin välilyönneistä.
Tämä onnistuu seuraavasti funktiolla
\texttt{getline}:

\begin{lstlisting}
string s;
getline(cin, s);
\end{lstlisting}

Jos syötteessä olevan tiedon määrä ei ole tiedossa
etukäteen, seuraavanlainen silmukka on kätevä:
\begin{lstlisting}
while (cin >> x) {
    // koodia
}
\end{lstlisting}
Tämä silmukka lukee syötettä alkio
kerrallaan, kunnes syöte loppuu.

Joissakin kisajärjestelmissä syötteen ja tulosteen
käsittelyyn käytetään tiedostoja. Helppo ratkaisu tähän
on kirjoittaa koodi tavallisesti
standardivirtoja käyttäen,
mutta kirjoittaa alkuun seuraavat rivit:
\begin{lstlisting}
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
\end{lstlisting}
Tämän seurauksena koodi lukee syötteen tiedostosta
''input.txt'' ja kirjoittaa tulosteen
tiedostoon ''output.txt''.

\section{Lukujen käsittely}

\index{kokonaisluku@kokonaisluku}

\subsubsection{Kokonaisluvut}

Tavallisin kokonaislukutyyppi kisakoodauksessa on \texttt{int}.
Tämä on 32-bittinen tyyppi,
jonka sallittu lukuväli on $-2^{31} \ldots 2^{31}-1$
eli noin $-2 \cdot 10^9 \ldots 2 \cdot 10^9$.
Jos tyyppi \texttt{int} ei riitä, sen sijaan voi käyttää
64-bittistä tyyppiä
\texttt{long long}, jonka lukuväli on $-2^{63} \ldots 2^{63}-1$
eli noin $-9 \cdot 10^{18} \ldots 9 \cdot 10^{18}$.

Seuraava koodi määrittelee
\texttt{long long} -muuttujan:
\begin{lstlisting}
long long x = 123456789123456789LL;
\end{lstlisting}
Luvun lopussa oleva \texttt{LL}
ilmaisee, että luku on \texttt{long long} -tyyppinen.

Yleinen virhe \texttt{long long} -tyypin käytössä on,
että jossain kohtaa käytetään kuitenkin \texttt{int}-tyyppiä.
Esimerkiksi tässä koodissa on salakavala virhe:

\begin{lstlisting}
int a = 123456789;
long long b = a*a;
cout << b << "\n"; // -1757895751
\end{lstlisting}

Vaikka muuttuja \texttt{b} on \texttt{long long} -tyyppinen,
laskussa \texttt{a*a} molemmat osat ovat \texttt{int}-tyyppisiä
ja myös laskun tulos on \texttt{int}-tyyppinen.
Tämän vuoksi muuttujaan \texttt{b} ilmestyy väärä luku.
Ongelman voi korjata vaihtamalla muuttujan \texttt{a}
tyypiksi \texttt{long long} tai kirjoittamalla
laskun muodossa \texttt{(long long)a*a}.

Yleensä tehtävät laaditaan niin, että tyypin
\texttt{long long} käyttäminen riittää.
On kuitenkin hyvä tietää, että
\texttt{g++}-kääntäjä tarjoaa myös 128-bittisen
tyypin \texttt{\_\_int128\_t}, jonka lukuväli on
$-2^{127} \ldots 2^{127}-1$ eli noin $-10^{38} \ldots 10^{38}$.
Tämä tyyppi ei kuitenkaan ole käytettävissä kaikissa kisajärjestelmissä.

\subsubsection{Vastaus modulossa}

\index{jakojxxnnos@jakojäännös}
\index{modulolaskenta@modulolaskenta}

Luvun $x$ jakojäännös luvulla $m$
merkitään $x \bmod m$.
Esimerkiksi $17 \bmod 5 = 2$,
koska $17 = 3 \cdot 5 + 2$.

Joskus tehtävän vastaus on hyvin suuri kokonaisluku,
mutta vastaus riittää ilmoittaa ''modulo $m$''
eli vastauksen jakojäännös luvulla $m$
(esimerkiksi ''modulo $10^9+7$'').
Ideana on, että vaikka todellinen vastaus
voi olla hyvin suuri luku,
tehtävässä riittää käyttää tyyppejä \texttt{int} ja \texttt{long long}.

Tärkeä jakojäännöksen ominaisuus on,
että yhteen-, vähennys- ja kertolaskussa
jakojäännöksen voi laskea ennen laskutoimitusta:

\[
\begin{array}{rcr}
(a+b) \bmod m & = & (a \bmod m + b \bmod m) \bmod m \\
(a-b) \bmod m & = & (a \bmod m - b \bmod m) \bmod m \\
(a \cdot b) \bmod m & = & (a \bmod m \cdot b \bmod m) \bmod m
\end{array}
\]

Näiden kaavojen ansiosta
jokaisen laskun vaiheen jälkeen voi laskea jakojäännöksen
eivätkä luvut kasva liian suuriksi.

Esimerkiksi seuraava koodi
laskee luvun $n$ kertoman $n!$ modulo $m$:
\begin{lstlisting}
long long x = 1;
for (int i = 2; i <= n i++) {
    x = (x*i)%m;
}
cout << x << "\n";
\end{lstlisting}

Yleensä vastaus modulossa tulee antaa niin,
että se on välillä $0\ldots m-1$.
Kuitenkin C++:ssa ja
muissa kielissä negatiivisen
luvun jakojäännös voi olla negatiivinen.
Helppo tapa varmistaa, että jakojäännös ei ole negatiivinen,
on laskea ensin jakojäännös tavallisesti ja lisätä sitten $m$,
jos tulos on negatiivinen:
\begin{lstlisting}
x = x%m;
if (x < 0) x += m;
\end{lstlisting}
Tämä on tarpeen kuitenkin vain silloin,
kun jakojäännös voi olla negatiivinen
koodissa olevien vähennyslaskujen vuoksi.

\subsubsection{Liukuluvut}

\index{liukuluku@liukuluku}

Tavalliset liukulukutyypit kisakoodauksessa
ovat 64-bittinen \texttt{double}
sekä \texttt{g++}-kääntäjän
laajennoksena
80-bittinen \texttt{long double}.
Yleensä \texttt{double} riittää,
mutta \texttt{long double} tuo tarvittaessa
lisää tarkkuutta.

Vastauksena oleva liukuluku täytyy yleensä tulostaa
tietyllä tarkkuudella.
Tämä onnistuu helpoiten \texttt{printf}-funktiolla,
jolle voi antaa desimaalien määrän.
Esimerkiksi seuraava koodi tulostaa luvun 9
desimaalin tarkkuudella:

\begin{lstlisting}
printf("%.9f\n", x);
\end{lstlisting}

Liukulukujen käyttämisessä on hankaluutena,
että kaikkia lukuja ei voi esittää tarkasti
liukulukuina vaan tapahtuu pyöristysvirheitä.
Esimerkiksi seuraava koodi tuottaa yllättävän tuloksen:

\begin{lstlisting}
double x = 0.3*3+0.1;
printf("%.20f\n", x); // 0.99999999999999988898
\end{lstlisting}

Pyöristysvirheen vuoksi muuttujan \texttt{x}
sisällöksi tulee hieman alle 1,
vaikka sen arvo tarkasti laskettuna olisi 1.

Liukulukuja on vaarallista vertailla \texttt{==}-merkinnällä,
koska vaikka luvut olisivat todellisuudessa samat,
niissä voi olla pientä eroa pyöristysvirheiden vuoksi.
Parempi tapa vertailla liukulukuja on
tulkita kaksi lukua samoiksi, jos niiden ero on alle $\varepsilon$,
jossa $\varepsilon$ on sopiva pieni luku.

Käytännössä vertailun voi toteuttaa seuraavasti ($\varepsilon=10^{-9}$):

\begin{lstlisting}
if (abs(a-b) < 1e-9) {
    // a ja b ovat yhtä suuret
}
\end{lstlisting}

Huomaa, että
vaikka liukuluvut ovat epätarkkoja, niillä voi esittää
tarkasti kokonaislukuja tiettyyn rajaan asti.
Esimerkiksi \texttt{double}-tyypillä voi esittää
tarkasti kaikki kokonaisluvut, joiden itseisarvo
on enintään $2^{53}$.

\section{Koodin lyhentäminen}

Kisakoodauksessa ihanteena on lyhyt koodi,
koska algoritmi täytyy pystyä toteuttamaan
mahdollisimman nopeasti.
Monet kisakoodarit käyttävätkin lyhennysmerkintöjä
tietotyypeille ja muille koodin osille.

\subsubsection{Tyyppinimet}
\index{tuppdef@\texttt{typedef}}
Komennolla \texttt{typedef} voi antaa lyhyemmän
nimen tietotyypille.
Esimerkiksi nimi \texttt{long long} on pitkä,
joten tyypille voi antaa lyhyemmän nimen \texttt{ll}:
\begin{lstlisting}
typedef long long ll;
\end{lstlisting}
Tämän jälkeen koodin
\begin{lstlisting}
long long a = 123456789;
long long b = 987654321;
cout << a*b << "\n";
\end{lstlisting}
voi lyhentää seuraavasti:
\begin{lstlisting}
ll a = 123456789;
ll b = 987654321;
cout << a*b << "\n";
\end{lstlisting}

Komentoa \texttt{typedef} voi käyttää myös
monimutkaisempien tyyppien kanssa.
Esimerkiksi seuraava koodi antaa nimen \texttt{vi}
kokonaisluvuista muodostuvalle vektorille
sekä nimen \texttt{pi} kaksi
kokonaislukua sisältävälle parille.
\begin{lstlisting}
typedef vector<int> vi;
typedef pair<int,int> pi;
\end{lstlisting}

\subsubsection{Makrot}
\index{makro}
Toinen tapa lyhentää koodia on määritellä \key{makroja}.
Makro ilmaisee, että tietyt koodissa olevat
merkkijonot korvataan toisilla ennen koodin
kääntämistä.
C++:ssa makro määritellään
esikääntäjän komennolla \texttt{\#define}.

Määritellään esimerkiksi seuraavat makrot:
\begin{lstlisting}
#define F first
#define S second
#define PB push_back
#define MP make_pair
\end{lstlisting}
Tämän jälkeen koodin
\begin{lstlisting}
v.push_back(make_pair(y1,x1));
v.push_back(make_pair(y2,x2));
int d = v[i].first+v[i].second;
\end{lstlisting}
voi kirjoittaa lyhyemmin seuraavasti:
\begin{lstlisting}
v.PB(MP(y1,x1));
v.PB(MP(y2,x2));
int d = v[i].F+v[i].S;
\end{lstlisting}

Makro on mahdollista määritellä myös niin,
että sille voi antaa parametreja.
Tämän ansiosta makrolla voi lyhentää esimerkiksi
komentorakenteita.
Määritellään esimerkiksi seuraava makro:
\begin{lstlisting}
#define REP(i,a,b) for (int i = a; i <= b; i++)
\end{lstlisting}
Tämän jälkeen koodin
\begin{lstlisting}
for (int i = 1; i <= n; i++) {
    haku(i);
}
\end{lstlisting}
voi lyhentää seuraavasti:
\begin{lstlisting}
REP(i,1,n) {
    haku(i);
}
\end{lstlisting}

\section{Matematiikka}

Matematiikka on tärkeässä asemassa kisakoodauksessa,
ja menestyvän kisakoodarin täytyy osata myös
hyvin matematiikkaa.
Käymme seuraavaksi läpi joukon keskeisiä
matematiikan käsitteitä ja kaavoja.
Palaamme moniin aiheisiin myöhemmin tarkemmin kirjan aikana.

\subsubsection{Summakaavat}

Jokaiselle summalle muotoa
\[\sum_{x=1}^n x^k = 1^k+2^k+3^k+\ldots+n^k\]
on olemassa laskukaava,
kun $k$ on jokin positiivinen kokonaisluku.
Tällainen laskukaava on aina astetta $k+1$
oleva polynomi. Esimerkiksi
\[\sum_{x=1}^n x = 1+2+3+\ldots+n = \frac{n(n+1)}{2}\]
ja
\[\sum_{x=1}^n x^2 = 1^2+2^2+3^2+\ldots+n^2 = \frac{n(n+1)(2n+1)}{6}.\]

\key{Aritmeettinen summa} on summa, \index{aritmeettinen summa@aritmeettinen summa}
jossa jokaisen vierekkäisen luvun erotus on vakio.
Esimerkiksi
\[3+7+11+15\]
on aritmeettinen summa,
jossa vakio on 4.
Aritmeettinen summa voidaan laskea kaavalla
\[\frac{n(a+b)}{2},\]
jossa summan ensimmäinen luku on $a$,
viimeinen luku on $b$ ja lukujen määrä on $n$.
Esimerkiksi
\[3+7+11+15=\frac{4 \cdot (3+15)}{2} = 36.\]
Kaava perustuu siihen, että summa muodostuu $n$ luvusta
ja luvun suuruus on keskimäärin $(a+b)/2$.

\index{geometrinen summa@geometrinen summa}
\key{Geometrinen summa} on summa,
jossa jokaisen vierekkäisen luvun suhde on vakio.
Esimerkiksi
\[3+6+12+24\]
on geometrinen summa,
jossa vakio on 2.
Geometrinen summa voidaan laskea kaavalla
\[\frac{bx-a}{x-1},\]
jossa summan ensimmäinen luku on $a$,
viimeinen luku on $b$ ja vierekkäisten lukujen suhde on $x$.
Esimerkiksi
\[3+6+12+24=\frac{24 \cdot 2 - 3}{2-1} = 45.\]

Geometrisen summan kaavan voi johtaa merkitsemällä
\[ S = a + ax + ax^2 + \cdots + b .\] 
Kertomalla molemmat puolet $x$:llä saadaan
\[ xS = ax + ax^2 + ax^3 + \cdots + bx,\]
josta kaava seuraa ratkaisemalla yhtälön
\[ xS-S = bx-a.\]

Geometrisen summan erikoistapaus on usein kätevä kaava
\[1+2+4+8+\ldots+2^{n-1}=2^n-1.\]

% Geometrisen summan sukulainen on
% \[x+2x^2+3x^3+\cdots+k x^k = \frac{kx^{k+2}-(k+1)x^{k+1}+x}{(x-1)^2}. \]

\index{harmoninen summa@harmoninen summa}

\key{Harmoninen summa} on summa muotoa
\[ \sum_{x=1}^n \frac{1}{x} = 1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n}.\]

Yläraja harmonisen summan suuruudelle on $\log_2(n)+1$.
Summaa voi näet arvioida ylöspäin
muuttamalla jokaista termiä $1/k$ niin,
että $k$:ksi tulee alempi 2:n potenssi.
Esimerkiksi tapauksessa $n=6$ arvioksi tulee
\[ 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6} \le
1+\frac{1}{2}+\frac{1}{2}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}.\]
Tämän seurauksena summa jakaantuu $\log_2(n)+1$ osaan
($1$, $2 \cdot 1/2$, $4 \cdot 1/4$, jne.),
joista jokaisen summa on enintään 1.

\subsubsection{Joukko-oppi}

\index{joukko-oppi}
\index{joukko@joukko}
\index{leikkaus@leikkaus}
\index{yhdiste@yhdiste}
\index{erotus@erotus}
\index{osajoukko@osajoukko}
\index{perusjoukko}

\key{Joukko} on kokoelma alkioita.
Esimerkiksi joukko
\[X=\{2,4,7\}\]
sisältää alkiot 2, 4 ja 7.
Merkintä $\emptyset$ tarkoittaa tyhjää joukkoa.
Joukon $S$ koko eli alkoiden määrä on $|S|$.
Esimerkiksi äskeisessä joukossa $|X|=3$.

Merkintä $x \in S$ tarkoittaa,
että alkio $x$ on joukossa $S$,
ja merkintä $x \notin S$ tarkoittaa,
että alkio $x$ ei ole joukossa $S$.
Esimerkiksi äskeisessä joukossa
\[4 \in X \hspace{10px}\textrm{ja}\hspace{10px} 5 \notin X.\]

\begin{samepage}
Uusia joukkoja voidaan muodostaa joukko-operaatioilla
seuraavasti:
\begin{itemize}
\item \key{Leikkaus} $A \cap B$ sisältää alkiot,
jotka ovat molemmissa joukoista $A$ ja $B$.
Esimerkiksi jos $A=\{1,2,5\}$ ja $B=\{2,4\}$,
niin $A \cap B = \{2\}$.
\item \key{Yhdiste} $A \cup B$ sisältää alkiot,
jotka ovat ainakin toisessa joukoista $A$ ja $B$.
Esimerkiksi jos $A=\{3,7\}$ ja $B=\{2,3,8\}$,
niin $A \cup B = \{2,3,7,8\}$.
\item \key{Komplementti} $\bar A$ sisältää alkiot,
jotka eivät ole joukossa $A$.
Komplementin tulkinta riippuu siitä, mikä on
\key{perusjoukko} eli joukko, jossa on kaikki
mahdolliset alkiot. Esimerkiksi jos
$A=\{1,2,5,7\}$ ja perusjoukko on $P=\{1,2,\ldots,10\}$,
niin $\bar A = \{3,4,6,8,9,10\}$.
\item \key{Erotus} $A \setminus B = A \cap \bar B$ sisältää alkiot,
jotka ovat joukossa $A$ mutta eivät joukossa $B$.
Huomaa, että $B$:ssä voi olla alkioita,
joita ei ole $A$:ssa.
Esimerkiksi jos $A=\{2,3,7,8\}$ ja $B=\{3,5,8\}$,
niin $A \setminus B = \{2,7\}$.
\end{itemize}
\end{samepage}


Merkintä $A \subset S$ tarkoittaa,
että $A$ on $S$:n \key{osajoukko}
eli jokainen $A$:n alkio esiintyy $S$:ssä.
Joukon $S$ osajoukkojen yhteismäärä on $2^{|S|}$.
Esimerkiksi joukon $\{2,4,7\}$
osajoukot ovat
\begin{center}
$\emptyset$,
$\{2\}$, $\{4\}$, $\{7\}$, $\{2,4\}$, $\{2,7\}$, $\{4,7\}$ ja $\{2,4,7\}$.
\end{center}

Usein esiintyviä joukkoja ovat

\begin{itemize}[noitemsep]
\item $\mathbb{N}$ (luonnolliset luvut),
\item $\mathbb{Z}$ (kokonaisluvut),
\item $\mathbb{Q}$ (rationaaliluvut) ja
\item $\mathbb{R}$ (reaaliluvut).
\end{itemize}

Luonnollisten lukujen joukko $\mathbb{N}$ voidaan määritellä
tilanteesta riippuen kahdella tavalla:
joko $\mathbb{N}=\{0,1,2,\ldots\}$
tai $\mathbb{N}=\{1,2,3,...\}$.

Joukon voi muodostaa myös säännöllä muotoa
\[\{f(n) : n \in S\},\]
missä $f(n)$ on jokin funktio.
Tällainen joukko sisältää kaikki alkiot
$f(n)$, jossa $n$ on valittu joukosta $S$.
Esimerkiksi joukko
\[X=\{2n : n \in \mathbb{Z}\}\]
sisältää kaikki parilliset kokonaisluvut.

\subsubsection{Logiikka}

\index{logiikka@logiikka}
\index{negaatio@negaatio}
\index{konjunktio@konjunktio}
\index{disjunktio@disjunktio}
\index{implikaatio@implikaatio}
\index{ekvivalenssi@ekvivalenssi}

Loogisen lausekkeen arvo on joko \key{tosi} (1) tai
\key{epätosi} (0).
Tärkeimmät loogiset operaatiot ovat
$\lnot$ (\key{negaatio}),
$\land$ (\key{konjunktio}),
$\lor$ (\key{disjunktio}),
$\Rightarrow$ (\key{implikaatio}) sekä
$\Leftrightarrow$ (\key{ekvivalenssi}).
Seuraava taulukko näyttää operaatioiden merkityksen:

\begin{center}
\begin{tabular}{rr|rrrrrrr}
$A$ & $B$ & $\lnot A$ & $\lnot B$ & $A \land B$ & $A \lor B$ & $A \Rightarrow B$ & $A \Leftrightarrow B$ \\
\hline
0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\
1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\
\end{tabular}
\end{center}

Negaatio $\lnot A$ muuttaa lausekkeen käänteiseksi.
Lauseke $A \land B$ on tosi, jos molemmat $A$ ja $B$ ovat tosia,
ja lauseke $A \lor B$ on tosi, jos $A$ tai $B$ on tosi.
Lauseke $A \Rightarrow B$ on tosi,
jos $A$:n ollessa tosi myös $B$ on aina tosi.
Lauseke $A \Leftrightarrow B$ on tosi,
jos $A$:n ja $B$:n totuusarvo on sama.

\index{predikaatti@predikaatti}

\key{Predikaatti} on lauseke, jonka arvo on tosi tai epätosi
riippuen sen parametreista.
Yleensä predikaattia merkitään suurella kirjaimella.
Esimerkiksi voimme määritellä predikaatin $P(x)$,
joka on tosi tarkalleen silloin, kun $x$ on alkuluku.
Tällöin esimerkiksi $P(7)$ on tosi, kun taas $P(8)$ on epätosi.

\index{kvanttori@kvanttori}

\key{Kvanttori} ilmaisee, että looginen
lauseke liittyy jollakin tavalla joukon alkioihin.
Tavalliset kvanttorit
ovat $\forall$ (\key{kaikille}) ja $\exists$ (\key{on olemassa}).
Esimerkiksi
\[\forall x (\exists y (y < x))\]
tarkoittaa, että jokaiselle joukon
alkiolle $x$ on olemassa
jokin joukon alkio $y$ niin, että $y$ on $x$:ää pienempi.
Tämä pätee kokonaislukujen joukossa,
mutta ei päde luonnollisten lukujen joukossa.

Yllä esitettyjen merkintöjä avulla on mahdollista esittää
monenlaisia loogisia väitteitä.
Esimerkiksi
\[\forall x ((x>2 \land \lnot P(x)) \Rightarrow (\exists a (\exists b (x = ab \land a > 1 \land b > 1))))\]
tarkoittaa, että jos luku $x$ on suurempi
kuin 2 eikä ole alkuluku,
niin on olemassa luvut $a$ ja $b$,
joiden tulo on $x$ ja jotka molemmat ovat suurempia kuin 1.
Tämä väite pitää paikkansa kokonaislukujen joukossa.

\subsubsection{Funktioita}

Funktio $\lfloor x \rfloor$ pyöristää luvun $x$
alaspäin kokonaisluvuksi ja
funktio $\lceil x \rceil$ pyöristää luvun $x$
ylöspäin kokonaisluvuksi. Esimerkiksi
\[ \lfloor 3/2 \rfloor = 1 \hspace{10px} \textrm{ja} \hspace{10px} \lceil 3/2 \rceil = 2.\]

Funktiot $\min(x_1,x_2,\ldots,x_n)$
ja $\max(x_1,x_2,\ldots,x_n)$
palauttavat pienimmän ja suurimman
arvoista $x_1,x_2,\ldots,x_n$.
Esimerkiksi
\[ \min(1,2,3)=1 \hspace{10px} \textrm{ja} \hspace{10px} \max(1,2,3)=3.\]

\index{kertoma@kertoma}

\key{Kertoma} $n!$ määritellään
\[\prod_{x=1}^n x = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n\]
tai vaihtoehtoisesti rekursiivisesti
\[
\begin{array}{lcl}
0! & = & 1 \\
n! & = & n \cdot (n-1)! \\
\end{array}
\]

\index{Fibonaccin luku@Fibonaccin luku}

\key{Fibonaccin luvut} esiintyvät monissa erilaisissa yhteyksissä.
Ne määritellään seuraavasti rekursiivisesti:
\[
\begin{array}{lcl}
f(0) & = & 0 \\
f(1) & = & 1 \\
f(n) & = & f(n-1)+f(n-2) \\
\end{array}
\]
Ensimmäiset Fibonaccin luvut ovat
\[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\]
Fibonaccin lukujen laskemiseen on olemassa myös
suljetun muodon kaava
\[f(n)=\frac{(1 + \sqrt{5})^n - (1-\sqrt{5})^n}{2^n \sqrt{5}}.\]

\subsubsection{Logaritmi}

\index{logaritmi@logaritmi}

Luvun $x$
\key{logaritmi} merkitään $\log_k(x)$, missä $k$ on logaritmin kantaluku.
Logaritmin määritelmän mukaan
$\log_k(x)=a$ tarkalleen silloin, kun $k^a=x$.

Algoritmiikassa hyödyllinen tulkinta on,
että logaritmi $\log_k(x)$ ilmaisee, montako kertaa lukua $x$
täytyy jakaa $k$:lla, ennen kuin tulos on 1.
Esimerkiksi $\log_2(32)=5$,
koska lukua 32 täytyy jakaa 2:lla 5 kertaa:

\[32 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \]

Logaritmi tulee usein vastaan algoritmien analyysissa,
koska monessa tehokkaassa algoritmissa jokin asia puolittuu
joka askeleella.
Niinpä logaritmin avulla voi arvioida algoritmin tehokkuutta.

Logaritmille pätee kaava
\[\log_k(ab) = \log_k(a)+\log_k(b),\]
josta seuraa edelleen
\[\log_k(x^n) = n \cdot \log_k(x).\]
Samoin logaritmille pätee
\[\log_k\Big(\frac{a}{b}\Big) = \log_k(a)-\log_k(b).\]
Lisäksi on voimassa kaava
\[\log_u(x) = \frac{\log_k(x)}{\log_k(u)},\]
minkä ansiosta logaritmeja voi laskea mille tahansa kantaluvulle,
jos on keino laskea logaritmeja jollekin kantaluvulle.

\index{luonnollinen logaritmi@luonnollinen logaritmi}
\index{Neperin luku@Neperin luku}

Luvun $x$ \key{luonnollinen logaritmi} $\ln(x)$ on logaritmi, jonka kantaluku on
\key{Neperin luku} $e \approx 2{,}71828$.

Vielä yksi logaritmin ominaisuus on, että
luvun $x$ numeroiden määrä $b$-kantaisessa
lukujärjestelmässä
on $\lfloor \log_b(x)+1 \rfloor$.
Esimerkiksi luvun $123$ esitys
2-järjestelmässä on 1111011 ja
$\lfloor \log_2(123)+1 \rfloor = 7$.