State doctoral examination

Syntax of propositional logic, Hilbert axiomatic system, types of mathematical proofs, deduction theorem, correctness and completeness, compactness theorem. Predicate logic, syntax and semantics, logically equivalent formulas, laws of the predicate logic, interpretation, model, theory, Hilbert axiomatic system, correctness and completeness. Many-valued logics, fuzzy logics. Set theory: potential infinity, cardinality, countable and uncountable sets, continuum hypothesis, axiom of choice, formal systems.

Polynomials, roots of polynomials, fundamental theorem of algebra, linear algebra, Gauss elimination, methods for solving systems of linear equations, linear spaces, linear dependence and independence, base, dimension, coordinates, linear mapping, matrices, matrix operations, determinant, LU decomposition, affine space, eigenvalues and eigenvectors, orthogonality, analytic geometry, linear codes. Semi groups, monoids, groups, Abelian groups, Euler-Fermat theorem, modular arithmetic, Chinese remainder theorem, primality testing. Residual class fields, polynomials over finite fields, irreducibility, rings and fields of polynomials, Euclid´s algorithm for polynomials over Zp, applications of finite fields. Boolean algebra. Binary relations and their properties, directed graphs and binary relations, equivalence and order relations, lattices and distributive lattices. Homomorphisms of structures described by operations and/or relations, free objects and free algebras.

Probability and random events, conditional probability, dependency and independency of events. Bayesian formula, random variables, distribution function, continuous and discrete distributions, random vectors, mixtures of random variables, hash functions, probabilistic algorithms. Information theory, entropy, relative entropy and mutual information. Random sampling, basic sampling statistics, sample mean and variance, hypothesis testing, mean value and variance tests, non-parametric tests, goodness-of-fit tests and correlation, analysis of variance, normality testing. Correlation and regression analysis, linear and quadratic regression, sample correlation. Stochastic processes, Markov chains, queuing theory, Monte Carlo methods. Bootstrap methods.

Asymptotic complexity, time and memory complexity in the best, average, and worst cases. Complexity classes P and NP, NP-hard and NP-complete problems, polynomial reduction, Cook theorem, Turing machines and their generalization, halting problem, undecidable problems, computability and enumerability. Exact methods and heuristics, local and global methods, algorithms for state space search (backtrack, branch-and-bound), constructive and iterative heuristic methods, prevention of getting trapped in a local minimum, simulated annealing, genetic algorithms, taboo search.

Graph models, undirected graphs, isomorphism, neighbourhood, connectivity, directed graphs, strong connectivity, depth-first and breadth-first graph search, topological ordering, dominating and independent sets, graph colourability, planarity, regularity and symmetry, trees, spanning trees, circuits, minimal spanning trees, shortest paths, network flows, matching problems, design of greedy algorithms. Basics of combinatorics, inclusion and exclusion principle, cardinality of finite discrete structures (sets, mappings, realions, trees, graphs, etc.).

Regular expressions, languages and grammars, nondeterminism. Context-free languages and grammars, stack automata, parsing models, LL, LR, strong LR, SLR, LALR grammars, transformation of context-free grammars, parser construction. Formal translations, regular translation grammars and finite translation automata, context-free translation grammars and stack translation automata, formal translation directed by LL parser. Attribute grammars, calculation of attribute values, formal translations and one-pass attributed translations. Translator and its parts, lexical analyzer, parser, processing of semantics, target program generation, optimization.

Algorithm design techniques (recursion, iteration, divide and conquer, backtracking, greedy algorithms, dynamic programming), time and memory analysis of algorithm complexity, specification and implementation of data structures, data structures and their properties (arrays, lists, sets, tables, queues, stacks, trees, heaps), search and search trees, balancing, sorting algorithms and their stability, text search algorithms, graph and network algorithms, computational geometry algorithms, algebraic algorithms and linear algebra algorithms. Scalability and optimality of parallel algorithms, parallel complexity theory, the PRAM and APRAM models, parallel prefix sum, the Euler tour technique, parallel sorting, parallel algorithms for linear algebra.

