MATA2520 Set theory and graphs (5 cr)

Study level:
Intermediate studies
Grading scale:
0-5
Language:
English, Finnish
Responsible organisation:
Department of Mathematics and Statistics
Curriculum periods:
2024-2025, 2025-2026, 2026-2027, 2027-2028

Tweet text

Opintojakso on tarkoitettu tekniikan alan opiskelijoille ja ohjelmiin hakemista suunnitteleville, sekä tilastotieteen ja datatieteen opiskelijoille.

Description

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

Learning outcomes

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

Additional information

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. 


Description of prerequisites

MATA2700 Todistamisen ja päättelyn perusteet tekniikan alalle

tai vastaavat matemaattiset taidot.

Literature

  • Oscar Levin: Discrete Mathematics, An Open Introduction
  • Margaret M. Fleck: Building Blocks for Theoretical Computer Science

Completion methods

Method 1

Evaluation criteria:
Harjoitukset ja kurssitentti. Tarkemmat arviointiperusteet ilmoitetaan opetusohjelmassa.
Time of teaching:
Period 1
Select all marked parts

Method 2

Evaluation criteria:
Lopputentin pistemäärä
Select all marked parts
Parts of the completion methods
x

Participation in teaching (5 cr)

Type:
Participation in teaching
Grading scale:
0-5
Language:
English, Finnish

Teaching

x

Exam (5 cr)

Type:
Exam
Grading scale:
0-5
Language:
English, Finnish

Teaching