2 Degree Plans – Discrete Models and Algorithms

Coordinated by: Department of Applied Mathematics
Study branch coordinator: Doc. RNDr. Martin Klazar, Dr.

Specializations:

 Discrete mathematics and algorithms
 Geometry and mathematical structures of computer science
 Optimization

The study branch Discrete Models and Algorithms provides education in the area of discrete (meaning non-continuous) mathematical structures used in Computer Science. It deals also with combinatorial (and other) algorithms and with modeling phenomena and processes by means of such structures and algorithms. In the specialization Optimization it puts emphasis on solid grasp of various kinds of optimization. The study branch enables to its graduates to be in contact with current scientific results and ideally it prepares them for independent research activity.

The graduate knows in depth discrete mathematics and discrete structures used in computer science and can model, using algorithms, various phenomena and processes. According to chosen specialization the graduate has advanced knowledge in one or more of the areas: combinatorics and graph theory, random techniques and methods in discrete mathematics and algorithms, algebraic and topological methods, and finally optimization of various kinds. The graduate can use this knowledge in research when solving difficult theoretical and practical questions in the area of applied mathematics and computer science, in technical and economical practice, and in interdisciplinary research. The graduate can work in research and development in either academia or industry in any position requiring logical reasoning, analytical capabilities, an algorithmic approach, and the exploitation of modern methods of computer science.

2.1 Obligatory courses

Code Subject Credits Winter Summer
NTIN090 Introduction to Complexity and Computability   5 2/1 C+Ex
NTIN066 Data Structures I   5 2/1 C+Ex
NMAI064 Mathematical Structures   6 2/2 C+Ex
NSZZ023 Diploma Thesis I   6 0/4 C 0/4 C
NSZZ024 Diploma Thesis II   9 0/6 C 0/6 C
NSZZ025 Diploma Thesis III   15 0/10 C 0/10 C

2.2 Elective courses - Set 1

The student needs to obtain at least 45 credits for the courses from the following set:

Code Subject Credits Winter Summer
NAIL076 Logic Programming I   3 2/0 Ex
NDMI009 Combinatorial and Computational Geometry I   6 2/2 C+Ex
NDMI010 Graph Algorithms   3 2/0 Ex
NDMI013 Combinatorial and Computational Geometry II   6 2/2 C+Ex
NDMI015 Combinatorial Counting   3 2/0 Ex
NDMI018 Approximation and Online Algorithms   6 2/2 C+Ex
NDMI025 Randomized Algorithms   6 2/2 C+Ex
NDMI028 Linear Algebra Applications in Combinatorics   6 2/2 C+Ex
NDMI036 Combinatorial Structures   3 2/0 Ex
NDMI037 Geometric Representations of Graphs I   3 2/0 Ex
NDMI045 Analytic and Combinatorial Number Theory   3 2/0 Ex
NDMI055 Selected Chapters on Combinatorics I   3 2/0 Ex
NDMI056 Selected Chapters on Combinatorics II   3 2/0 Ex
NDMI059 Graph Minors and Tree Decompositions   3 2/0 Ex
NDMI060 Coloring of Graphs and Other Combinatorial Structures   3 2/0 Ex
NDMI064 Applied Discrete Mathematics   3 2/0 Ex
NDMI065 Matroid Theory   6 2/2 C+Ex
NDMI066 Algebraic Number Theory and Combinatorics   3 2/0 Ex
NDMI067 Flows, Paths and Cuts   3 2/0 Ex
NDMI073 Combinatorics and Graph Theory III   6 2/2 C+Ex
NDMI074 Algorithms and Their Implementation   6 2/2 C+Ex
NDMI088 Graph Algorithms II   3 2/0 Ex
NMAG337 Introduction to Group Theory   5 2/2 C+Ex
NMAI040 Introduction to Number Theory   3 2/0 Ex
NMAI065 Fundamentals of Category Theory for Computer Scientists   3 2/0 Ex
NMAI066 Topological and Algebraic Methods   3 2/0 Ex
NMAI067 Logic in Computer Science   3 2/0 Ex
NMAI071 Math++   6 2/2 C+Ex
NMMA901 Introduction to Complex Analysis (O)   5 2/2 C+Ex
NMMA903 Measure and Integration Theory (O)   8 4/2 C+Ex
NMMA931 Introduction to Functional Analysis (O)   8 4/2 C+Ex
NOPT008 Nonlinear Optimisation Algorithms   6 2/2 C+Ex
NOPT016 Integer Programming   6 2/2 C+Ex
NOPT017 Multiobjective Optimisation   3 2/0 Ex
NOPT018 Fundamentals of Nonlinear Optimization   6 2/2 C+Ex
NOPT034 Mathematical Programming and Polyhedral Combinatorics   5 2/1 C+Ex
NOPT042 Constraint Programming   6 2/2 C+Ex
NOPT051 Interval Methods   6 2/2 C+Ex
NTIN017 Parallel Algorithms   3 2/0 Ex
NTIN022 Probabilistic Techniques   6 2/2 C+Ex
NTIN063 Complexity   5 2/1 C+Ex
NTIN064 Computability   3 2/0 Ex
NTIN067 Data Structures II   3 2/0 Ex
NTIN103 Introduction to Parameterized Algorithms   6 2/2 C+Ex

