Topics for Master degree state examinations - Open Informatics (accreditation before 2016 - running out)

Common part

  1. Efficient algorithms for standard graph problems: Algorithms of finding strongly connected components (Tarjan's, Kosaraju-Sharir's). Finding topological ordering of an acyclic graph. Algorithms of finding minimum spanning tree of a graph (Borůvka's, Prim's, Kruskal's). The Union-Find problem. (AE4M33PAL)
  2. Amortised complexity. Priority queues, heaps (binary, d-regular, binomial, Fibonacci), operations on them and their complexities. (AE4M33PAL)
  3. Exact and approximate matching of sets of patterns. Hamming and Levenshtein distances. Efficient pattern matching algorithms based on finite automata. Standard text search methods (naive, Boyer-Moore). Dictionary automata. (AE4M33PAL)
  4. Search trees: B, B+, R-B, 2-3-4, Splay and their usage in practice. High dimensional search problem, K-D trees. (AE4M33PAL)
  5. Algorithm, algorithmic correctness, algorithmic complexity, problem complexity, order of P, order of NP. (AE4M01TAL)
  6. NP-complete and NP-hard problems, Cook's theorem, heuristics for the solution of NP-hard problems, probabilistic algorithms. (AE4M01TAL)
  7. Turing machines, recursive and recursively enumerable languages, decidability, undecidability, problems algorithmically unsolvable. (AE4M01TAL)
  8. The branch and bound method. Algorithms for integer linear programming. Formulation of optimisation and decision problems using integer linear programming. Flows and cuts. Multi-commodity flows. (AE4M35KO)
  9. Shortest paths. The traveling salesman problem. Heuristics and approximation algorithms. Dynamic programming. The knapsack problem. Pseudo-polynomial algorithms. (AE4M35KO)
  10. Timetabling on a single processor and on parallel processors. Timetabling a project with time limits. Programming with restrictive conditions.(AE4M35KO)

Artificial Intelligence

  1. Ontology - purpose, types of elements, relation to other representation frameworks. Ontology languages - goal, examples of languages and their use. (AE4M33RZN)
  2. Representing uncertainty: modal logic, graphical probability models and inference in them. (AE4M33RZN)
  3. Representation of vague statements using fuzzy sets. Basic operations in fuzzy logic. (AE4M33RZN)
  4. The planning problem definition, representation and complexity of planning problems. Differences in domain independent and domain specific planning. Planning algorithms, searching of state and plan spaces. (AE4M36PAH)
  5. Planning graphs definition and usage, incl. mutexes. Heuristic search, relaxation and abstraction. (AE4M36PAH)
  6. Robot motion planning, configuration space and road maps, randomized sampling methods. Hierarchical planning - problem representation, methods and planning process. (AE4M36PAH)
  7. A basic model of an Evolution Algorithm (EA) and its components. Advantages and disadvantages of EAs over gradient optimization methods. Genetic algorithm and genetic programming: representation, operators and scope of applications. (AE4M33BIA)
  8. Multi-objective evolution algorithms. Pareto domination principle. Algorithms Non-Dominated Sorting Genetic Algorithm (NSGA) and Strength Pareto Evolutionary Algorithm (SPEA) and their differences. (AE4M33BIA)
  9. Supervised and unsupervised artificial neural network learning. Perceptrons and RBF neurons. Summarize neural network paradigms and their application areas. (AE4M33BIA)
  10. Formal concept of autonomous agents and multiagent systems. Agent control architectures, BDI architectures. Distributed problem solving, distributed constraint satisfaction and optimization algorithm. (AE4M36MAS)
  11. Non-cooperative game theory. Games in the normal and extensive form. Solution concepts for non-cooperative games (in particular the Nash equilibrium), their properties and algorithms for their computation. Systematic (in particular minimax and alfa-beta pruning) as well as sampling-based algorithms for game tree search. (AE4M36MAS)
  12. Coalitional game formalization and solution concepts, in particular the core and Shapley value. Auction mechanisms and their properties. Social choice theory and voting protocols. (AE4M36MAS)
  13. Cluster analysis, the k-means algorithm, hierarchical clustering, spectral clustering, semi-supervised clustering. (AE4M33SAD)
  14. Frequent itemsets, subsequences and subgraphs. Association rules, the Apriori algorithm. Episodal rules. (AE4M33SAD)
  15. Computational learning theory: capacity of the hypothesis space, PAC-learnability. PAC-learnability of propositional conjunctions, disjunctions, CNF, DNF, decision trees and lists. (AE4M33SAD)
  16. Principles of automatic proving in Boolean domains and in predicate logic (e.g. the DPLL procedure, unification, subsumption, Skolemization, resolution, the tableaux method). (AE4M33AU)
  17. Principles of automatic proving in Boolean domains and in predicate logic (e.g. the DPLL procedure, unification, subsumption, Skolemization, resolution, the tableaux method) (AE4M33AU)
  18. Soundness, completeness, theoretical and practical limits of current proving systems. (AE4M33AU)
  19. Model checking (e.g. SAT, finite automata, timed automata). Practical applications of automatic inference systems, e.g. program verification through formal methods. The TPTP language. (AE4M33AU)

Computer Vision and Image Processing

  1. Image formation and its physical origins. Geometric optics, radiometry. Colour spaces and multispectral images. (AE4M33DZO)
  2. Convolution, correlation, Fourier transform of images. Sampling theorem, image reconstruction, image interpolation, e.g. during geometric transformations. (AE4M33DZO)
  3. Edge detection, Canny and Sobel detectors, scale space. Mathematical morphology, the concepts of image neighbourhood and connectedness, discrete image topology, discrete metrics. (AE4M33DZO)
  4. Image segmentation. Taxonomy of different approaches. Segmentation by thresholding, segmentation based on spatial similarity, segmentation using mathematical morphology, by k-means clustering, by solving optimisation problems (e.g. using the minimal graph cut). (AE4M33DZO)
  5. Compression of image and video, the LZW, JPEG and MPEG methods. (AE4M33DZO)
  6. Detectors of points and regions of interest. Detection algorithms and their sensitivity to geometric and photometric changes in the image. Description of the regions of interest: The method of local frames for ensuring geometrical invariance of the descriptor, The SIFT descriptor (scale invariant feature transform). (AE4M33MPV)
  7. Finding correspondences between images. Hough Transform (HT). The use of HT and RANSAC (Random Sample and Consensus) methods and their use for robust search of geometric transformations between images. Speed and memory requirements of HT and RANSAC methods. (AE4M33MPV)
  8. Object Tracking. Formal description of the problem. Standard algorithms (e.g. Kanade-Lucas tracker). (AE4M33MPV)
  9. Affine and projective plane and space. Representation of points, lines, planes, angles and distances and elementary operations with these entities. (AE4M33GVG)
  10. Mathematical model of a perspective camera. Camera calibration and orientation and the corresponding algorithms. (AE4M33GVG)
  11. 3D scene reconstruction from images. Homography. Epipolar geometry. Computing camera motion from image correspondences. (AE4M33GVG)
  12. Cluster analysis, the k-means algorithm, hierarchical clustering, spectral clustering, semi-supervised clustering. (AE4M33SAD)
  13. Frequent itemsets, subsequences and subgraphs. Association rules, the Apriori algorithm. Episodal rules. (AE4M33SAD)
  14. Computational learning theory: capacity of the hypothesis space, PAC-learnability. PAC-learnability of propositional conjunctions, disjunctions, CNF, DNF, decision trees and lists. (AE4M33SAD)
  15. Basic algorithms involving cameras: Camera resection (six-point algorithm), camera absolute orientation (three-point algorithm), relative orientation of a camera pair (five-point algorithm), computing fundamental matrix (seven-point algorithm), 3D point triangulation from correspondences. Relative positions and orientations in a multi-camera system. Bundle adjustment. Minimal representation of projective camera matrix. Radial distortion models. (AE4M33TDV, AE4M33GVG)
  16. The sparse (wide-baseline) matching problem. Algebraic and geometric error and their properties. Sampson error approximation. The concept of a robust error and its optimization by random sampling. (AE4M33TDV)
  17. Epipolar rectification for stereoscopic vision. Disparity map and the uniqueness and ordering constraints. Formulation of the stereoscopic matching problem and basic algorithms. (AE4M33TDV)
  18. Photometric stereo. Computing the reflectance map and the needle (normal vector) map for a Lambertian surface from three illuminations. (AE4M33TDV)
  19. Convex set, convex hull of a set (definitions). Representation of convex hull in 2D. Its computation from a set of points: Graham's Algorithm, Jarvis' Algorithm of 'gift wrapping', the Divide and Conquer method. Computation of convex hull for a simple polygon. Computation and representation of convex hull in 3D. (AE4M39VG)
  20. Point location in a polygon and in a planar subdivision (the method of slabs, the tree of monotonous chains). Representation of planar subdivision (DCEL), computation of intersections of planar subdivisions (intersection, union, difference) by modified Plane-Sweep algorithm for intersections of a set of line segments. (AE4M39VG)
  21. The proximity problem and Voronoi Diagram. Finding the nearest neighbour of a given point and finding all nearest neighbours in a set of points. Finding the nearest point from a set to a point outside of the set. (AE4M39VG)
  22. Orthogonal search, K-D tree, range tree, segments tree in computational geometry. (AE4M39VG)
Responsible person: prof. Ing. Jiří Jakovenko, Ph.D.