Principles of the object-oriented paradigm, concepts of object-oriented programming (data types, objects, message, classes, polymorphism, inheritance, static and dynamic binding, exception handling), object-oriented and object-based programming languages. Functional programming, the lambda calculus, theory of recursive functions, the fixed point theory, functional programming languages, logic programming, logic programming languages, implementation of functional and logic programming languages on Von Neumann architectures, virtual machines, memory control.

Von Neumann and Harvard architectures, CISC and RISC processors architecture, machine code and data, interrupt processing, polyadic number systems, codes for displaying negative numbers, adders, subtractors, multipliers and dividers, linear and cyclic safety codes, processor microarchitecture, stream processing of instructions and arithmetic operations, instruction-level parallelism, superscalar and VLIW processors, jump prediction and speculative instruction execution, vector processors, multithreaded and multicore processors, memory hierarchy, associative memories, hidden memories, hardware support for memory virtualization, dynamic address translation and TLB, single-chip microcomputers, embedded processors, control computers, microcomputer input and output embedding, non-von Neumann computer architectures, parallel computer architectures, with shared memory (symmetric multiprocessors), with distributed memory, shared memory coherence and consistency, synchronization locks and barriers.

OS kernel, OS implementation, privileged user and administrator, processes and threads and their scheduling, communication and synchronization, pipelines, time-dependent errors, critical sections, mutual exclusion methods, semaphores, monitors, classical synchronization tasks, process deadlocks, OS resource allocation, processor virtualization, memory allocation and management, memory virtualization, paging, segmentation, file systems: files and directories, file access security, storage virtualization, real-time operating systems.

Communication channels, communication protocols, transmission medium sharing, frequency division and time division multiplexing, broadband networks, routers, bridges and switches, fault protection mechanisms and protocols, access methods for local and wireless networks, throughput, latency and datapath load, quality of services requirements, congestion protection, internal and end-to-end flow control, data-flow analysis, mechanisms of cryptographic protection of data transmission and authentication. Interconnection networks for parallel computers, bus networks, orthogonal and sparse hypercube direct network interconnection, indirect multistage networks, nesting, simulation of networks and computational equivalence of networks, permutations algorithms, group communication and one-to-all and all-to-all communication, mobile systems architecture, infrastructure and ad-hoc networks, routing algorithms, topology optimization, construction and automatic (re)configuration, consumption optimization, transmission capacity, latency, use of group communication, mobility support in the Internet, VoIP networks and middleware systems, autonomy and cooperation in mobile systems, optical networks.

Computational models, cooperating automata, Petri nets, process algebras, pi-calculus, distributed computing, global state, causality, logical time, exclusive use algorithms, deadlock detection and prevention, termination of computation, component failures, fault tolerance, quorum algorithms, replication, asymmetric and symmetric algorithms, causality in distributed systems, logical time, Lamport clocks.

Methods of software project management, planning, complexity estimates, responsibility matrices, monitoring, testing, metrics, life cycle of the program, data and functional analysis, conceptual models used for analysis documentation, logical models used for design documentation, program documentation of implementation, software engineering methodologies and presentation techniques, conversion of conceptual models to logical models and their implementation, technology used in design, structured technologies, object-oriented technology, component technology, technology for network applications, design patterns, technology used in program systems implementation, web technology, testing, validation and verification, integration testing, user interface testing, final tests, load tests, acceptance tests, operation and maintenance of program software.

Conceptual data models, ER-model, entities, attributes, integrity constraints, logical data models, relational, object and relational-object models, functional dependencies, normal forms, relational schema design, expression of integrity constraints for entity types and for relational types, primary key, unique key, foreign key, referential integrity, query languages, database system architectures, client-server, database management system (DBMS), centralized and distributed database systems, data distribution, data replication, multi-user DB systems, transaction processing, transactions and locks, accepting and rejecting changes, ensuring data consistency in the case of parallel access, physical representation of data, record, file, table, index, techniques for storing and accessing records, B-trees. Information system architecture and layers, decision support systems and OLAP systems, company information systems.

Mathematical foundations of cryptography, symmetric and asymmetric algorithms, block, stream, exponential ciphers, public-key cryptography, digital signature, certificates, elliptic-curve cryptosystems, HW implementation of cryptographic algorithms.

