Mathematics for Information Technologies

Coordinated by: Department of Algebra
Study branch coordinator: doc. Mgr. Pavel Příhoda, Ph.D.

The study programme is oriented to extension and algorithmic treatment of theoretical knowledge of mathematical branches applied in information technologies. Within the study programme one can focus to cryptology, computer vision and robotics, or image processing and computer graphics. A graduate has advanced analytical ability. He is able to identify the mathematical basis of problems from IT praxis, apply a complex mathematical theory and further professional knowledge to solve these problems. Graduates realize themselves in companies concentrating to the development of ambitious and specialized applications.

Assumed knowledge

It is assumed that an incoming student of this branch has sufficient knowledge of the following topics and fields:

–Linear algebra, real analysis, and probability theory.

–Foundations of general algebra including divisibility in integral domains, properties of polynomial rings, finite fields, foundations of group theory and Galois theory, elementary number theory.

–Computational aspects of aforementioned topics: Basic matrix algorithms, discrete Fourier transform and modular arithmetic, polynomial arithmetic. Basic idea of applications (cryptography, error-correcting codes, geometric modelling). Foundations of algorithmization and programming in Python.

Should an incoming student not meet these entry requirements, the coordinator of the study programme may assign a method of acquiring the necessary knowledge and abilities, which may for example mean taking selected bachelor's courses, taking a reading course with an instructor, or following tutored independent study.

3.1 Obligatory Courses

3.2 Elective Courses

Set 1

It is required to earn at least 46 credits from this group. The topics of the state exam to which the course relates is noted in brackets. The other courses are general.

^* The course is taught once in two years only.

Set 2

The topics of the state exam are covered by these courses. It is required to earn at least 17 credits in 46 credits from the following short list.

Set 3

This group consists of scientific or working seminars. It is required to earn at least 4 credits from this group.

3.3 State Final Exam

Requirements for taking the final exam

– Earning at least 120 credits during the course of the study.

– Completion of all obligatory courses prescribed by the study plan.

– Earning at least 46 credits by completion of elective courses from set 1. At least 17 credits must be from the short list of elective courses in set 2.

– Earning at least 4 credits by completion of elective courses from set 3.

– Submission of a completed Master's Thesis by the submission deadline.

Oral part of the state final exam

1. Mathematics for information technologies
Computational models, algorithmic decidability, basic complexity classes, regular languages. Basic methods of convex optimization. Groebner bases and Buchberger's algorithm. Lattices and the LLL algorithm.

2A. Algebraic and numerical algorithms
Factorization of polynomials: Berlekamp's algorithm, Hensel's lifting, Berlekamp-Hensel algorithm. Applications of Groebner bases in algebraic geometry. Algorithms for factorization of integers: Pollard rho, Pollard (p-1), CFRAC, ECM, and quadratic sieve. Connection between factorization of integers and discrete logarithm problem.

2B. Algorithms for linear algebra and optimization
Sparse Cholesky and LU decomposition, sparse QR decomposition. Krylov space iterative methods for solving systems of linear algebraic equations and linear approximation problems including construction of algebraic preconditionings. Methods for solving non-linear algebraic equations and their systems, functional minimization without constraints, local and global convergence of methods.

2C. Cryptology
Foundations of Boolean functions (bent functions, APN and AB functions, equivalences, S-boxes, Walsh transform and LAT, difference uniformity and DDT). Sequences generated by shift registers. Basic cryptanalytic attacks on block ciphers (differential and linear cryptanalysis, higher level attacks, meet-in-the middle) and stream ciphers (correlations, algebraic attacks), side channel attacks. Applications of lattices: NTRU, applications of LLL (for example attack on RSA with small public exponent). Probabilistic complexity classes, pseudorandom generators.

2D. Computer vision and robotics.
Mathematical model of perspective camera. Calculation of movement of calibrated camera from the pictures of unknown scene. 3D reconstruction from two images of unknown scene. Geometry of three calibrated cameras. Denavit-Hartenberg description of kinematics of manipulator. Inverse kinematic problem of 6-arm serial manipulator - formulation and solution. Calibration of parameters of manipulator - formulation and solution.

2E. Image processing and computer graphics.
Modelling of inverse problems, regularization methods, digitization of image, deblurring, edge detection, image registration, compression, image synthesis, compressed sensing, analytical, kinematic and differential geometry.

3.4 Recommended Course of Study

1st year

2nd year