# FI:MB154 Discrete mathematics - Course Information

## MB154 Discrete mathematics

**Faculty of Informatics**

Autumn 2020

**Extent and Intensity**- 2/2/0. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
**Teacher(s)**- prof. RNDr. Jan Slovák, DrSc. (lecturer)

doc. Lukáš Vokřínek, PhD. (lecturer)

Mgr. Martin Dzúrik (seminar tutor)

Mgr. Pavel Francírek, Ph.D. (seminar tutor)

Mgr. Jan Jurka (seminar tutor)

Mgr. Martin Panák, Ph.D. (seminar tutor)

Mgr. Miloslav Štěpán (seminar tutor)

Mgr. Dominik Trnka (seminar tutor)

Mgr. Michal Bulant, Ph.D. (assistant) **Guaranteed by**- prof. RNDr. Jan Slovák, DrSc.

Department of Computer Science – Faculty of Informatics

Supplier department: Faculty of Science **Timetable**- Mon 14:00–15:50 D3
- Timetable of Seminar Groups:

*J. Jurka*

MB154/02: Wed 12:00–13:50 B204,*M. Štěpán*

MB154/03: Thu 8:00–9:50 A320,*D. Trnka*

MB154/04: Thu 10:00–11:50 A320,*D. Trnka*

MB154/05: Thu 12:00–13:50 A320,*M. Dzúrik*

MB154/06: Thu 14:00–15:50 A320,*M. Dzúrik*

MB154/07: Wed 14:00–15:50 B204,*P. Francírek*

MB154/08: Wed 16:00–17:50 B204,*P. Francírek* **Prerequisites**- !
**MB104**Discrete mathematics && !**MB204**Discrete mathematics B && (**MB101**Mathematics I ||**MB201**Linear models B ||**MB151**Linear models ||**MB102**Calculus ||**MB202**Calculus B ||**MB152**Calculus )

High school mathematics. Elementary knowledge of algebraic and combinatorial tasks. **Course Enrolment Limitations**- The course is also offered to the students of the fields other than those the course is directly associated with.
**fields of study / plans the course is directly associated with**- there are 53 fields of study the course is directly associated with, display
**Course objectives**- Tho goal of this course is to introduce the basics of theory of numbers with its applications to cryptography, and also the basics of coding and more advanced combinatorial methods.
**Learning outcomes**- At the end of this course, students should be able to: understand and use methods of number theory to solve simple tasks; understand approximately how results of number theory are applied in cryptography: understand basic computational context; model and solve simple combinatorial problems.
**Syllabus**- Number theory:
- divisiblity (gcd, extended Euclid algorithm, Bezout); numerics of big numbers (gcd, modular exponential); prime numbers (properties, basic theorems of arithmetics, factorization, prime number testing (Rabin-Miller, Mersenneho prime numbers); congruences (basic properties, small Fermat theorem; Euler theorem; linear congruences; binomial congruences a primitiv roots; discrete logarithm;
- Number theory applications:
- short introduction to asymetric cryptography (RSA, DH, ElGamal, DSA, ECC); basic coding theory (linear and polynomial codes);
- Combinatorics:
- reminder of basics of combinatorics; generalized binomial theorem; combinatorial identities; Catalan numbers; formal power series; (ordinary) generating functions; exponential generating functions; probabilistic generating functions; solving combinatorial problems with the help of generating functions; solving basic reccurences (Fibonacci).

**Literature**- SLOVÁK, Jan, Martin PANÁK and Michal BULANT.
*Matematika drsně a svižně (Brisk Guide to Mathematics)*. 1st ed. Brno: Masarykova univerzita, 2013, 773 pp. ISBN 978-80-210-6307-5. Available from: https://dx.doi.org/10.5817/CZ.MUNI.O210-6308-2013.*Základní učebnice matematiky pro vysokoškolské studium*info

- SLOVÁK, Jan, Martin PANÁK and Michal BULANT.
**Teaching methods**- There are standard two-hour lectures and standard tutorial (in case of need replaced by ther distance form complemented by homework solving).
**Assessment methods**- During the semester, students will sit a mid-term exam, max 20 points. In the seminar groups there will be tests run, awarded in total max 20 points (13 tests per 2 points, the worst 3 results are erased; in case of the distance form, the tests will be replaced by homeworks). Out of these max 40 points, it is necessary to get at least 15 points in order to be allowed to sit the final exam in the exam period, consisting of a theoretical and a practical part, max 60 points. Altogether, it is possible to get max 100 points. For successful examination (the grade at least E) the student needs to obtain at least 50 points.
**Language of instruction**- Czech
**Further Comments**- Study Materials

The course is taught annually. **Listed among pre-requisites of other courses****MB141**Linear algebra and discrete mathematics

!NOW(MB151) && ( !MB151 || !MB154 )

- Enrolment Statistics (Autumn 2020, recent)
- Permalink: https://is.muni.cz/course/fi/autumn2020/MB154