FI:MB154 Discrete mathematics - Course Information
MB154 Discrete mathematics
Faculty of InformaticsAutumn 2024
- Extent and Intensity
- 2/2/0. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
In-person direct teaching - Teacher(s)
- doc. Mgr. Josef Šilhan, Ph.D. (lecturer)
doc. Lukáš Vokřínek, PhD. (lecturer)
Mgr. Pavel Francírek, Ph.D. (seminar tutor)
Mgr. Jan Procházka (seminar tutor)
Bc. et Bc. Martin Zahradníček, MSc (seminar tutor) - Guaranteed by
- doc. Lukáš Vokřínek, PhD.
Department of Mathematics and Statistics – Departments – Faculty of Science
Supplier department: Department of Mathematics and Statistics – Departments – Faculty of Science - Timetable
- Mon 23. 9. to Mon 16. 12. Mon 10:00–11:50 D2
- Timetable of Seminar Groups:
MB154/02: Thu 26. 9. to Thu 19. 12. Thu 16:00–17:50 A320, J. Procházka
MB154/03: Thu 26. 9. to Thu 19. 12. Thu 18:00–19:50 A320, J. Procházka
MB154/04: Fri 27. 9. to Fri 20. 12. Fri 8:00–9:50 A320, M. Zahradníček
MB154/05: Fri 27. 9. to Fri 20. 12. Fri 10:00–11:50 A320, M. Zahradníček - Prerequisites
- MB151 Linear models || MB152 Calculus || PřF:M1110 Linear Algebra I || PřF:M1100 Mathematical Analysis I
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
- Image Processing and Analysis (programme FI, N-VIZ)
- Bioinformatics and systems biology (programme FI, N-UIZD)
- Computer Games Development (programme FI, N-VIZ_A)
- Computer Graphics and Visualisation (programme FI, N-VIZ_A)
- Computer Networks and Communications (programme FI, N-PSKB_A)
- Cybersecurity Management (programme FI, N-RSSS_A)
- Formal analysis of computer systems (programme FI, N-TEI)
- Graphic design (programme FI, N-VIZ)
- Graphic Design (programme FI, N-VIZ_A)
- Hardware Systems (programme FI, N-PSKB_A)
- Hardware systems (programme FI, N-PSKB)
- Image Processing and Analysis (programme FI, N-VIZ_A)
- Information security (programme FI, N-PSKB)
- Informatics (programme FI, B-INF) (2)
- Informatics in education (programme FI, B-IVV) (2)
- Information Security (programme FI, N-PSKB_A)
- Quantum and Other Nonclassical Computational Models (programme FI, N-TEI)
- Computer graphics and visualisation (programme FI, N-VIZ)
- Computer Networks and Communications (programme FI, N-PSKB)
- Principles of programming languages (programme FI, N-TEI)
- Programming and development (programme FI, B-PVA)
- Cybersecurity management (programme FI, N-RSSS)
- Services development management (programme FI, N-RSSS)
- Software Systems Development Management (programme FI, N-RSSS)
- Services Development Management (programme FI, N-RSSS_A)
- Software Systems Development Management (programme FI, N-RSSS_A)
- Software systems (programme FI, N-PSKB)
- Machine learning and artificial intelligence (programme FI, N-UIZD)
- Teacher of Informatics and IT administrator (programme FI, N-UCI)
- Informatics for secondary school teachers (programme FI, N-UCI) (2)
- Computer Games Development (programme FI, N-VIZ)
- Processing and analysis of large-scale data (programme FI, N-UIZD)
- Natural language processing (programme FI, N-UIZD)
- 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
- 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 10 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 + 20 = 40 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 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 (probably available only in Czech)
- Study Materials
The course is taught annually. - Listed among pre-requisites of other courses
- MB141 Linear algebra and discrete mathematics
!NOW(MB151) && ( !MB151 || !MB154 )
- MB141 Linear algebra and discrete mathematics
- Enrolment Statistics (recent)
- Permalink: https://is.muni.cz/course/fi/autumn2024/MB154