MATA2520 Joukko-oppi ja graafiteoria (5 op)

Opinnon taso:
Aineopinnot
Arviointiasteikko:
0-5
Suorituskieli:
englanti, suomi
Vastuuorganisaatio:
Matematiikan ja tilastotieteen laitos
Opetussuunnitelmakaudet:
2021-2022, 2022-2023, 2023-2024

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

Opintojaksoista MATA140 Johdatus diskreettiin matematiikkaan sekä MATAxxxx Joukko-oppi ja graafiteoria molempia ei voi sisällyttää matematiikan opintokokonaisuuteen. Opintojakso toteutetaan ensimmäisen kerran lukuvuonna 2022-2023.

Esitietojen kuvaus

MATA2700 Todistamisen ja päättelyn perusteet tekniikan alalle

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