MB154 Discrete mathematics

Faculty of Informatics
Autumn 2021
Extent and Intensity
2/2/0. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Taught in person.
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: Department of Mathematics and Statistics – Departments – Faculty of Science
Timetable
Mon 13. 9. to Mon 6. 12. Mon 14:00–15:50 D2
  • Timetable of Seminar Groups:
MB154/01: Mon 13. 9. to Mon 6. 12. Mon 16:00–17:50 A320, L. Vokřínek
MB154/02: Tue 14. 9. to Tue 7. 12. Tue 10:00–11:50 A320, P. Francírek
MB154/03: Tue 14. 9. to Tue 7. 12. Tue 12:00–13:50 A320, P. Francírek
MB154/04: Wed 15. 9. to Wed 8. 12. Wed 16:00–17:50 B204, P. Francírek
MB154/05: Mon 13. 9. to Mon 6. 12. Mon 18:00–19:50 A320, J. Jurka
MB154/06: Tue 14. 9. to Tue 7. 12. Tue 10:00–11:50 B204, M. Dzúrik
MB154/07: Tue 14. 9. to Tue 7. 12. Tue 12:00–13:50 B204, M. Dzúrik
MB154/08: Wed 15. 9. to Wed 8. 12. Wed 8:00–9:50 A320, M. Štěpán
MB154/09: Wed 15. 9. to Wed 8. 12. Wed 14:00–15:50 A320, M. Štěpán
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
Teaching methods
There are standard two-hour lectures and standard tutorials (in case of need replaced by ther distance form).
Assessment methods
The attendance of the seminar groups will be monitored; in order to be allowed for the final exam, the maximum of 3 absences is allowed.


During the semester, students will sit two "mid-term" exams, probably in the time of the lectures, max 20 points (2 exams, 10 points each). Their contents will correspond to what will be covered by then in the seminar groups in the first/second half of the semester.


There will be given 13 homeworks per 2 points, mostly one homework each week, giving the gain of max 26 points from the homeworks.


Before the final exam, it is thus possible to get max 20 + 26 = 46 points, out of which at least 20 points will be needed in order to be allowed for the final exam.


The final exam will take place in the exam period and consists of a computational and a theoretical part (distributed roughly 70% : 30%), max 54 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 (probably available only in Czech)
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
The course is also listed under the following terms Autumn 2020, Autumn 2022, Autumn 2023, Autumn 2024.
  • Enrolment Statistics (Autumn 2021, recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2021/MB154