# 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

Code | Subject | Credits | Winter | Summer | |

NMMB409 | Convex optimization | 9 | 4/2 C+Ex | — | |

NMMB411 | Algorithms on Lattices | 5 | 2/1 C+Ex | — | |

NMMB413 | Algorithms on Polynomials | 4 | 2/1 C+Ex | — | |

NMMB415 | Automata and Computational Complexity | 6 | 3/1 C+Ex | — | |

NSZZ023 | Diploma Thesis I | 6 | — | 0/4 C | |

NSZZ024 | Diploma Thesis II | 9 | 0/6 C | — | |

NSZZ025 | Diploma Thesis III | 15 | — | 0/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.

Code | Subject | Credits | Winter | Summer | |

NDMI018 | Approximation and Online Algorithms | 5 | — | 2/2 C+Ex | |

NDMI025 | Randomized Algorithms | 5 | — | 2/2 C+Ex | |

NMAG331 | Mathematical Logic | 3 | 2/0 Ex | — | |

NMAG401 | Algebraic Geometry | 5 | 2/2 C+Ex | — | |

NMAG403 | Combinatorics | 5 | 2/2 C+Ex | — | |

NMAG430 | Algebraic Number Theory | 6 | — | 3/1 C+Ex | |

NMAG436 | Curves and Function Fields | (2C) | 6 | — | 3/1 C+Ex |

NMAG535 | Computational Logic | (2A) | 5 | 2/2 C+Ex | — |

NMAG563 | Introduction to complexity of CSP | 3 | 2/0 Ex | — | |

NMMB331 | Boolean functions | (2C) | 3 | 2/0 Ex | — |

NMMB333 | Introduction to data analysis | 5 | 2/2 C+Ex | — | |

NMMB402 | Numerical Algorithms | (2A) | 5 | — | 2/1 C+Ex |

NMMB404 | Cryptanalysis | (2C) | 6 | — | 3/1 C+Ex |

NMMB430 | Algorithms on Eliptic curves | (2A,2C) | 4 | — | 2/1 C+Ex |

NMMB432 | Randomness and Calculations | (2C) | 4 | — | 2/1 Ex |

NMMB433 | Geometry for Computer Graphics | (2E) | 3 | — | 2/0 Ex |

NMMB437 | Legal Aspects of Data Protection | (2C) | 3 | 2/0 Ex | — |

NMMB438 | Fundamentals of Continuous Optimization | (2B) | 6 | — | 2/2 C+Ex |

NMMB440 | Geometry of Computer Vision | (2D)^{*} | 6 | — | 2/2 C+Ex |

NMMB442 | Geometric Problems in Robotics | (2D)^{*} | 6 | — | 2/2 C+Ex |

NMMB460 | Cryptanalysis Upon the Level of Instructions | (2C) | 4 | — | 0/4 C |

NMMB464 | Introduction to Computational Topology | (2A,2D,2E) | 4 | — | 2/1 C+Ex |

NMMB498 | MIT Elective 1 | 3 | 2/0 Ex | — | |

NMMB499 | MIT Elective 2 | 3 | — | 2/0 Ex | |

NMMB501 | Network Certification Security | (2C) | 5 | 2/2 C+Ex | — |

NMMB531 | Number Field Sieve | (2A) | 3 | 2/0 Ex | — |

NMMB532 | Standards and Cryptography | (2C) | 3 | — | 2/0 Ex |

NMMB534 | Quantum Information | 6 | — | 3/1 C+Ex | |

NMMB538 | Elliptic Curves and Cryptography | (2C) | 6 | 3/1 C+Ex | — |

NMMO537 | Saddle Point Problems and Their Solution | (2B) | 5 | — | 2/2 C+Ex |

NMNV411 | Algorithms for matrix iterative methods | (2B) | 5 | 2/2 C+Ex | — |

NMNV412 | Analysis of matrix iterative methods — principles and interconnections | (2B) | 6 | — | 4/0 Ex |

NMNV503 | Numerical Optimization Methods 1 | (2B) | 6 | 3/1 C+Ex | — |

