MATA2520 Set theory and graphs (5 cr)

Open the course unit brochure on Sisu
Study level:
Intermediate studies
Grading scale:
0-5
Language:
English, Finnish
Responsible organisation:
Department of Mathematics and Statistics
Curriculum periods:
2021-2022, 2022-2023, 2023-2024

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

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.

Description of prerequisites

MATA2700 Todistamisen ja päättelyn perusteet tekniikan alalle

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