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 set^{1}:
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 | — |
^{1}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
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 | — |