2.3 Elective courses - Set 2

The student needs to obtain at least 6 credits for the courses from the following set1:

Code Subject Credits Winter Summer
NDMI073 Combinatorics and Graph Theory III   6 2/2 C+Ex
NOPT018 Fundamentals of Nonlinear Optimization   6 2/2 C+Ex

1For specializations Discrete mathematics and algorithms, Geometry and mathematical structures of computer science we recommend the course NDMI073; for the specialization Optimization we recommend the course NOPT018. After completing one course from Set 2, the credits are counted for that set and the minimal credit requirement for Set 2 is satisfied. If the student completes both courses from Set 2, the credits for the second course are counted for Set 1.

2.4 State Final Exam

In addition to the two examination areas that are obligatory for all study branches, the student will select three examination areas from the following lists. At least two examination areas must be selected from a chosen specialization, one area may be selected from another specialization. In total, each student will get five questions.

Specialization: Discrete mathematics and algorithms

Examination areas

1. Combinatorics and graph theory
2. Probabilistic methods and combinatorial enumeration
3. Combinatorial optimization

Knowledge requirements

1. Combinatorics and graph theory
Graph colorings (and variants - choosability), graph minors, tree width and its relation to complexity, geometric representations of graphs (characterization theorems, recognizing algorithms), algebraic properties of graphs, matching theory, Ramsey theory and Szemeredi's regularity lemma, set systems (Steiner triple systems, finite geometries).

Recommended courses

Code Subject Credits Winter Summer
NDMI037 Geometric Representations of Graphs I   3 2/0 Ex
NDMI059 Graph Minors and Tree Decompositions   3 2/0 Ex
NDMI060 Coloring of Graphs and Other Combinatorial Structures   3 2/0 Ex
NDMI073 Combinatorics and Graph Theory III   6 2/2 C+Ex

2. Probabilistic methods and combinatorial enumeration
Combinatorial counting, generating functions, recurrences, basic probabilistic models, linearity of expectation, variance and its uses, Markov's inequality and its applications to particular examples, Chernov's inequality, Lovasz local lemma, asymptotic estimates of functions, probabilistic constructions and algorithms.

Recommended courses

Code Subject Credits Winter Summer
NDMI015 Combinatorial Counting   3 2/0 Ex
NDMI025 Randomized Algorithms   6 2/2 C+Ex
NTIN022 Probabilistic Techniques   6 2/2 C+Ex

3. Combinatorial optimization
Graph algorithms, theory of polyhedra, travelling salesman problem, classes of special matrices, integrality, matchings and flows in networks, matroid theory, ellipsoid method.

Recommended courses

Code Subject Credits Winter Summer
NTIN090 Introduction to Complexity and Computability   5 2/1 C+Ex
NDMI010 Graph Algorithms   3 2/0 Ex
NDMI065 Matroid Theory   6 2/2 C+Ex
NOPT034 Mathematical Programming and Polyhedral Combinatorics   5 2/1 C+Ex
NDMI088 Graph Algorithms II   3 2/0 Ex

Specialization: Geometry and mathematical structures of computer science

Examination areas

1. Combinatorial and computational geometry
2. Algebraic and topological structures in Computer Science
3. Category theory in Computer Science
4. Number theory in Computer Science

Knowledge requirements

1. Combinatorial and computational geometry
Geometric problems in finite-dimensional spaces, combinatorial properties of geometric configurations, algorithmic applications, design of geometric algorithms, geometric representations of graphs.

