# MAT-02657 Mathematics for Algorithms, 5 cr

#### Lisätiedot

The course will be lectured in English every second year.

Henri Hansen

#### Opetus

 Toteutuskerta Periodi Vastuuhenkilö Suoritusvaatimukset MAT-02657 2019-01 1 Henri Hansen Exam + exercises

#### Osaamistavoitteet

This course enables the student to understand basic set-theoretic and logical notation, and to prove equivalences of sets. The student will recognize different types of relations and in particular, functions, and is able to demonstrate and prove properties such as injectivity and surjectivity, and find an inverse function if one exists. The student will know the meaning of logical connectives, and is able to prove equivalence of logical expressions. The student is able to carry out basic logical deduction using known theories. The student is able to formulate first-order expressions with quantifiers and understands the meaning of quantifiers, for example, the meaning of their ordering. The student is able to formulate sets, relations and functions by means of recursive definitions, and prove properties of sets, relantions and function by means of induction.

#### Sisältö

 Sisältö Ydinsisältö Täydentävä tietämys Erityistietämys 1. Proof methods, set theory, some data structures. Cardinality of finite sets 2. Relations and functions; properties thereof. Equivalence relation, preorder relation. Injective, surjective and bijective functions. Closure, cardinality (countable/uncountable). Rates of growth of functions and time complexity functions 3. Propositional and predicate logic. Logical deduction Normal forms of formulas Proving equivalence of propositional formulas 4. Induction and recursion. Recursive definitions. Proofs by induction. Lists 5. Boolean algebras

#### Ohjeita opiskelijalle osaamisen tasojen saavuttamiseksi

Exercises and exam needed. Hard working and succesful exercises can raise the grade.

#### Arvosteluasteikko:

Numerical evaluation scale (0-5)

#### Esitietovaatimukset

 Opintojakso P/S Selite MAT-01100 Insinöörimatematiikka X 1 Advisable 1 MAT-01110 Insinöörimatematiikka A 1 Advisable 1 MAT-01130 Insinöörimatematiikka C 1 Advisable 1 MAT-01160 Matematiikka 1 Advisable 1

1 . Suositeltavana esitietona Insinöörimatematiikka 1 (A/B/C/X) tai Matematiikka 1.

#### Vastaavuudet

 Opintojakso Vastaa opintojaksoa Selite MAT-02657 Mathematics for Algorithms, 5 cr MAT-02656 Mathematics for Algorithms, 4 cr

 Päivittäjä: Kunnari Jaana, 05.03.2019