Machine learning algorithms, ontology and knowledge representation, speech and natural language processing, statistical and symbolic methods of artificial intelligence, artificial neural networks, theoretical foundations, paradigm classification, supervised and unsupervised learning algorithms, evolutionary algorithms, knowledge extraction from data, clustering, classification, modelling and prediction of data, inductive modelling, self-organization as a means for discovering relationships between objects, automatic construction of models by methods of artificial intelligence.

Continuous simulation, simulation of discrete systems, quasi-parallel environment, digital circuit simulation (levels of abstraction, synchronous and asynchronous simulations, simulation of structures, simulation of delays, resolution functions, transaction-level modelling), queueing systems: simulation and analytical models, generation, transformation and testing of pseudorandom sequences, parallel simulations (conservative and optimistic methods).

Graphic items and their attributes, coordinate systems and transformations, colour spaces and models, raster and vector graphics, image operations, planar graphics algorithms, basics of spatial graphics and solid modelling, textures, visibility solutions, lighting models, shading, ray tracing and radiosity, interpolation and approximation methods of curves and surfaces modelling, data structures and algorithms of computational geometry, fractals, virtual reality, data structures for data visualization, volume data visualization, dynamic phenomena and information, principles of user interface design, user interface models, user interface testing and evaluation, design of user interface in cooperation with users (usability, accessibility), problems of perception of graphic information.

Conceptual modelling, ontologies, foundational ontologies, modal logic, conceptual modelling in software engineering, conceptual modelling in enterprise engineering, conceptual modelling in the semantic web (RDF, OWL), structural conceptual modelling, OntoUML/UFO, conceptual modelling of behaviour, DEMO method, specification of constraints in conceptual models (OCL), quality of conceptual models.

Methods of implementation of digital circuits – VLSI design styles, custom circuits, regular structures, electrical level and timing. Design of asynchronous systems. Quantitative approach to design. Design to requirements: size, consumption, operating frequency, reliability, safety, testability, real-time operation. Combinatorial synthesis, representation of logical function, minimization, decomposition, exact and heuristic SAT methods. Principles of reconfiguration (complete, partial, dynamic), reconfiguration latency, reconfiguration control. Hardware/software co-design, models, simulations. System-on-chip (SoC) design, efficient design and communication of multiple cores/processors on a chip (NoC). Tools for description and verification of digital systems.

Defects of digital circuits and their modelling using fault models. Optimized ATPG systems for testing of specific faults and systems for test vectors compression and decompression. Built-in self-test (BIST) diagnostic tools. Test generators based on LFSR, CA, test evaluation, built-in MISR analyzers. Implementation of a testing system using a combination of tools for fault testing. Implementation of systems with increased reliability and a higher level of security. Design of self-controlled and totally self-checking (TSC) circuits. Design of automatic fault correction systems. Calculations of reliability indicators, block and Markov models.

Theoretical foundations of multidimensional statistical models and methods of advanced learning and parameter estimation. Context-based and non-context-based classification methods and multi-classifier systems. Data normalization and invariants. Modern methods of selection of attributes. Classification of text documents. Methods of testing and verification of recognition algorithms and benchmarking.

Methods of dynamic branch prediction and speculative execution of instructions. Methods of speculative pre-selection of data. Support for parallel threads. Multi-level hierarchies of hidden memories. Architecture, structures and algorithms of virtually distributed shared memory in multiprocessor systems. Algorithms and tools for process synchronization in distributed computer systems.

Automated description of communication protocol, RTAG system. The LOTOS specification language. Protocol transformations. Protocol validation and verification. Dynamic behaviour of networks under load, flow-control mechanisms.

Theoretical foundations of artificial neural networks, paradigm classification, neural networks as approximators and classifiers. Supervised and unsupervised methods of learning of neural networks. Gradient and evolutionary methods of learning. Development of neural network topologies by evolution, genetic programming. Pulsed neural networks. Self-organization for analysis and knowledge mining. Inductive modelling methods. Automatic construction of models by methods of artificial intelligence. Acceleration of calculations in the field of neural networks.

Special classes of graphs (interval, chordal and perfect). Tree structures (tree-width, path-width, clique-width). Advanced colouring of graphs (list colouring, selectivity, edge colouring). Flows and sections. Random graphs (probability algorithms, web graph). Visualization of graphs.