NMNV531 | Inverse Problems and Regularization | (2B) | 5 | 2/2 C+Ex | — |

NMNV532 | Parallel Matrix Computations | (2B) | 5 | — | 2/2 C+Ex |

NMNV533 | Sparse Matrices in Numerical Mathematics | (2B) | 5 | 2/2 C+Ex | — |

NOPT016 | Integer Programming | (2B) | 5 | — | 2/2 C+Ex |

NPFL114 | Deep Learning | 7 | — | 3/2 C+Ex | |

NPGR010 | Advanced 3D graphics for film and games | (2E) | 5 | 2/2 C+Ex | — |

NPGR013 | Special Functions and Transformations in Image Processing | (2E) | 3 | — | 2/0 Ex |

NPGR016 | Applied Computational Geometry | (2D,2E) | 5 | — | 2/1 C+Ex |

NPGR029 | Variational methods in image processing | (2E) | 3 | — | 2/0 Ex |

NTIN022 | Probabilistic Techniques | 5 | 2/2 C+Ex | — | |

NTIN104 | Foundations of theoretical cryptography | (2C) | 4 | 2/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.

Code | Subject | Credits | Winter | Summer | |

NMMB331 | Boolean functions | (2C) | 3 | 2/0 Ex | — |

NMMB402 | Numerical Algorithms | (2A) | 5 | — | 2/1 C+Ex |

NMMB404 | Cryptanalysis | (2C) | 6 | — | 3/1 C+Ex |

NMMB432 | Randomness and Calculations | (2C) | 4 | — | 2/1 Ex |

NMMB433 | Geometry for Computer Graphics | (2E) | 3 | — | 2/0 Ex |

NMMB440 | Geometry of Computer Vision | (2D) | 6 | — | 2/2 C+Ex |

NMMB442 | Geometric Problems in Robotics | (2D) | 6 | — | 2/2 C+Ex |

NMNV411 | Algorithms for matrix iterative methods | (2B) | 5 | 2/2 C+Ex | — |

NMNV503 | Numerical Optimization Methods 1 | (2B) | 6 | 3/1 C+Ex | — |

NMNV533 | Sparse Matrices in Numerical Mathematics | (2B) | 5 | 2/2 C+Ex | — |

NPGR013 | Special Functions and Transformations in Image Processing | (2E) | 3 | — | 2/0 Ex |

NPGR029 | Variational methods in image processing | (2E) | 3 | — | 2/0 Ex |

*Set 3*

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

Code | Subject | Credits | Winter | Summer | |

NMMB361 | Contemporary Issues in Cryptography | 2 | — | 0/2 C | |

NMMB451 | Aplications of Mathematics in Computer Science | 3 | — | 0/2 C | |

NMMB452 | Seminar on Mathematics Inspired by Cryptography | 3 | 0/2 C | 0/2 C | |

NMMB453 | Students' Seminar on Logic | 2 | 0/2 C | 0/2 C | |

NMMB471 | MIT Elective Seminar | 2 | — | 0/2 C | |

NMMB551 | Seminar on Combinatorial, Algorithmic and Finitary Algebra | 2 | 0/2 C | 0/2 C | |

NMNV451 | Seminar in Numerical Mathematics | 2 | 0/2 C | 0/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*

Code | Subject | Credits | Winter | Summer | |

NMMB409 | Convex optimization | 9 | 4/2 C+Ex | — | |

NMMB411 | Algorithms on Lattices | 5 | 2/1 C+Ex | — | |

NMMB413 | Algorithms on Polynomials | 4 | 2/1 C+Ex | — | |

NMMB415 | Automata and Computational Complexity | 6 | 3/1 C+Ex | — | |

NSZZ023 | Diploma Thesis I | 6 | — | 0/4 C | |

Optional and Elective Courses | 27 |

*2nd year*

Code | Subject | Credits | Winter | Summer | |

NSZZ024 | Diploma Thesis II | 9 | 0/6 C | — | |

NSZZ025 | Diploma Thesis III | 15 | — | 0/10 C | |

Optional and Elective Courses | 36 |