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

Opetus

x

Lopputentti (5 op)

Tyyppi:
Tentti
Arviointiasteikko:
0-5
Suorituskieli:
englanti, suomi

Opetus