Degree Plans

The obligatory and elective courses, as specified below, are the same for the three specializations. The specializations differ in one area of the state final exam and the students are recommended to adjust their choice of elective and optional courses accordingly.

Obligatory courses

¹ The course NOPT048 went under name "Optimization methods" until the academic year 2017/18.

² In the course NPRG031 the exam can be taken before obtaining the course credit.

Elective courses

Set 1

The student needs to obtain at least 6 credits for courses from this set.

Set 2

The student needs to obtain at least 34 credits for courses from this set.

^** The course can be taken in the summer as well as in the winter semester.

Recommended course of study

The recommended course of study contains all obligatory courses, some elective courses in required extend and some optional courses. The student needs to choose other courses him/herself. The obligatory courses are printed in boldface, the elective courses are printed upright and the optional courses in italics.

First year

¹The course NMAI069 Mathematical skills is highly recommended to students who want to master basic mathematical skills used in mathematical courses. The use of logical thinking is heavily emphasized.

^* In the course NPRG031 the exam can be taken before obtaining the course credit.

Second year

Third year

Recommended choice of the elective courses for each study plan

Algorithms and optimization

Discrete models and structures

Mathematical linguistics

State Final Exam

The state final exam has three parts in the bachelor programme:

–oral examination in Mathematics

–oral examination in Computer Science

–defense of the bachelor thesis

Necessary conditions for taking the state final exam

–obtaining of 180 credits at least

–passing all obligatory courses of a given branch and specialization

–obtaining a given number of credits for the elective courses

–submitting the completed bachelor thesis by the specified deadline.

Knowledge requirements for the part Mathematics of the State Final Exam

1. Numbers 
Properties of natural, whole, rational, real and complex numbers. Sequences and series of numbers. Cauchy sequences.

2. Fundamentals of differential calculus 
Real functions of one variable. Continuity, limit of a function (ordinary, infinite). Some specific functions (polynomials, rational functions, trigonometric and inverse trigonometric functions, logarithms and exponential functions). Derivation: the definition, basic rules, theorems about the mean value, higher order derivatives. Applications (examination of properties of functions, Taylor polynomial).

3. Basics of the theory of multivariable functions 
Partial derivatives and total differential, theorems about extreme values of multivariable functions, implicit function theorem.

4. Integral 
Primitive functions, methods of calculation. Definite (Riemann) integral, applications of the definite integral. Multivariate integrals and Fubini's theorem.

5. Metric spaces 
Definition of a metric space, examples. Continuity, open and closed sets. Compactness.

6. Elementary algebraic structures 
Groups, rings, fields - definitions, examples. Fermat's Little Theorem. Divisibility and irreducible factorization of polynomials. Factorization for polynomials with real, rational and complex coefficients. Multiplicity of roots and their relationship with derivations of the polynomial.

7. Vector spaces 
Basic properties of vector spaces, subspaces, generation, linear dependence and independence. Steinitz (exchange) theorem. Finitely generated vector spaces, basis. Linear mapping.

8. Scalar product 
Properties in vector spaces over the real and complex fields. Norm. Cauchy-Schwarz inequality. Ortogonality. Orthogonal complement and its properties.

9. Systems of linear equations 
Affine subspace in vector spaces and geometric interpretation. Solution of a system of linear equations as an affine subspace. Frobenius theorem. Solving system of linear equations by elimination. Solution of a system of linear equations and its orthogonal complement.

10. Matrices 
Matrices, their rank. Operations with matrices and their properties. Inverse matrix. Nonsingular matrices, various characterizations. Matrices and linear mappings, changes of coordinate systems.

11. Determinants 
Definitions and basic properties of determinant. Calculation of determinant. Geometric interpretation of a determinant. Minors and inverse matrices. Cramer's rule.

12. Eigenvalues and eigenvectors 
Eigenvalues and eigenvectors of linear mapping and square matrix. Calculation, basic properties. Transformation of a matrix to a diagonal form, in the case of different eigenvalues. Jordan normal form of a matrix, in the general case (basic information).

13. Discrete Mathematics 
Sets, ordered sets, mappings, relations, equivalences. Combinatorial counting. The principle of inclusion and exclusion. Generating functions.

