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

CodeSubjectCreditsWinterSummer
NMMB409Convex optimization 94/2 C+Ex
NMMB411Algorithms on Lattices 52/1 C+Ex
NMMB413Algorithms on Polynomials 42/1 C+Ex
NMMB415Automata and Computational Complexity 63/1 C+Ex
NSZZ023Diploma Thesis I 60/4 C
NSZZ024Diploma Thesis II 90/6 C
NSZZ025Diploma Thesis III 150/10 C

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.

CodeSubjectCreditsWinterSummer
NDMI018Approximation and Online Algorithms 52/2 C+Ex
NDMI025Randomized Algorithms 52/2 C+Ex
NMAG331Mathematical Logic 32/0 Ex
NMAG401Algebraic Geometry 52/2 C+Ex
NMAG403Combinatorics 52/2 C+Ex
NMAG430Algebraic Number Theory 63/1 C+Ex
NMAG436Curves and Function Fields(2C)63/1 C+Ex
NMAG535Computational Logic(2A)52/2 C+Ex
NMAG563Introduction to complexity of CSP 32/0 Ex
NMMB331Boolean functions(2C)32/0 Ex
NMMB333Introduction to data analysis 52/2 C+Ex
NMMB402Numerical Algorithms(2A)52/1 C+Ex
NMMB404Cryptanalysis(2C)63/1 C+Ex
NMMB430Algorithms on Eliptic curves(2A,2C)42/1 C+Ex
NMMB432Randomness and Calculations(2C)42/1 Ex
NMMB433Geometry for Computer Graphics(2E)32/0 Ex
NMMB437Legal Aspects of Data Protection(2C)32/0 Ex
NMMB438Fundamentals of Continuous Optimization(2B)62/2 C+Ex
NMMB440Geometry of Computer Vision(2D)*62/2 C+Ex
NMMB442Geometric Problems in Robotics(2D)*62/2 C+Ex
NMMB460Cryptanalysis Upon the Level of Instructions(2C)40/4 C
NMMB464Introduction to Computational Topology(2A,2D,2E)42/1 C+Ex
NMMB498MIT Elective 1 32/0 Ex
NMMB499MIT Elective 2 32/0 Ex
NMMB501Network Certification Security(2C)52/2 C+Ex
NMMB531Number Field Sieve(2A)32/0 Ex
NMMB532Standards and Cryptography(2C)32/0 Ex
NMMB534Quantum Information 63/1 C+Ex
NMMB538Elliptic Curves and Cryptography(2C)63/1 C+Ex
NMMO537Saddle Point Problems and Their Solution(2B)52/2 C+Ex
NMNV411Algorithms for matrix iterative methods(2B)52/2 C+Ex
NMNV412Analysis of matrix iterative methods — principles and interconnections(2B)64/0 Ex
NMNV503Numerical Optimization Methods 1(2B)63/1 C+Ex
NMNV531Inverse Problems and Regularization(2B)52/2 C+Ex
NMNV532Parallel Matrix Computations(2B)52/2 C+Ex
NMNV533Sparse Matrices in Numerical Mathematics(2B)52/2 C+Ex
NOPT016Integer Programming(2B)52/2 C+Ex
NPFL114Deep Learning 73/2 C+Ex
NPGR010Advanced 3D graphics for film and games(2E)52/2 C+Ex
NPGR013Special Functions and Transformations in Image Processing(2E)32/0 Ex
NPGR016Applied Computational Geometry(2D,2E)52/1 C+Ex
NPGR029Variational methods in image processing(2E)32/0 Ex
NTIN022Probabilistic Techniques 52/2 C+Ex
NTIN104Foundations of theoretical cryptography(2C)42/1 C+Ex

* 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.

CodeSubjectCreditsWinterSummer
NMMB331Boolean functions(2C)32/0 Ex
NMMB402Numerical Algorithms(2A)52/1 C+Ex
NMMB404Cryptanalysis(2C)63/1 C+Ex
NMMB432Randomness and Calculations(2C)42/1 Ex
NMMB433Geometry for Computer Graphics(2E)32/0 Ex
NMMB440Geometry of Computer Vision(2D)62/2 C+Ex
NMMB442Geometric Problems in Robotics(2D)62/2 C+Ex
NMNV411Algorithms for matrix iterative methods(2B)52/2 C+Ex
NMNV503Numerical Optimization Methods 1(2B)63/1 C+Ex
NMNV533Sparse Matrices in Numerical Mathematics(2B)52/2 C+Ex
NPGR013Special Functions and Transformations in Image Processing(2E)32/0 Ex
NPGR029Variational methods in image processing(2E)32/0 Ex

Set 3

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

CodeSubjectCreditsWinterSummer
NMMB361Contemporary Issues in Cryptography 20/2 C
NMMB451Aplications of Mathematics in Computer Science 30/2 C
NMMB452Seminar on Mathematics Inspired by Cryptography 30/2 C0/2 C
NMMB453Students' Seminar on Logic 20/2 C0/2 C
NMMB471MIT Elective Seminar 20/2 C
NMMB551Seminar on Combinatorial, Algorithmic and Finitary Algebra 20/2 C0/2 C
NMNV451Seminar in Numerical Mathematics 20/2 C0/2 C

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

The oral part of the final exam consists of two subject areas. One question is asked from common subject area 1. Student chooses two topic from among 2A, 2B, 2C, 2D, 2E. One question is asked from every chosen topic. Expected combinations are 2A+2C, 2B+2D, 2B+2E.

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

CodeSubjectCreditsWinterSummer
NMMB409Convex optimization 94/2 C+Ex
NMMB411Algorithms on Lattices 52/1 C+Ex
NMMB413Algorithms on Polynomials 42/1 C+Ex
NMMB415Automata and Computational Complexity 63/1 C+Ex
NSZZ023Diploma Thesis I 60/4 C
 Optional and Elective Courses 27  

2nd year

CodeSubjectCreditsWinterSummer
NSZZ024Diploma Thesis II 90/6 C
NSZZ025Diploma Thesis III 150/10 C
 Optional and Elective Courses 36