# State Exam Requirements, for the English track in the specialization Computer Science and Engineering

### Traversing of graphs (X36TIN) - Bachelor-level course

Depth-first and breadth-first traversals, connectivity, topological sort, strong connectivity, minimum spanning trees, searching state spaces of problems, heuristic searching.

### Graph algorithms and their complexity (X36TIN) - Bachelor-level course

Shortest paths from a single vertex, shortest paths from all vertices, algebraic connectivity, design of greedy algorithms and dynamic programming algorithms.

### Computing models (X36TIN) - Bachelor-level course

Languages and automata, finite automata, nondeterminism, Turing machines, universal Turing machine, undecidable problems.

### Logic (X01DML) - Bachelor-level course

Predicate logic and its interpretation, semantic consequence, tautology, mathematical induction, structural induction.

### Probability (X01MVT)

Random variables and their properties, unary and binary operations on random variables, fundamental distributions, random vectors, mixtures of random variables.

### Statistics (X01MVT)

Method of moments, maximum likelihood method. Estimates for the mean and variance. Goodness-of-fit tests, correlation tests, non-parametric tests. Hypothesis testing.

### Groups (X01AVT)

Semigroups, monoids, groups, Abelian groups, uses of groups, Euler-Fermat theorem, arithmetics (mod p), Chinese remainder theorem.

### Fields (X01AVT)

Residual class fields, polynomials over finite fields Zp, irreducibility, rings and fields of polynomials, Euclid's algorithm for polynomials over Zp, applications of finite fields.

### Lattices (X01AVT)

Binary relations and their properties, relationship between directed graphs and binary relations, equivalence and order relations, lattices and distributive lattices.

### Relationships among structures (X01AVT)

Homomorphisms of structures described by operations and/or relations, equalities, free objects, free algebras.

### Oscillations and waves (X02F2P)

Oscillating systems, resonance. Wave equation. Fourier transform, linear and nonlinear phenomena. Group velocity, phase propagation velocity.

### Electromagnetic field (X02F2P)

Significance of Maxwell equations. Electromagnetic waves in vacuum, conductors, optical fibers, plasma, anisotropic environment.

### Light (X02F2P)

Group velocity and phase propagation velocity of light. Optical fibers, diffraction, diffraction grating. Lorentz transform, Doppler effect.

### Quantum theory fundamentals (X02F2P)

Uncertainty principle, Schroedinger and Heisenberg matrix mechanics, spin. Applications of quantum theory. Tunnel effect, barriers, quantum computers, quantum cryptography, the EPR paradox. Quantum description of electromagnetic field, interactions of elementary particles.

### Numerical simulations in physics (X02F2P)

Methods of solving ordinary and partial differential equations, Monte Carlo methods, variational methods.

### Complexity (X36PAA)

Time (operational) and space (memory) complexity. Average, worst-case and best-case operational complexity. Asymptotic complexity. P and NP classes: definitions, relationship to the state space, polynomial reduction, NP-complete and NP-hard problems. Cook theorem, the idea of the proof of NP-completeness.

### Evaluation (assessment) of quality of algorithms (X36PAA)

Definition of an error. Approximation algorithms. Experimental evaluation of algorithms.

### Exact methods and heuristics (X36PAA)

Local and global methods. Recursion, iteration, divide-and-conquer. Algorithms for searching the state space (backtracking, branch-and-bound). Sweep-line technique. Principles and properties of dynamic programming. The notion of "neighborhood" in local methods. Constructive and iterative heuristic methods. Prevention of getting trapped in a local minimum. Principle and skeleton of the following methods: simulated annealing, genetic algorithms, tabu search.

### Interconnection networks of parallel computers, communication algorithms (X36PAR)

Interconnection networks for parallel computers (taxonomies, requirements for their properties). Direct interconnection networks: orthogonal and sparse hypercubic. Multistage indirect networks. The embedding problem. Simulation of networks and computational equivalence of networks. Routing algorithms and router architectures. Basic switching techniques. The deadlock problem and its solution (channel dependency graph, nonblocking routing, virtual channels). Permutation algorithms (minimal, randomized, sorting-based, off-line). Efficient and optimal algorithms for one-to-all and all-to-all broadcast and scatter and for multicast: lower bounds and upper bounds on the number of rounds and communication latency.

### Parallel algorithms (X36PAR)

Criteria for evaluation of complexity of parallel computations. Optimality and scalability of algorithms (isoefficiency functions). NC class and P-complete problems. PRAM models and their mutual simulations. APRAM model and optimal APRAM algorithms. Fundamental parallel NC algorithms on PRAM and usual interconnection networks: parallel reduction and prefix computation on arrays, pointer jumping and computation on a linked list, Euler tour construction in a graph. Parallel sorting algorithms, sorting networks and 0-1 lemma. Parallel algorithms for linear algebra (matrix transposition, matrix-vector multiplication, matrix-matrix multiplication, solving systems of linear equations).

### Modeling of software systems (X36ASS,X36OBP)

Conceptual data, functional and dynamic models. Methods of analyzing requirements on software and information systems. Techniques and methods of object-oriented analysis and design. Logical models used at design time. The UML notation, formal and semi-formal presentation techniques, semantic specifications.

### Software systems architectures (X36ASS,X36OBP)

Software quality, integration, interoperability and reusability. Architecture design, architectonic styles, reference models, reference architectures. Component architectures, standards for inter-component communication. Object-oriented architecture.

### Object-oriented programming (X36OBP)

Theoretical foundations of object-oriented programming. Notions of object, class, message, method, polymorphism, inheritance; other relationships among objects. Object-oriented programming languages (pure and mixed).

### Non-procedural languages for communication with relational databases (X36SQL,X36DB2)

Data definition language DDL SQL. Table, view, index, sequence. Integrity constraints, definition, and usage. Queries, projection specification, selecting, various types of joins. Capabilities under various SQL standards. Single-line and aggregation functions, subqueries. Data manipulation language DML SQL. Effects of integrity constraints on processing of updates. Transactions, locks, transaction control statements, implicit and explicit commits of transactions. Object-oriented extensions of the SQL.

### Procedural languages for communication with databases (X36SQL,X36DB2,X36OBP)

Language of modules as a procedural extension of the SQL. The structure of a block, scalar types, records, arrays, cursors, exceptions, exception handling. Modules stored in a database - procedure, function, package, trigger. Other procedural and object-oriented languages for communication with databases.

### Specific problems of database systems (X36DB2,X36OBP)

Methods of designing E-R diagrams. The binary E-R model. Transformation of an E-R diagram into a relational data model. Distributed databases, the 2-phase commit protocol in distributed databases. Multidimensional databases, object-relational, and object-oriented databases. Query evaluation, execution plan, and optimization.

### Data compression (X36KOD)

Models and encoding. Entropy. Integer encoding. Statistical, dictionary, and context methods of data compression.

### Mechanisms of distributed computations (X36DSV)

Synchronous and asynchronous computation, acknowledgment mechanisms, routing and flow control, message passing, distributed shared memory. CORBA, Java RMI, and SOAP procedural mechanisms. Mobility.

### Distributed algorithms (X36DSV)

Logical time, resource sharing, mutual exclusion, deadlocks, termination detection, data and process replication, consistency, fault tolerance, quorum mechanisms, stabilizing algorithms.