Parallel complexity theory and P-completeness. Parallel prefix sum over field and list. Parallel tree contractions. Parallel graph algorithms. Optimal parallel sorting algorithms. Parallel algebraic algorithms and algorithms for computational geometry.

Entropy. Number coding. Statistical, dictionary and context methods of data compression and their properties. Layered data compression methods. Word-based compression. Use of finite automata in data compression. Efficient search in compressed texts.

Search for strings and sequences in one-dimensional and multidimensional text. Search automata and their simulations. Search in preprocessed texts, index and signature methods. Search data structures. Searching for regularities in text. Tree languages, tree and stack automata. Methods for searching for patterns in trees. Indexing of tree structures. Searching for regularities in trees.

Syntax and semantics of specification languages, different ways of specification of systems. Algebraic specifications, different ways of implementing algebraic specifications. Transcription systems, conversion of specification to a transcription system, abstract transcription machine. Prototyping of algebraic specifications, examples. Other methods of formal specifications, examples.

Errors and their estimates, numerical conditionality and stability. The principle of iterative methods, Banach’s fixed point theorem, contraction mapping. Selected methods for solving large systems of linear equations. Use of libraries for precise calculations. Solution of systems of nonlinear equations. Use of modular arithmetic for errorless calculation. Interval and p-adic arithmetic. Continued fractions.

Elements of quantum mechanics. Quantum nonlocality, quantum correlation – entanglement, entanglement rate. Quantum random number generator. Quantum teleportation. Quantum cryptography – principle, BB84 protocol, one-photon and two-photon methods, current state. Quantum computers, computational complexity; qubit, quantum gates. Quantum algorithm for factorization. Applications of quantum algorithms.

Objectives of information retrieval in comparison with database management, document relevance and fuzzy logic, Zipf law, descriptors and indexíng, text processing for indexing, vector model of information retrieval, indexing by n-grams, term clustering, document clustering, centroid in vector model, query expansion, answer expansion, position indexing and proximity operator, measures in information retrieval (precision, recall, ROC), similarity measures (edit distance, Jaccard coefficient, cosine similarity), weights in information retrieval (term frequency, inverse documents frequency), ranking methods.

Objectives and problems of text mining, architecture of text mining systems, text processing used for representing documents in vector model, dimension reduction by chi-square method, dimension reduction by latent semantic indexing and concepts, clustering methods (square error, k-means, nearest neighbor), classification methods (Bayes, k-NN), semantic relation detection, named entities and pattern extraction, parsing, part-of-speech tagging, coreference, first story detection, text summarization, automatic query answering.

Novel architectural styles to design applications and services, methods to ensure good application performance such as scalability and availability, languages to represent application interfaces at information, process and technological levels, methods to secure web services, service lifecycle process and its automation.

Languages to represent semantics of data, ontologies, linked data principles, languages to query semantic data and seasoning algorithms, methods for semantic annotation of content.

Application of the finite difference method in partial differential equations. Variational formulation of boundary value problems for partial differential equations, weak solution. Mathematical fundamentals of the finite element method. Algorithmization in the finite element method. Construction of sparse systems of linear algebraic equations. Mathematical fundamentals of the finite volume method.

Sparse systems of linear algebraic equations, computer representation of sparse systems, sparse matrices, storage formats for sparse matrices. Algorithms for sparse matrix vector multiplication. Numerical methods for solving sparse systems of linear algebraic equations, iterative methods, conjugate gradient method, preconditioning. Numerical methods for computing eigenvalues and eigenvectors of sparse matrices.

Transition systems, temporal logic (LTL, CTL), abstraction, abstraction refinement, counter-example guided abstraction refinement, decision procedures for predicate logical theories, SAT and SAT modulo theories.

Design and testing of true random generators (TRNG). Design and testing of physical unclonable functions (PUF). PUF and TRNG models. Sources of entropy in FPGA and ASIC technologies. Metrics for evaluating TRNG and PUF quality. Side channel attacks. Power analysis attacks (SPA, DPA). Side channel measurements and processing of the measured signal. Side channel modelling. Profiled and unprofiled attacks. Fault injection attacks (faults via EM field, supply voltage, clock signal). Resistance to tampering.