Translated using DeepL

Machine-translated page for increased accessibility for English questioners.

Page in original, Czech language.

N-TEI Questions: Theoretical Computer Science

Common Core of the Programme

  1. Logic: Syntax, semantics and inference systems for propositional and predicate logic, their correctness and completeness. Compactness theorem. Algorithmic decidability and the complexity of the satisfiability problem for propositional and predicate logic. Gödel’s incompleteness theorems. The resolution principle in propositional and predicate logic. (MA007)
  2. Probability: Definition of a probability space. Random variable, definition and its applications; Markov’s and Chebyshev’s inequalities. Random processes, Markov chains, invariant distributions, the ergodic theorem. Information theory (entropy, mutual information), coding theory (Kraft–McMillan theorem, Huffman coding, capacity theorem for error-prone channels). (IV111)
  3. Computationalcomplexity: Temporal and spatial computational complexity, basic complexity classes. The relationship between deterministic and non-deterministic classes, Savitch’s theorem. Probabilistic complexity classes. Alternation and the polynomial hierarchy. (IA012)
  4. Semantics of programming languages: Operational, denotational and axiomatic semantics. Complete partial orders, the fixed-point theorem. Denotational semantics of the `while` loop. Statements on partial correctness of programmes, the weakest input condition, loop invariants, Hoare’s inference system, its correctness and completeness. Principles of automated deductive verification. (IA011)
  5. Algorithm design: Amortised complexity, examples of application. Algorithm design techniques: divide and conquer, dynamic programming, greedy algorithms. The shortest path problem in a graph (Bellman–Ford, Floyd–Warshall, Dijkstra). (IV003)

Specialisation – Discrete Algorithms and Models

  1. Algorithms for hard problems: Approximation algorithms; design of approximation algorithms; approximation schemes. Parameterised algorithms; pseudopolynomial algorithms. Types of probabilistic algorithms; derandomisation. (IA101)
  2. Graph Theory: Euler’s theorem. Ore’s theorem. Properties of trees. Planar graphs; Euler’s formula; the five-colour theorem; characterisation of planar graphs. Vertex and edge colouring; Brooks’ theorem; Vizing’s theorem. Vertex and edge connectivity; Menger’s theorems; König’s theorem; Hall’s theorem. Ramsey’s theorem. (MA010)
  3. Algorithmic game theory: Games in normal form; pure and mixed strategies; dominated strategies; iterated elimination of strictly dominated strategies. Nash equilibrium; support enumeration; von Neumann’s theorem (minimax). Extensive form games; subgame-perfect equilibrium; backward induction. Repeated games; grim trigger; folk theorems. Combinatorial auctions; Bayesian games; Bayesian Nash equilibrium. (IA168)
  4. Optimisation (compulsory for the study programme according to the 2022/2023 curriculum): Unconstrained optimisation (Nelder–Mead method, steepest descent method, Newtonian methods). Linear programming (simplex method) and integer programming. (PV027)
  5. Graph algorithms (compulsory for students following the 2023/2024 study plan or later): The minimum spanning tree problem (greedy algorithms, Fredman–Tarjan, Karger–Klein–Tarjan). Flow problems in networks (Ford–Fulkerson, Edmonds–Karp, Dinitz, reduction of problems to flow problems); matching in bipartite graphs. Edmonds’ algorithm for maximum matching. Tree breadth. The graph isomorphism problem (heuristics, tree isomorphism). (MA015)

Specialisation – Formal Analysis of Computer Systems

  1. Model checking: Model checking for linear-time and branching-time logics, enumerative and symbolic approaches, bounded model checking, k-induction. Abstraction of transition systems, the CEGAR method. Property-directed reachability. (IA169)
  2. Static programme analysis: Analysis of pointers and dynamically allocated memory (shape analysis). Programme slicing. Symbolic execution. Automatic test generation (grey-box, white-box testing). Verification using automata, symbolic execution and interpolation. Configurable programme analysis. (IA159)
  3. Satisfiability and automated reasoning: Satisfiability decision for propositional logic formulas (DPLL, CDCL). Predicate logic and theories in predicate logic (linear arithmetic of integers and real numbers, field theory). Decision on the satisfiability of predicate formulas with respect to theories and their combinations (CDCL(T)), and techniques for quantified formulas. (IA085)
  4. Algorithms for quantitative verification: Timed systems, timed automata, region-based construction for timed automata. Probabilistic systems, Markov chains (DTMC, CTMC), Markov decision processes. Attainability in probabilistic systems. Rewards in probabilistic systems. Specification and verification of properties of timed and probabilistic systems. (IA175)

