**Requirements for the comprehensive doctoral examination **

The Ph.D. students sit for the rigorous examination that consists of **two parts. **The requirements for the first part are given in the list of the common areas of the general Informatics fundamentals. The requirements for the second part consist of a list of narrower, more in-depth topics that cover the areas of research within the Informatics DSP; therefore, these topics are similar to topics that the doctoral students explore in their dissertations. When selecting the topics, the doctoral student follows the advice of his/her supervisor. The final selection of topics for the comprehensive doctoral examination is approved by the Chairman of the BBP after consulting with the supervisor and discussion in the BBP.

**Common topics for the comprehensive doctoral examination covering the main fields of Informatics**

**Logic and set theory**

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.

**Algebra**

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 Z_{p}, 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 statistics**

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.

**Computational models, complexity theory, heuristics**

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 theory and combinatorics**

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.).

**Thematic topics**

**Information Retrieval**

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 (presision, recall, ROC), similarity measures (edit distance, Jaccard coefficient, cosine similarity), weights in information retrieval (term frequency, inverse documents frequency), ranking methods.

**Text Mining**

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.

**Modern Web Technologies Principles**

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

**Semantic Web**

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

**Numerical solution of partial differential equations**

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.

**Numerical methods in linear algebra**

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, conjugent gradient method, preconditioning. Numerical methods for computing eigenvalues and eigenvectors of sparse matrices.

Last modified: 13.12.2013, 16:49