N-TEI questions Theoretical computer science

Common Core Program

Logic: Syntax, semantics and inference systems for propositional and predicate logic, their correctness and completeness. The compactness theorem. Algorithmic decidability and complexity of the satisfiability problem for propositional and predicate logic. Gödel's incompleteness theorems. The resolution principle in propositional and predicate logic. (MA007)
Probability: Definition of probability space. Random variable, definition and its applications, Markov and Chebyshev inequalities. Random processes, Markov chains, invariant distributions, ergodic theorem. Information theory (entropy, mutual information), coding theory (Kraft and McMillan theorem, Huffman coding, error channel capacity theorem).
Complexity: Temporal and spatial computational complexity, basic complexity classes. Relationship of deterministic and non-deterministic classes, Savitch theorem. Probabilistic complexity classes. Alternation and polynomial hierarchy. (IA012)
Semantics of programming languages: Operational, denotational and axiomatic semantics. Complete partial orderings, fixed point theorem. Denotational semantics of the while loop. Partial correctness assertion of programs, weakest input condition, cycle invariant, Hoare derivation system, its correctness and completeness. Principles of automated deductive verification. (IA011)
Design of algorithms: Amortized complexity, examples of applications. Algorithm design techniques: divide and conquer, dynamic programming, hungry algorithms. The shortest path problem in a graph (Bellman-Ford, Floyd-Warshall, Dijkstra).

Specialization - Discrete algorithms and models

Algorithmics for hard problems: approximation algorithms; design of approximation algorithms; approximation schemes. Parameterized algorithms; pseudopolynomial algorithms. Types of probabilistic algorithms; derandomization. (IA101)
Graph theory: Euler's theorem. Euler's theorem. Properties of trees. Planar graphs; Euler's formula; five-color theorem; characterization of planar graphs. Vertex and edge coloring; Brooks' theorem; Vizing's theorem. Vertex and edge coherence; Menger's theorem; König's theorem; Hall's theorem. Ramsey's theorem. (MA010)
Algorithmic game theory: games in normal form; pure and mixed strategies; dominated strategies; iterated elimination of sharply dominated strategies. Nash equilibrium; support enumeration; von Neumann theorem (minimax). Extensive form games; subgame-perfect equilibrium; backward induction. Repeated games; grim trigger; folk theorems. Combinatorial auctions; Bayesian games; Bayesian Nash equilibrium. (IA168)
Optimization (compulsory for study under the 2022/2023 control template): Unconstrained optimization (Nelder-Mead method, method of maximum gradient, Newtonian methods). Linear programming (simplex method) and integer programming. (PV027)
Graph Algorithms (required for study according to the 2023/2024 or newer control template): the minimum skeleton problem (hungry algorithms, Fredman-Tarjan, Karger-Klein-Tarjan). Flows in networks (Ford-Fulkerson, Edmonds-Karp, Dinitz, reducing problems to flows); matching in bipartite graphs. Edmonds' algorithm for maximum matching. Treewidth. Graph isomorphism problem (heuristics, tree isomorphism). (MA015)

Specialization - Formal analysis of computer systems

Model checking: model checking for linear and branching time logics, enumerative and symbolic approaches, bounded model checking, k-induction. Abstraction of transition systems, CEGAR method. Property Directed Reachability. (IA169)
Static program analysis: pointer analysis and dynamically-allocated memory (shape analysis). Program pruning (slicing). Symbolic execution. Automatic test generation (grey-box, white-box testing). Automata verification, symbolic execution and interpolation. Configurable program analysis. (IA159)
Executability and automatic inference: deciding executability of propositional logic formulas (DPLL, CDCL). Predicate logic and theories in predicate logic (linear arithmetic of integers and real numbers, field theory). Deciding satisfiability of predicate formulas with respect to theories, their combinations (CDCL(T)) and techniques for quantified formulas. (IA085)
Algorithms for quantitative verification: timed systems, timed automata, region construction for timed automata. Probabilistic systems, Markov chains (DTMC, CTMC), Markov decision processes. Reachability in probabilistic systems. Rewards in probabilistic systems. Specification and verification of properties of timed and probabilistic systems. (IA175)

Specialization - Quantum and other non-classical computational models

Randomized algorithms: Principles and methods of designing randomized algorithms. Probabilistic complexity classes and their relationship to deterministic complexity classes. Random walks, Markov chains and their applications. Randomness methods in cryptography. (IA062)
Fundamentals of quantum information processing: quantum bit and its state, superposition principle, measurement, evolution of quantum state. Composite systems, state space, generalized Born's rule, quantum entangled states, gates, dense coding and teleportation. Reversible computation of Boolean functions, quantum parellelism. Fundamentals of quantum cryptography (BB84 protocol), Shor's and Grover's algorithm. (IA066)
Algorithmics for hard problems: approximation algorithms; design of approximation algorithms; approximation schemes. Parameterized algorithms; pseudopolynomial algorithms. Types of probabilistic algorithms; derandomization. (IA101)
Cryptography: Symmetric encryption (stream and block ciphers, modes of block ciphers). Cryptographic hash functions, MACs, authenticated encryption. Asymmetric encryption: RSA, discrete logarithm based cryptography, Diffie-Hellman protocol. Elliptic curves and cryptography using them. Digital signatures. Zero-knowledge protocols. Security definitions (semantic security, CPA and CCA security, existence fraud) (IA174)

Specialization - Principles of programming languages

Lambda calculus: syntax, semantics: alpha and beta conversion, order of expression evaluation. Recursion and fixed point combinators. Encoding of data types. Applied lambda calculi. Typed extensions - simply typed lambda calculus, Hindley-Milner system, System F. Type derivation. (IA081 or IA038)
Modern concepts of functional programming: type classes and their implementation, constructor classes, functional dependencies. Functors, monads, their meaning and applications. Monadic transformers. Type extensions - generalized algebraic types (GADT), dependent types. (IA014)
Deterministic context-free languages and their syntactic analysis. Classes LL(k), SLL(k), LR(k) and their parsers. Semantic analysis. Name and range analysis, symbol table. Type checking and type conversion.Code generation techniques, optimization. (PA008, IA006)
Cryptography: Symmetric encryption (stream and block ciphers, block cipher modes). Cryptographic hashing functions, MACs, authenticated encryption. Asymmetric encryption: RSA, discrete logarithm based cryptography, Diffie-Hellman protocol. Elliptic curves and cryptography using them. Digital signatures. Zero-knowledge protocols. Security definitions (semantic security, CPA and CCA security, existence fraud) (IA174)

Specialization - Foundations of Artificial Intelligence

Algorithmic game theory: Normal form games; pure and mixed strategies; dominated strategies; iterated elimination of sharply dominated strategies. Nash equilibrium; support enumeration; von Neumann theorem (minimax). Extensive form games; subgame-perfect equilibrium; backward induction. Repeated games; grim trigger; folk theorems. Combinatorial auctions; Bayesian games; Bayesian Nash equilibrium. (IA168)
Neural networks: Multilayer networks and their expressive capabilities. Learning neural networks: Gradient descent, backpropagation, practical learning issues (data preparation, initialization of weights, choice and adaptation of hyperparameters). Regularization. Convolutional networks. Recurrent networks. (PV021)
Reinforcement Learning: TBA (PA230)
Bayes networks: TBA (IA178)