FI:MB204 Discrete mathematics B - Course Information
MB204 Discrete mathematics BFaculty of Informatics
- Extent and Intensity
- 4/2. 6 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
- Mgr. Michal Bulant, Ph.D. (lecturer)
Mgr. Martin Panák, Ph.D. (lecturer)
prof. RNDr. Jan Slovák, DrSc. (lecturer)
Mgr. Aleš Návrat, Dr. rer. nat. (seminar tutor)
Mgr. Jaroslav Šeděnka, Ph.D. (seminar tutor)
RNDr. Jan Vondra, Ph.D. (seminar tutor)
- Guaranteed by
- prof. RNDr. Jan Slovák, DrSc.
Faculty of Informatics
Supplier department: Faculty of Science
- Mon 12:00–13:50 G101, Tue 8:00–9:50 G126, Wed 10:00–11:50 G101
- Timetable of Seminar Groups:
- High school mathematics. Elementary knowledge of algebraic and combinatorial tasks (in the extent of MB101 or MB102).
- 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 16 fields of study the course is directly associated with, display
- Course objectives
- The fourth part of the block of four courses in Mathematics in its extended version. In the entire course, the fundamentals of general algebra, linear algebra and mathematical analysis, including their applications in probability, statistics are presented. This semester introduces elemetns of number theory, algebra and some combinatorial methods, including numerical and applied aspects.
- 1. Computer algebra introduction (3 týdny) – groups, permutations, symetries, modular groups, homomorfisms and factorization, group actions (Burnside lemma); rings and fields (polynomials and their roots, divisibility in integers and in polynomial rings, ideals; finite fields and their basic properties (including applications in computer science; polynomials of more variables (Gröbner basis).
- 2. Number theory (4 weeks) – 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; prime numbers - testing up to AKS, divisors, eliptic curves (introduction); Legendre symbol and the quadratic reciprocity law.
- 3. Number theory applications (1 week) – short introduction to asymetric cryptography (RSA, DH, ElGamal, DSA, ECC); basic coding theory (linear and polynomial codes); aplication of fast Fourier transform for quick computations (e.g. Schönhage-Strassen)
- 4. Combinatorics (4 weeks) – reminder of basics of combinatorics; generalized binomial theorem; combinatorial identities; Catalan numbers; formál power seriew; (ordinary) generating functions; exponential generating functions; probabilistic generating functions; solving combinatorial problems with the help of generating functions; solving basic reccurences (Fibonacci); complexity of reccurent algorithm; generating functions in computer science (graph applications, complexity, hashing analysis)
- recommended literature
- J. Slovák, M. Panák a kolektiv, Matematika drsně a svižně, učebnice v přípravě
- not specified
- RILEY, K.F., M.P. HOBSON and S.J. BENCE. Mathematical Methods for Physics and Engineering. second edition. Cambridge: Cambridge University Press, 2004. 1232 pp. ISBN 0 521 89067 5. info
- Teaching methods
- Lecture combining theory with problem solving. Seminar groups devoted to solving problems.
- Assessment methods
- Four hours of lectures, two hours of tutorial. Final written test followed by oral examination. Results of tutorials/homeworks are partially reflected in the assessment.
- Language of instruction
- Further Comments
- Study Materials
The course is taught annually.
- Listed among pre-requisites of other courses