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 program offers wide education in theoretical and mathematical fundaments of computer science. Students obtain knowledge in the area of discrete models and related algorithmic and data techniques, and various mathematical methods for their design. The study familiarizes the student both with the last results on discrete models, algorithms and optimization, and with possibilities and limitations in solving related algorithmic questions. The student acquires thorough mathematical knowledge necessary for analysis and design of discrete models and algorithms.

The graduate is familiar with modelling by means of discrete structures, and also with the practical algorithmic aspects. The graduate understands models of computation and their relations and knows limits of effective computing. They have knowledge on algorithmic techniques and data structures, and has awareness of some optimization techniques and results. The graduate familiarized themselves with mathematical approaches to discrete models and algorithms during their studies. This, besides the ubiquitous combinatorics and discrete mathematics, includes geometric, topological, algebraic, number-theoretic, logical, and, last but not least, probabilistic methods. The graduate can asses applicability of these methods to particular discrete model. She or he can follow last research trends in the area. The graduate can work in analyzing and planning of discrete models, and in their algorithmic implementations and in development corresponding technologies. He or she can work in top companies and institutions investigating and developing new technologies, analyzing data or modelling real processes (finances, logistics, economy etc.). He or she is prepared for further Ph.D. study of computer science in domestic institutions or abroad.

1.1 Obligatory Courses

1.2 Elective Courses - Set 1

The student needs to obtain at least 45 credits for the courses from the following set. The courses NDMI055 and NDMI056 can be attended both by students of Master programs and students of Doctoral programs.

1.3 Elective Courses - Set 2

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

¹For the two specializations Discrete mathematics and algorithms, and 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 among the credits of student's free choice.

1.4 Other Recommended Courses

The list of other recommended courses contains only one course, because of the requirements of the examination area Combinatorial and computational geometry. Additionally, a student can chose other courses from the extensive collection of computer science courses at the Charles University.

1.5 State Final Exam

Each student will get five questions, two from the common background (one from Introduction to complexity and computability and one from Data structures) and three from three examination areas (selected by the student) given in the following lists. At least two of these three examination areas must be selected from student's chosen specialization, one examination area may be selected from another specialization.

Examination areas

1. Introduction to complexity and computability

2. Data structures

Knowledge requirements

1. Introduction to complexity and computability
Models of computation (Turing machines, RAM). Basic complexity classes and their relations. Approximation algorithms and schemas.

Recommended courses

Knowledge requirements

2. Data structures
Search trees ((a,b)-trees, splay trees). Heaps (regular, binomial). Hashing, collisions, universal hashing, hash function.

Recommended courses

Specialization: Discrete mathematics and algorithms

Examination areas

1. Combinatorics and graph theory

2. Probabilistic methods and combinatorial enumeration

3. Polyhedral optimisation

4. Graph algorithms

Knowledge requirements

1. Combinatorics and graph theory
Graph colorings and its variants, e.g. 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, e.g. Steiner triple systems, finite geometries.

Recommended courses

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

Recommended courses

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

Recommended courses

4. Graph algorithms
Advanced algorithms for shortest paths, transitive closure, flows in networks, cuts, matchings and minimal spanning trees, testing of planarity of a graph, drawing a graph in the plane. Graph data structures: union-find, link/cut trees, E-T trees, fully dynamic maintaining of connectivity components, common ancestors in trees (LCA).

Recommended courses

Specialization: Geometry and mathematical structures in Computer Science

Examination areas

1. Combinatorial and computational geometry

2. Structures in Computer Science

3. Topology in Computer Science and Combinatorics

4. Category theory in Computer Science

5. Number theory in Computer Science

Knowledge requirements

1. Combinatorial and computational geometry
Basic theorems on convex sets (Helly's theorem, Radon's theorem, Caratheodory's theorem, hyperplane separation theorem) and their extensions (fractional Helly's theorem, colored Caratheodory's theorem, Tverberg's theorem), Minkowski's theorem on lattices, incidences of points and lines, geometric duality, convex polytopes (basic properties, combinatorial complexity), Voronoi diagrams, convex-independent sets, halving lines, complexity of the lower envelope of segments.

Recommended courses

2. Structures in Computer Science
Relations and relational structures. Ordered sets. Suprema and infima, semilattices and lattices. Fixed-point theorems. Distributive lattices. Boolean and Heyting algebras. Basics of universal algebra. Fundamentals of general topology, topological constructions. Scott's topology, DCPO and domains.

Recommended courses

3. Topology in Computer Science and Combinatorics
Basics of metric and general topology. Topological constructions, special spaces, compact spaces and connected spaces. Simplicial complexes, simplicial maps. Jordan curve theorem (informatively, its place in discrete mathematics). The Borsuk–Ulam theorem and its applications: the sandwich theorem, the necklace theorem, chromatic number of Kneser graphs. Brouwer's fixed-point theorem.

Recommended courses

4. 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

5. Number theory in Computer Science
Diophantine approximation (Dirichlet's theorem, Farey fractions, transcendental numbers). Diophantine equations (Pell's equation, Thue equations, four squares theorem, Hilbert's tenth problem). Prime numbers (bounds on the prime-counting 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 with 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, applications of submodular functions in economy. Optimization based on enumeration, generating functions of edge cuts and of perfect matchings, enumerative dualities, the maximum cut problem for graphs embedded in 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, one-parametric and multi-parametric programming, relation to multiobjective optimization. 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