Theoretical Foundations of Computer Science

Topics offered for the exam

• Graph theory
• Advanced graph theory
• Computational complexity
• Algorithms and complexity for hard problems
• Fundamentals of probability theory
• Markov chains with discrete and continuous time
• Logic and finite model theory
• Advances topics in mathematics

In addition to the listed topics, other topics belonging to the mathematical and theoretical foundations of informatics may be discussed with and assigned by the guarantor and examiners.

Graph theory

Graphs are one of the mostly used mathematical structures in computer science. The student will study in appropriate depth all basic areas of graph theory. The topic is suitable for all students even without a theoretical background, and the study literature can be adjusted with more emphasis on the practical aspects of graph applications.

Syllabus:
Basic concepts, matching and covers, connectivity, planar graphs, graph colorings, flows in graphs.

Main study materials:
Reinhard Diestel, Graph Theory , 4th edition 2010, Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume 173, ISBN 978-3-642-14278-9, chapters 1-6, 167 pages (this includes also basic areas taught in the master-level courses at FI).

Examiners: prof. RNDr. Petr Hliněný, Ph.D. , prof. RNDr. Daniel Kráľ, Ph.D., DSc. , doc. Mgr. Jan Obdržálek, PhD.

Other recommended literature:
Matoušek, J., Nešetřil, J .: Chapters from discrete mathematics. Karolinum, Prague 2009

Advanced graph theory

Graphs are one of the mostly used mathematical structures in computer science. This topic is suitable for students who already do their research in graph theory itself or in theoretical disciplines closely tied with graphs. The student will study in depth selected directions of graph theory, especially those related to advanced algorithms and computational complexity (e.g., structural graph theory).

Syllabus:
Choose from one of the directions below:

• Structural graph theory - extremal graph theory, graph minors, connectivity, WQO, tree-decompositions.
• Topological graph theory - embeddings and drawings of graphs, genus of a graph, combinatorial description of graph embeddings, edge-width and face-width.
• Theory of graph sparsity - shallow minors, tree-depth, sparse classes of graphs and their characterization.

Main study materials (one of):
Reinhard Diestel, Graph Theory , 4th edition 2010, Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume 173, ISBN 978-3-642-14278-9. A selection of advanced chapters assigned by the examiner.
Bojan Mohar, Carsten Thomassen: Graphs on Surfaces, Johns Hopkins University Press, 2001 Chapters 1-4, 5.1, 5.5, 136 pages.
J. Nešetřil and P. Osson de Mendez: Sparsity, Springer, 2012, ISBN 978-3-642-27874-7. Chapters 1-7, 170 pages.

Examiners: prof. RNDr. Petr Hliněný, Ph.D. , prof. RNDr. Daniel Kráľ, Ph.D., DSc. , doc. Mgr. Jan Obdržálek, PhD.

Computational complexity

The student will study the basic methods and techniques in the field of computational complexity and learn about their use in other areas of informatics. This is a topic suitable general acquaintance with computational complexity.

Syllabus:
Computational models and computational complexity. Complexity classes, the hard and complete problems. Methods of diagonalization and separation of complexity classes. Space complexity. Polynomial hierarchy and alternation. Logic circuits. Randomized algorithms, Interactive proof systems. Lower bounds for specific computational models. Communication complexity. PCP and non-approximability.

Main study materials:
S. Arora, B. Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009. The examiner determines a selection of chapters in the range of 100-200 pages from the textbook.

Examiners: prof. RNDr. Ivana Černá, CSc. , prof. RNDr. Daniel Kráľ, Ph.D., DSc. , doc. RNDr. Petr Novotný, Ph.D.

Other recommended literature:
D. Kozen, Theory of Computation. Springer, 2006.
B. Barak: An Intensive Introduction to Cryptography (Lecture Notes), a selection of chapters

Algorithms and complexity for hard problems

The topic covers methods and techniques for solving hard problems (and not only those in NP). Students can choose "classical" approaches including approximation, randomized and heuristic techniques, and pseudopolynomial and (reasonable) exponential algorithms. The other option is to focus on recently growing parameterized approaches which measure complexity of algorithms and of problems with respect to additional (usually fixed) parameters. The discussed techniques can be applied in the design of specific algorithms from various application areas.

Syllabus:
Choose from one of the directions below (or discuss other possibilities with the guarantor and/or the potential examiners):

• Classical algorithms: Deterministic approaches (pseudopolynomial and parameterized algorithms, low-level exponential algorithms). Approximative techniques (combinatorial approach, approach based on linear and semilinear programming, random approach). Random algorithms (classification, techniques, applications in the field of data structure design, graph algorithms). Heuristic methods (local search, simulated annealing and more).
• Parameterized algorithms and complexity: Parameterized problems and reductions. Fixed-parameter tractability, FPT and XP classes, W[i] hierarchy and W[1]-complete problems. Kernelization. Algorithmic metatheorems.

