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

2.2 Elective courses - Set 1

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

2.3 Elective courses - Set 2

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

¹For 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

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

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

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

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

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

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

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

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

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

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