*Conducted in terms:*2023L, 2024L

*Erasmus code:*11.0

*ISCED code:*0540

*ECTS credits:*7

*Language:*Polish

*Organized by:*Faculty of Mathematics, Informatics, and Mechanics

*Related to study programmes:*

# Discrete mathematics 1000-212bMD

* Mathematical induction and recursion

* Finite sums

* Binomial Coefficients

* Permutations and partitions

* Generating functions with application

* Counting methods:

- enumerators

- inclusion-exclusion principle

* Asymptotics:

- asymptotic notation

- Master theorem

* Elementary number theory:

- divisibility, primes, factorization

- gcd and Euclid's algorithm

* modular arithmetic:

- Fermat's little theorem and Euler's theorem

- Chinese remainder theorem

- solving modular equations

* Elements of the cryptography: Miller-Rabin primality and the RSA system

* Graphs:

- paths, trees and cycles

- Euler and Hamilton cycles

- bipartite graphs, transversals and Hall theorem

- planarity

- coloring

## Type of course

## Requirements

## Course coordinators

## Assessment criteria

Written tests during the course, written exam.

## Bibliography

1. R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka Konkretna, Państwowe Wydawnictwo Naukowe, Warszawa 2013.

2. W.Lipski, Kombinatoryka dla programistów, Wydawnictwa Naukowo-Techniczne 2004.

3. Z.Palka, A.Ruciński, Wykłady z kombinatoryki, Wydawnictwa Naukowo-Techniczne 2009

4. R.J.Wilson, Wprowadzenie do teorii grafów, Państwowe Wydawnictwo Naukowe, Warszawa 2012.

## Additional information

Information on *level* of this course, *year of study* and semester when the course
unit is delivered, types and amount of *class hours* - can be found in course structure
diagrams of apropriate study programmes. This course is related to
the following study programmes:

Additional information (*registration* calendar, class conductors,
*localization and schedules* of classes), might be available in the USOSweb system: