MATA2520 Joukko-oppi ja graafiteoria (5 op)
Opinnon taso:
Aineopinnot
Arviointiasteikko:
0-5
Suorituskieli:
englanti, suomi
Vastuuorganisaatio:
Matematiikan ja tilastotieteen laitos
Opetussuunnitelmakaudet:
2024-2025, 2025-2026, 2026-2027, 2027-2028
Avainteksti
Opintojakso on tarkoitettu tekniikan alan opiskelijoille ja ohjelmiin hakemista suunnitteleville, sekä tilastotieteen ja datatieteen opiskelijoille.
Kuvaus
- Joukko-opin peruskäsitteet
- Relaatiot ja funktiot. Relaatioiden ominaisuuksia. Ekvivalenssiluokat.
- Binääripuut.
- Suuntaamattomat ja suunnatut graafit. Kytketyt ja vahvasti kytketyt komponentit.
- Isomorfismi ja bisimilaarisuus.
Osaamistavoitteet
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
Lisätietoja
Kurssin sisältö on osittain yhtenevä seuraavien kurssien kanssa: 1) MATA140 Johdatus diskreettiin
matematiikkaan,
2) Johdatus verkkoteoriaan
3) Johdatus kombinatoriikkaan
Jos sisällytät kurssin MATA2520 Joukko-oppi ja graafiteoria matematiikan opintokokonaisuuteen, et voi sisällyttää siihen edellä mainittuja kursseja.
Esitietojen kuvaus
MATA2700 Todistamisen ja päättelyn perusteet tekniikan alalle
tai vastaavat matemaattiset taidot.
Kirjallisuus
- Oscar Levin: Discrete Mathematics, An Open Introduction
- Margaret M. Fleck: Building Blocks for Theoretical Computer Science
Suoritustavat
Tapa 1
Arviointiperusteet:
Harjoitukset ja kurssitentti. Tarkemmat arviointiperusteet ilmoitetaan opetusohjelmassa.
Opetusajankohta:
Periodi 1
Valitaan kaikki merkityt osat
Tapa 2
Arviointiperusteet:
Lopputentin pistemäärä
Valitaan kaikki merkityt osat
Suoritustapojen osat
x
Osallistuminen opetukseen (5 op)
Tyyppi:
Osallistuminen opetukseen
Arviointiasteikko:
0-5
Suorituskieli:
englanti, suomi
x
Lopputentti (5 op)
Tyyppi:
Tentti
Arviointiasteikko:
0-5
Suorituskieli:
englanti, suomi