Recommended courses

Code Subject Credits Winter Summer
NDMI009 Combinatorial and Computational Geometry I   6 2/2 C+Ex
NDMI013 Combinatorial and Computational Geometry II   6 2/2 C+Ex

2. Algebraic and topological structures in Computer Science
Posets (partially ordered sets), suprema and infima, semilattices and lattices. Fix point theorems. Special ordered structures in Computer Science (DCPO, domains). Fundamentals of general topology, topological constructions. Topological approaches in Computer Science (Scott's topology, continuous lattices). Categories of topological spaces and certain kinds of posets used in Computer Science.

Recommended courses

Code Subject Credits Winter Summer
NMAI064 Mathematical Structures   6 2/2 C+Ex
NMAI066 Topological and Algebraic Methods   3 2/0 Ex

3. Category theory in Computer Science
Categories, functors, transformations, examples. Limits and colimits, special constructions. Adjunction, relation to categorical constructions. Reflections and coreflections. Examples of adjoint situations. Cartesian closed categories. Categories and structures, especially structures used in Computer Science. Monadic algebras.

Recommended courses

Code Subject Credits Winter Summer
NMAI065 Fundamentals of Category Theory for Computer Scientists   3 2/0 Ex

4. Number theory in Computer Science
Diophantine approximation (Dirichlet's theorem, Farey fractions transcendental numbers). Diophantine equations (Pell's equation, Thue equation, four squares theorem, Hilbert's tenth problem). Prime numbers (bounds on the prime number function, Dirichlet's theorem). Geometry of numbers (lattices, Minkowski's theorem). Congruences (quadratic residues). Integer partitions (identities, e.g., the pentagonal identity).

Recommended courses

Code Subject Credits Winter Summer
NMAI040 Introduction to Number Theory   3 2/0 Ex

Specialization: Optimisation

Examination areas

1. Nonlinear programming
2. Discrete optimisation processes
3. Multiobjective and integer programming
4. Parametric programming and interval methods

Knowledge requirements

1. Nonlinear programming
Properties of convex sets and convex functions. Generalizations of convex functions. Necessary and sufficient optimality conditions for free and constrained extrema in problems of nonlinear programming. Quadratic programming. Semidefinite programming. Duality in nonlinear programming. Methods for solving problems on free and constrained extrema, including penalization and barrier methods. One-dimensional optimization.

Recommended courses

Code Subject Credits Winter Summer
NOPT008 Nonlinear Optimisation Algorithms   6 2/2 C+Ex
NOPT018 Fundamentals of Nonlinear Optimization   6 2/2 C+Ex

2. Discrete optimisation processes
Algorithmic game theory, election mechanisms, electronic auctions, application of submodular functions in economy. Optimization based on enumeration, generating functions of edge cuts and perfect matchings, enumerative dualities, the maximum cut problem for graphs on surfaces.

Recommended courses

Code Subject Credits Winter Summer
NDMI064 Applied Discrete Mathematics   3 2/0 Ex
NOPT018 Fundamentals of Nonlinear Optimization   6 2/2 C+Ex

3. Multiobjective and integer programming
Various approaches to solving problems with several criteria. Functional associated to a problem of vector programming. Pareto optimal solution. Problems of linear and nonlinear vector optimization. Methods for obtaining Pareto optimal solutions. Problems of linear programming with integrality conditions or with binary variables. Nonlinear optimization problems with integrality conditions.

Recommended courses

Code Subject Credits Winter Summer
NOPT016 Integer Programming   6 2/2 C+Ex
NOPT017 Multiobjective Optimisation   3 2/0 Ex
NOPT018 Fundamentals of Nonlinear Optimization   6 2/2 C+Ex

4. Parametric programming and interval methods
Domains of stability of solutions. Domains of solvability. Solvability function for one-parametric and multi-parametric programming. Interval linear algebra (systems of linear equations, regularity, eigenvalues). Linear programming with imprecise data. Deterministic global optimization, lower and upper bounds on objective function and optimum value.

Recommended courses

Code Subject Credits Winter Summer
NOPT017 Multiobjective Optimisation   3 2/0 Ex
NOPT018 Fundamentals of Nonlinear Optimization   6 2/2 C+Ex
NOPT051 Interval Methods   6 2/2 C+Ex