Specialisation – Quantum and other non-classical computational models

  1. Randomised algorithms: Principles and methods for designing randomised algorithms. Probabilistic complexity classes and their relationship to deterministic complexity classes. Random walks, Markov chains and their applications. Randomised methods in cryptography. (IA062)
  2. Fundamentals of quantum information processing: The quantum bit and its state, the principle of superposition, measurement, evolution of the quantum state. Composite systems, state space, the generalised Born rule, quantum-entangled states, gates, dense coding and teleportation. Reversible computations of Boolean functions, quantum parallelism. Fundamentals of quantum cryptography (BB84 protocol), Shor’s and Grover’s algorithms. (IA066)
  3. Algorithms for hard problems: Approximation algorithms; design of approximation algorithms; approximation schemes. Parameterised algorithms; pseudopolynomial algorithms. Types of probabilistic algorithms; derandomisation. (IA101)
  4. Cryptography: Symmetric encryption (stream and block ciphers, block cipher modes). Cryptographic hash functions, MACs, authenticated encryption. Asymmetric encryption: RSA, cryptography based on the discrete logarithm, the Diffie–Hellman protocol. Elliptic curves and cryptography utilising them. Digital signatures. Zero-knowledge protocols. Security definitions (semantic security, CPA and CCA security, existential forgery) (IA174)

Specialisation – Principles of Programming Languages

  1. Lambda calculus: Syntax, semantics: alpha and beta conversion, order of evaluation of expressions. Recursion and fixed-point combinators. Encoding of data types. Applied lambda calculi. Typed extensions – simply typed lambda calculus, the Hindley–Milner system, System F. Type inference. (IA081 or IA038)
  2. Modern concepts of functional programming: Type classes and their implementation, constructor classes, functional dependencies. Functors, monads, their significance and applications. Monadic transformers. Type extensions – generalised algebraic data types (GADTs), dependent types. (IA014)
  3. Compilers: Deterministic context-free languages and their syntactic analysis. The LL(k), SLL(k) and LR(k) classes and their parsers. Semantic analysis. Analysis of names and scopes, symbol table. Type checking and type conversion. Code generation techniques, optimisation. (PA008, IA006)
  4. Cryptography: Symmetric encryption (stream and block ciphers, block cipher modes). Cryptographic hash functions, MACs, authenticated encryption. Asymmetric encryption: RSA, cryptography based on the discrete logarithm, the Diffie–Hellman protocol. Elliptic curves and cryptography utilising them. Digital signatures. Zero-knowledge protocols. Security definitions (semantic security, CPA and CCA security, existential forgery) (IA174)

Specialisation – Fundamentals of Artificial Intelligence

  1. Algorithmic game theory: Games in normal form; pure and mixed strategies; dominated strategies; iterated elimination of strictly dominated strategies. Nash equilibrium; support enumeration; von Neumann’s theorem (minimax). Extensive form games; subgame-perfect equilibrium; backward induction. Repeated games; grim trigger; folk theorems. Combinatorial auctions; Bayesian games; Bayesian Nash equilibrium. (IA168)
  2. Neural networks: Multi-layer networks and their expressive power. Neural network learning: Gradient descent, backpropagation, practical learning issues (data preparation, weight initialisation, hyperparameter selection and adaptation). Regularisation. Convolutional networks. Recurrent networks. (PV021)
  3. Reinforcement Learning: Markov decision processes, formulation of RL tasks. Main types of RL algorithms, including examples: Monte Carlo vs. temporal difference methods, on-policy vs. off-policy methods, policy evaluation vs. control tasks. Deep Q-networks. Policy gradient methods, Actor-Critic methods, the PPO algorithm. Multi-armed bandit problems. Model-based RL, offline RL. (PA230)
  4. Bayesian networks: TBA (IA178)