14. Graph Theory 
Basic concepts of graph theory, graph representation. Trees and their basic properties, spanning tree. Eulerian graphs. Planar graphs, graph colorings. Menger's theorem, duality of flows and cuts. Matching, matching in bipartite graphs (system of different representatives).

15. Probability and Statistics 
Random events, conditional probability, independence of random events. Random variables, the mean, the distribution of random variables, normal and binomial distribution. Linear combinations of random variables. Point estimates, confidence intervals, hypothesis testing, t-test, chi-square test, linear regression.

16. Logic 
Language, formula, semantics, tautology. Decidability, satisfiability, truth, provability. Compactness theorems, completeness of propositional and predicate logic. Normal forms of propositional formulas, prenex normal forms in predicate logic.

17. Algebra 
Subgroups, normal subgroups, quotient groups, ideal. Homomorphisms of groups and other structures. Quotient fields.

Knowledge requirements for the part Computer Science of the State Final Exam

1. Automata and languages 
Chomsky hierarchy, classes of automata and grammars, determinism and non-determinism. Closure properties of classes of languages.

2. Algorithms and Data Structures 
Time complexity of algorithms, complexity in the worst and average case. Complexity classes P and NP, reducibility, NP-completeness. ``Divide-and-conquer" technique - applications and complexity analysis, dynamic programming. Binary search trees, balancing, heaps. Hashing. Sequential sorting, comparison based algorithms, bucket sorting, sorting networks. Graph algorithms - depth-first search and breadth-first search, connected components, strongly connected components in oriented graphs, topological sorting, shortest path, spanning tree, network flows. Transitive closure. Text search algorithms. Algebraic algorithms - DFT, Euclid's algorithm. RSA. Approximation algorithms.

3. Databases 
Architectures of database systems. Conceptual, logical and physical database design. Algorithms for design of relational schemas, normal forms, referential integrity. Transactional processing, properties of transactions, locking protocols, deadlocks. ER-diagrams, methods for IS design. Overview of SQL.

4. Programming languages 
Implementation principles of object-oriented languages, runtime support. Separate compilation, linking, build management. Concepts and principles of object-oriented design. Generic programming, templates and generics, compile time polymorphism. Non-procedural programming.

5. Computer Architecture and Operating Systems 
Computer architecture. Processors, multiprocessors. Buses, protocols. Input and output devices. OS architecture. Relationship between OS and HW architecture, interruption handling. Processes, threads, scheduling. Synchronization primitives, mutual exclusion. Deadlock, deadlock recovery. Memory management, allocation algorithms. Principles of memory virtualization, paging, page replacement algorithms, page faults, page tables. File systems, directory structure.

6. Networking Fundamentals 
Taxonomy of computer networks. ISO/OSI reference architecture. Overview of the TCP/IP protocol model. Routing. Addresses, ports, sockets. Client-server architectures. Fundamentals of HTTP, FTP and SMTP protocols.

7. Optimization Methods 
Polyhedron, Minkowski-Weyl theorem. Basics of linear programming, duality theorems, algorithms for LP. Edmonds' algorithm. Integer programming.

8. For specialization Algorithms and optimization 
Approximation algorithms for combinatorial problems (satisfiability, independent set, set cover, scheduling). Applications of linear programming in approximation algorithms. The use of probability in the design of algorithms. Voronoi diagrams, arrangements of (complex) hyperplanes, incidence of points and lines, elementary computational geometry algorithms. Error-correcting codes. The probabilistic method - examples of application.

8. For specialization Discrete models and structures 
Sets and mappings. Subvalence and equivalence of sets. Good arrangement. Axiom of choice (Zermel's theorem, Zorn's lemma). Graph coloring (Brooks' and Vizing's theorem). Tutte's theorem. Extremal combinatorics (Ramsey's theorem, Erdös-Ko-Rado theorem). Error-correcting codes. The probabilistic method - application examples.

8. For specialization Computational linguistics 
Formal languages and automata, basic formalisms for description of a natural language; morphological and syntactic analysis of a natural language; theory of information, language modeling.