MATA2520 Joukko-oppi ja graafiteoria (5 op)

• Joukko-opin peruskäsitteet
• Relaatiot ja funktiot. Relaatioiden ominaisuuksia. Ekvivalenssiluokat.
• Binääripuut.
• Suuntaamattomat ja suunnatut graafit. Kytketyt ja vahvasti kytketyt komponentit.
• Isomorfismi ja bisimilaarisuus.

Opintojakson suorittamisen jälkeen opiskelija

• tuntee karteesisen tulon ja sen yhteyden monesta osasta koostuvaan tietoon
• tuntee potenssijoukon käsitteen
• osaa laskea äärellisten joukkojen kokoja inkluusio-ekskluusioperiaatteen mukaan sekä tulo- ja potenssijoukon koon
• osaa käyttää refleksiivisyyden, symmetrisyyden, antisymmetrisyyden ja transitiivisuuden määritelmiä yksinkertaisissa binäärirelaatioita koskevissa päättelyissä
• hallitsee ekvivalenssin ja järjestysrelaation käsitteet, sekä ekvivalenssiluokkien ja osituksen välisen suhteen
• tuntee funktion, funktioiden yhdistämisen, bijektion, käänteisfunktion, injektion ja surjektion käsitteet
• tuntee binääripuun käsitteen ja osaa käydä binääripuun läpi esi-, keski- ja jälkijärjestyksessä
• osaa suuntaamattoman ja suunnatun graafin määritelmät
• hallitsee graafeihin liittyviä käsitteitä: solmu, kaari, polku, silmukka, kierros, kytketty komponentti, vahvasti kytketty komponentti
• on tutustunut graafien isomorfismiin ja bisimilaarisuuteen, ja tietää niiden yhteyden ekvivalenssiluokkiin sekä tietokoneohjelmien käyttäytymiseen
• tunnistaa milloin kyse on graafista määritelmän mukaisena graafina ja milloin isomorfisten määritelmän mukaisten graafien ekvivalenssiluokkana

MATA2700 Todistamisen ja päättelyn perusteet tekniikan alalle