Main study materials (one of):
J. Hromkovič, Algorithmics for Hard Problems. 2nd Edition. Spinger, 2006. The examiner determines a selection of chapters in the range of 100-200 pages from the textbook.
J. Flum and M. Grohe, Parameterized Complexity Theory, Springer, 2006. Chapters 1-6.1 (p.1-114), 9.1-9.3 (p. 207-222)
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer 2015, https://link.springer.com/book/10.1007/978-3-319-21275-3. Combination of any four chapters (except introduction), 110 to 150 pages.

Examiners: prof. RNDr. Ivana Černá, CSc. , prof. RNDr. Petr Hliněný, Ph.D. , prof. RNDr. Daniel Kráľ, Ph.D., DSc. , doc. Mgr. Jan Obdržálek, PhD.

Other recommended literature:
V. Vazirani, Approximation Algorithms. Springer, 2001.
R. Motwani, P. Raghava, Randomized Algorithms. Cambridge University Press, 1995.
R. Downey and M. Fellows, Fundamentals of Parameterized Complexity, Springer, 2013.
R. Niedermayer, Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.

Fundamentals of probability theory

The general theory of probability is built on the foundations of the theory of measure and integral. The candidate will get acquainted with the general way of introducing basic concepts (probability space, random variable, mean value, etc.) and with selected tools of probability theory, which are often used in practice.

Syllabus:
Lebesgue measure, measurable function, random variable; Lebesgue integral, mean; the law of large numbers and its variants; Borel-Cantelli lemma, Kolmogorov's law 0-1.

Main study material:
JS Rosenthal, A First Look at Rigorous Probability Theory, World Scientific, 2006. Chapters 1-7 (pp. 1-82), or Chapters 1-6,8.

Examiners: doc. RNDr. Tomáš Brázdil, Ph.D. , prof. RNDr. Daniel Kráľ, Ph.D., DSc. , prof. Dr. rer. nat. RNDr. Mgr. Bc. Jan Křetínský, Ph.D. , prof. RNDr. Antonín Kučera, Ph.D. , doc. RNDr. Vojtěch Řehák, Ph.D.

Other recommended literature:
P. Billingsley. Probability and Measure, Wiley, 1995.

Markov chains with discrete and continuous time

Markov chains are a basic tool for modeling and analysis of random processes in natural and technical sciences, including computer science. The candidate will get acquainted with the basics of the theory of Markov chains with discrete and continuous time.

Syllabus:
Recurrent and transient states, probability and mean return time, invariant probability distribution, Ergodic theorem.

Main study material:
JR Norris, Markov chains, Cambridge Univ. Press, 1997, Chapters 1-3 (pp. 1-125).

Examiners: doc. RNDr. Tomáš Brázdil, Ph.D. , prof. RNDr. Antonín Kučera, Ph.D. , doc. RNDr. Vojtěch Řehák, Ph.D.

Other recommended literature:
W. Feller. An Introduction to Probability Theory and Its Applications, Wiley, 1966 (Volume I, II).
John G. Kemeny, J. Laurie Snell, Anthony W. Knapp. Denumerable Markov Chains. Springer, 1976.

Logic and finite model theory

Logic, in particular Finite Model Theory, is used in many places in computer science. The candidate will get acquainted with the basics of Finite Model Theory and its relation to computer science. Alternatively, the candidate may focus on studying the basics of mathematical logic and its relation to computer science.

Syllabus:
Choose from one of the directions below (or discuss other possibilities with the guarantor and/or the potential examiners):

• Finite model theory - Ehrenfeucht-Fraïssé games, the theorems of Hanf and Gaifman, capturing complexity classes.
• Mathematical logic - syntax, semantics, completeness, incompleteness, Löwenheim-Skolem, compactness.

Main study materials:
Ebbinghaus, Flum: Finite Model Theory, Springer, 1995 (Chapters 1-2, 4-6).
Ebbinghaus, Flum, Thomas: Mathematical Logic, Springer, 1994 (Chapters 1-7).

Examiners: Dr. rer. nat. Achim Blumensath , prof. RNDr. Antonín Kučera, Ph.D. , doc. Mgr. Jan Obdržálek, PhD.

Other recommended literature:
...

Advanced topics in mathematics

It is possible to be assigned advanced topics from a selected area of mathematics if such topics are relevant to the PhD study of a student. Areas of mathematics particularly include algebra, mathematical analysis, number theory and set theory, and examples of suitable study materials are given below as guidance. The exact choice of topics will be determined on case by case basis.

Syllabus:
The particular area of mathematics and topics within this area as determined in each case individually.

Main study materials:
Donald L. Cohn: Measure Theory, Springer, 2013.
Allen Hatcher: Algebraic Topology, Cambridge University Press, 2002.
Kenneth Ireland, Michael Rosen: A Classical Introduction to Modern Number Theory, Springer, 1990.
Thomas Jech: Set Theory, Springer 2003.
James C. Robinson: An Introduction to Functional Analysis, Cambridge University Press, 2020.
Loring T. Wu: An Introduction to Manifolds, Springer, 2011.
Peter Walters: Ergodic Theory, Springer, 1982.

Examiners: prof. RNDr. Daniel Kráľ, Ph.D., DSc. ,