N-TEI questions Theoretical computer science

For students following the 2022/2023 or newer control template:

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: Discrete and continuous probability space. Random variable and its applications. Mean, variance. Random processes, Markov chains. Information theory (entropy, mutual information), coding theory (Huffman coding, error channel capacity).
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). (IV003)

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, maximum gradient method, Newtonian methods, conjugate gradient method, constrained step methods, least squares problem). Linear programming and integer programming. (PV027)
Graph Algorithms (required for study according to the 2023/2024 or later 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

(compulsory for study according to the 2022/2023 control template)

Model checking: model checking for linear and branching time logics, enumerative and symbolic approaches, bounded model checking. (IA159, IA169)
Testing methods: testing missions and strategies, oracle problem, methods for testing a product without code knowledge (black-box testing) and with code knowledge (white-box testing). Code coverage. Symbolic execution as a method for fault detection and test generation (IA169).
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)
Continuous and hybrid systems: continuous and hybrid systems: definition of system, object, model, system. Dynamical system, transition function, system dimension, equations of state. Continuous, discrete, hybrid system. Linear and nonlinear systems, linearization. Stability and stability characterization. System identifiability, parameter estimation. Achievability in hybrid system. Basic concepts of control theory: controllability, observability. (IV120)

(compulsory for study according to the control template 2023/2024 or later)

Model checking: model checking for linear and branching time logics, enumerative and symbolic approaches, bounded model checking, k-induction. Transition system abstraction, 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: Bellman equations for probabilistic systems. Algorithms for analyzing temporal and reward-based properties, value iteration, strategy iteration, linear and quadratic programming, feedback learning. Region construction for timed systems. (IA175)

Specialization - Quantum and other non-classical computational models

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, quantum sources of randomness, quantum interference and the principle of superposition. Quantum security and the uncertainty principle. Schrodinger's equation and quantum gates. Quantum entanglement and teleportation. Shor's and Grover's algorithm. Basic principles of quantum cryptography (one-time pad system, BB84 protocol). Types of quantum measurements. (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)

For students following the 2021/2022 or earlier control template:

Common Core Curriculum

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.
Probability. Discrete and continuous probability space. Random variable and its use. Mean, variance. Random processes, Markov chains. Information theory (entropy, mutual information), coding theory (Huffman coding, error channel capacity).
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.
Neural networks. Multilayer networks and their expressive power. Neural network learning: gradient descent, backpropagation, practical learning issues (data preparation, weight initialization, hyperparameter selection and adaptation). Regularization. Convolutional networks. Recurrent networks (LSTM).
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's inference system, its correctness and completeness. Principles of automated deductive verification.

Specialization - Algorithms of computational models

Randomization algorithms. Principles and methods of designing randomized algorithms. Probabilistic complexity classes and their relation to deterministic complexity classes. Random walks, Markov chains and their applications. Randomness methods in cryptography.
Fundamentals of quantum information processing. Quantum bit, quantum sources of randomness, quantum interference and the principle of superposition. Quantum security and the uncertainty principle. Schrodinger's equation and quantum gates. Quantum entanglement and teleportation. Shor's and Grover's algorithm. Basic principles of quantum cryptography (one-time pad system, BB84 protocol). Types of quantum measurements.
Numerical methods. Error analysis, absolute and relative error. Iterative methods for solving systems of nonlinear equations, Jacobi and Gauss-Seidel methods. Solution of systems of nonlinear equations, Newton's method. Interpolation and approximation. Numerical derivation and integration.
Algorithmics for hard problems. Algorithmic techniques for solving hard problems: pseudopolynomial and parameterized algorithms. Approximative algorithms. Local search heuristics and genetic algorithms.

Specialization - Formal verification and program analysis

The concept of quality in software development. Software metrics. Principles of Clean Code & SOLID approaches. Code testing in the development cycle. Unit testing, integration testing, system testing and acceptance testing. Testing and optimization of computational performance. Test-based development methods. Software quality assurance management processes. (PV260)
Testing methods. Testing missions and strategies, oracle problem, methods for testing a product without code knowledge (black-box testing) and with code knowledge (white-box testing). Code coverage. Symbolic execution as a method for bug detection and test generation. (IA169)
Model checking. Model checking for linear and branching time logics, enumerative and symbolic approaches, bounded model checking. Abstraction of transition systems, CEGAR method. (IA169, IA159)
Games in the strategic form: Dominant strategies, iterative elimination of strictly dominated strategies, Nash equilibria in pure and mixed strategies. Computing Nash equilibria: Support enumeration, linear programming for zero-sum games, computational complexity. Extensive form games: Perfect and imperfect information, mixed and behavioral strategies, subgame-perfect equilibria, backward induction, repeated games (Folk theorems). Incomplete information games: Strict incomplete information games, dominant strategies, ex-post Nash equilibria; Bayesian games, Bayesian Nash equilibria, auctions.

Specialization - Principles of programming languages

Lambda calculus - syntax, semantics: alpha and beta conversion, order of evaluation of expressions. Recursions and fixed point combinators. Encoding of data types. Applied lambda calculi. Typed extensions - simply typed lambda calculus, Hindley-Milner system, System F. Type derivation.
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.
Compilers. 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.
Real time systems. Concepts of "soft" and "hard" real-time systems. Clock-driven and event-driven scheduling. Periodic tasks: EDF, RM and DM algorithms, optimality, schedulability tests using utilization and time-demand analysis. Aperiodic tasks: polling server, deferrable server, sporadic server, schedulability test using time-demand analysis. Sporadic tasks: Acceptance test. Resource scheduling: priority inversion, deadlock. Priority inheritance protocols, priority ceiling. Basic knowledge of multiprocessor scheduling (time anomalies, task migration, maximum utilization, global vs partitioned scheduling, Dhall effect).

Specialization - Discrete algorithms and models

Games in the strategic form: Dominant strategies, iterative elimination of strictly dominated strategies, Nash equilibria in pure and mixed strategies. Computing Nash equilibria: Support enumeration, linear programming for zero-sum games, computational complexity. Extensive form games: Perfect and imperfect information, mixed and behavioral strategies, subgame-perfect equilibria, backward induction, repeated games (Folk theorems). Incomplete information games: Strict incomplete information games, dominant strategies, ex-post Nash equilibria; Bayesian games, Bayesian Nash equilibria, auctions.
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.
Unconstrained optimization (Nelder-Mead method, maximum gradient method, Newton methods, pooled gradient, constrained step methods, least squares problem). Linear programming and integer programming. Global optimization (simulated annealing, genetic algorithms).
Algorithmics for hard problems. Algorithmic techniques for solving hard problems: pseudopolynomial and parameterized algorithms. Approximate algorithms. Local search heuristics and genetic algorithms.