SISÄLLYSLUETTELO

1. JOUKOT, RELAATIOT JA KUVAUKSET

1.1. Joukko-oppia ja matriisilaskentaa

: Merkinnät ja peruskäsitteet - Joukkoalgebraa - Täydellisen induktion periaate - Induktiotodistus - Kokonaislukujen jakoyhtälö - Alkuluvuista- Eratosteneen algoritmi - Karteesinen tulo ja matriisi - Matriisien laskutoimitukset - Totuusarvo- ja kokonaislukumatriisit - Ei-järjestetty tulo

1.2. Relaatio ja sen sulkeuma

: Määritelmä ja käsitteitä - Relaation esitystapoja - Käänteisrelaatio ja relaatioiden yhdistäminen - Käänteis- ja tulorelaation matriisit - Relaatioiden joukko-opilliset operaatiot - Kuvaukset eli funktiot - Muita relaatiotyyppejä - Relaation sulkeuma

1.3. Ekvivalenssirelaatio

: Ekvivalenssiluokat - Ositukset

1.4. Joukkojen mahtavuuksista

: Mahtavuuksien vertailu - Joukon kardinaliteetti

1.5. Äärelliset ja äärettömät joukot

: Äärelliset joukot - Laatikkoperiaate - ^*Äärettömistä joukoista

1.6. Osajoukot ja ositukset

: Potenssijoukko - Karakteristinen funktio - Summa- ja erotusperiaate - Äärellisen joukon ositukset - Stirlingin kolmio

2. VERKOT

2.1. Suuntaamaton verkko

: Määritelmiä ja käsitteitä - Äärellisten verkkojen esitystapoja - Ketjut ja yhtenäisyys - Yhtenäisyyden testaus - Kaksiyhtenäisyys - Hamiltonin ketjut - Triviaali menetelmä - Välttämättömiä ehtoja - Riittäviä ehtoja - Eulerin ketjut - Algoritmi Eulerin ketjun löytämiseksi - Suuntaamattomat puut - Virittävät puut - ^*Virittävien puiden lukumäärä

2.2. Suunnattu verkko

: Määritelmiä ja käsitteitä - Äärellisten suunnattujen verkkojen esitystapoja - Polut ja yhtenäisyys - ^*Suuntaamattoman verkon suunnistaminen - Hamiltonin polut - Algoritmeja Hamiltonin polun löytämiseksi - Eulerin polut - De Bruijnin jonot - Suunnatut puut

2.3. Isomorfia, planaarisuus ja muita verkko-ongelmia

Verkkojen isomorfisuudesta - Taso- vai avaruusverkko? - Kartan väritys - Painotetuista verkoista

3. JÄRJESTETYT JOUKOT JA HILAT

3.1. Järjestetty joukko

: Järjestys ja duaaliperiaate - Äärimmäiset alkiot sekä infimum ja supremum - ^*Pienimmän ylärajan ominaisuus - Järjestetty joukko verkkona ja Hassen kaaviona - Maksimaalisen alkion olemassaolo - Järjestysisomorfia - Täydellisesti järjestetty joukko

3.2. Hila

: Hilan määritelmä ja esimerkkejä - Hilan äärimmäiset alkiot - Hilan laskutoimitukset - Jaottomat alkiot ja hajotelmat - Distributiivinen hila - Boolen hila

4. LUKUMÄÄRÄONGELMISTA

4.1. Kombinatoriikkaa

: Summaperiaate - Tuloperiaate - Summaperiaatteen ja tuloperiaatteen probabilistinen tulkinta - Variaatiot ja kombinaatiot - Osittelut

4.2. Generoivat funktiot ja kombinatoriikka

: Sarjojen laskutoimitukset - Sarjoja koskevia kaavoja

4.3. Sijoittelu- ja partitio-ongelmat

: Sijoittelut - Yleistetty sijoitteluongelma - Partitioista

5. REKURSIOKAAVOISTA

5.1. Rekursiokaava ja differenssiyhtälö

: Rekursiokaava - Rekursiivisesta ohjelmoinnista - Differenssiyhtälöistä - Rekursiokaavojen käyttötilanteita - Rekursiokaavan ratkaiseminen - Kompleksiluvuista - Lineaarinen rekursiokaava

5.2. Homogeeninen rekursiokaava

100

: Yleinen ratkaisu - Alkuarvotehtävä

5.3. Lineaarinen vakiokertoiminen rekursiokaava

103

: Yritemenetelmä

5.4. Rekursiokaava ja generoiva funktio

106

: Esimerkkejä

^*5.5. Lineaarinen rekursiokaava generoivalla funktiolla

109

: Funktionaaliyhtälö g = [(F+q)/(p)] - Karakteristinen yhtälö

5.6. Asymptoottinen arviointi

111

5.7. "Hajota ja hallitse"-rekursiokaavat

114

Kirjallisuusluettelo

119

File translated from T_EX by T_TH, version 3.33.
On 02 Apr 2003, 20:07.