# Topics for Master degree state examinations - Open Informatics

## Common part

- 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)
- Amortised complexity. Priority queues, heaps (binary, d-regular, binomial, Fibonacci), operations on them and their complexities. (AE4M33PAL)
- 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)
- Search trees: B, B+, R-B, 2-3-4, Splay and their usage in practice. High dimensional search problem, K-D trees. (AE4M33PAL)
- Algorithm, algorithmic correctness, algorithmic complexity, problem complexity, order of P, order of NP. (AE4M01TAL)
- NP-complete and NP-hard problems, Cook's theorem, heuristics for the solution of NP-hard problems, probabilistic algorithms. (AE4M01TAL)
- Turing machines, recursive and recursively enumerable languages, decidability, undecidability, problems algorithmically unsolvable. (AE4M01TAL)
- 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)
- Shortest paths. The travelling salesman problem. Heuristics and approximation algorithms. Dynamic programming. The knapsack problem. Pseudo-polynomial algorithms. (AE4M35KO)
- Timetabling on a single processor and on parallel processors. Timetabling a project with time limits. Programming with restrictive conditions.(AE4M35KO)

## Artificial Intelligence

- Ontology - purpose, types of elements, relation to other representation frameworks. Ontology languages - goal, examples of languages and their use. (AE4M33RZN)
- Representing uncertainty: modal logic, graphical probability models and inference in them. (AE4M33RZN)
- Representation of vague statements using fuzzy sets. Basic operations in fuzzy logic. (AE4M33RZN)
- 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)
- Planning graphs definition and usage, incl. mutexes. Heuristic search, relaxation and abstraction. (AE4M36PAH)
- Robot motion planning, configuration space and road maps, randomized sampling methods. Hierarchical planning - problem representation, methods and planning process. (AE4M36PAH)
- 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)
- Multi-objective evolution algorithms. Pareto domination principle. Algorithms Non-Dominated Sorting Genetic Algorithm (NSGA) and Strength Pareto Evolutionary Algorithm (SPEA) and their differences. (AE4M33BIA)
- Supervised and unsupervised artificial neural network learning. Perceptrons and RBF neurons. Summarize neural network paradigms and their application areas. (AE4M33BIA)
- Formal concept of autonomous agents and multiagent systems. Agent control architectures, BDI architectures. Distributed problem solving, distributed constraint satisfaction and optimization algorithm. (AE4M36MAS)
- 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)
- 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)
- Cluster analysis, the k-means algorithm, hierarchical clustering, spectral clustering, semi-supervised clustering. (AE4M33SAD)
- Frequent itemsets, subsequences and subgraphs. Association rules, the Apriori algorithm. Episodal rules. (AE4M33SAD)
- Computational learning theory: capacity of the hypothesis space, PAC-learnability. PAC-learnability of propositional conjunctions, disjunctions, CNF, DNF, decision trees and lists. (AE4M33SAD)
- Principles of automatic proving in Boolean domains and in predicate logic (e.g. the DPLL procedure, unification, subsumption, Skolemization, resolution, the tableaux method). (AE4M33AU)
- Principles of automatic proving in Boolean domains and in predicate logic (e.g. the DPLL procedure, unification, subsumption, Skolemization, resolution, the tableaux method) (AE4M33AU)
- Soundness, completeness, theoretical and practical limits of current proving systems. (AE4M33AU)
- 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

- Image formation and its physical origins. Geometric optics, radiometry. Colour spaces and multispectral images. (AE4M33DZO)
- Convolution, correlation, Fourier transform of images. Sampling theorem, image reconstruction, image interpolation, e.g. during geometric transformations. (AE4M33DZO)
- Edge detection, Canny and Sobel detectors, scale space. Mathematical morphology, the concepts of image neighbourhood and connectedness, discrete image topology, discrete metrics. (AE4M33DZO)
- 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)
- Compression of image and video, the LZW, JPEG and MPEG methods. (AE4M33DZO)
- 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)
- 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)
- Object Tracking. Formal description of the problem. Standard algorithms (e.g. Kanade-Lucas tracker). (AE4M33MPV)
- Affine and projective plane and space. Representation of points, lines, planes, angles and distances and elementary operations with these entities. (AE4M33GVG)
- Mathematical model of a perspective camera. Camera calibration and orientation and the corresponding algorithms. (AE4M33GVG)
- 3D scene reconstruction from images. Homography. Epipolar geometry. Computing camera motion from image correspondences. (AE4M33GVG)
- Cluster analysis, the k-means algorithm, hierarchical clustering, spectral clustering, semi-supervised clustering. (AE4M33SAD)
- Frequent itemsets, subsequences and subgraphs. Association rules, the Apriori algorithm. Episodal rules. (AE4M33SAD)
- Computational learning theory: capacity of the hypothesis space, PAC-learnability. PAC-learnability of propositional conjunctions, disjunctions, CNF, DNF, decision trees and lists. (AE4M33SAD)
- 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)
- 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)
- Epipolar rectification for stereoscopic vision. Disparity map and the uniqueness and ordering constraints. Formulation of the stereoscopic matching problem and basic algorithms. (AE4M33TDV)
- Photometric stereo. Computing the reflectance map and the needle (normal vector) map for a Lambertian surface from three illuminations. (AE4M33TDV)
- 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)
- 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)
- 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)
- Orthogonal search, K-D tree, range tree, segments tree in computational geometry. (AE4M39VG)

# Topics for Master degree state examination Open Informatics, accreditation 2016

## Common part

- Polynomial algorithms for standard graph problems. Combinatorial and numerical theoretical algorithms, isomorphism, prime numbers. Search trees and their use. Text search based on finite automata. AE4M33PAL
- Problem/language complexity classes with respect to the time complexity of their solution and memory complexity including undecidable problems/languages.AE4M01TAL
- Combinatorial optimization problems including description of applications, problem formulation, complexity analysis and solving algorithms. AE4M35KO

## Artificial Intelligence

- Learnability models: PAC and online. Learnability of conjunctions and disjunctions. Bayesian networks. Reinforcement learning. BE4M36SMU
- Resolution in the first order logic, automatic proving. Principles of automatic proving in Boolean domains and in predicate logic. Searching for models in generic domains. BE4M36LUP
- Minimizing empirical risk. Maximum likelihood estimation, EM algorithm. Deep networks and their learning. Classical and deep neural networks and their learning. BE4M33SSU
- Domain independent planning. Features, heuristics and algorithms. BE4M36PUI
- Autonomous agents and multiagent systems. Noncooperative game theory. BE4M36MAS
- Decision making, planning and coordination of autonomous systems of one or more robots. BE4M36UIR

## Computer graphics

- Raster graphic. 3D objects and 3D scenes, transformations. Visibility, local illumination methods, shading and shadows. Radiometry, global illumination methods, texturing. B4M39APG
- Data structures for searching in multidimensional spaces. B4M39DPG
- Methods of 3D object representation and their animation. Tools to support the production process.B4M39MMA
- Basic datastructures for computational geometry, their representation and algorithms. B4M39VG
- Scientific visualization methods. Information visualization methods. B4M39VIZ
- Spatial geometry, image projection and perspective camera model for 3D reconstruction, virtual reality, visual odometry and SLAM. B4M33GVG

## Human-Computer Interaction

- Scientific visualization methods. Information visualization methods. B4M39VIZ
- A formal description of user interfaces. Models of human behavior in relation to user interaction. Formal evaluation and prototyping. B4M39NUR
- User research and its role in HCI. Cognitive psychological concepts and their usage in HCI. B4M39PUR1
- Statistical analysis, models and their assessment. Dimensionality reduction. Clustering. B4M36SAN
- Principles of shape psychology. Essential composition and form principles. B4M39PTV
- The methodology of software testing. Methods for test creation from the application model. Automated testing. B4M36ZKS

## Software Engineering

- The methodology of software testing. Methods for test creation from the application model. Automated testing. B4M36ZKS
- Software architectures, their parameters and qualitative metrics. Architectural patterns, styles and standards. B4M36SWA
- Properties of parallel and distributed algorithms. Communication operations for parallel algorithms. Parallel algorithms for linear algebra.. B4M35PAG
- Effective algorithms and optimization methods. Data structures, synchronization and multithreaded programs. . B4M36ESW
- Big Data concept, basic principles of distributed data processing, types and properties of NoSQL databases. B4M36DS2
- Security analysis of operating systems, development of secure software and web applications security. Analysis of cyberattacks and malware. Security of mobile devices. B4M36BSY

## Computer Vision and Digital Image

- Basic datastructures for computational geometry, their representation and algorithms. B4M39VG
- Image representation for computer vision. Segmentation and image preprocessing methods. B4M33DZO
- Object detection in images. Image matching and correspondence search. B4M33MPV
- Spatial geometry, image projection and perspective camera model for 3D reconstruction, virtual reality, visual odometry and SLAM. B4M33GVG
- Algorithms for 3D geometric model reconstruction from images. A4M33TDV
- Minimizing empirical risk. Maximum likelihood estimation, EM algorithm. Deep networks and their learning. Classical and deep neural networks and their learning. BE4M33SSU

## Data Science

- Statistical analysis, models and their assessment. Dimensionality reduction. Clustering. B4M36SAN
- Scientific visualization methods. Information visualization methods. B4M39VIZ
- Ontologies. Basic principles of ontological engineering, semantic web technologies, basic principles and technologies of linked data. B4M33OSW
- Minimizing empirical risk. Maximum likelihood estimation, EM algorithm. Deep networks and their learning. Classical and deep neural networks and their learning. BE4M33SSU
- Learnability models: PAC and online. Learnability of conjunctions and disjunctions. Bayesian networks. Reinforcement learning. BE4M36SMU
- Big Data concept, basic principles of distributed data processing, types and properties of NoSQL databases. B4M36DS2

## Cyber Security

- Statistical analysis, models and their assessment. Dimensionality reduction. Clustering. B4M36SAN
- The methodology of software testing. Methods for test creation from the application model. Automated testing. B4M36ZKS
- Security analysis of operating systems, development of secure software and web applications security. Analysis of cyberattacks and malware. Security of mobile devices. B4M36BSY
- Symmetric and asymmetric cryptography. Basic cryptosystems (RSA, El-Gamal). Number factorisation. Hashing algorithms. B4M01MKR
- Network routing principles. Network transport protocols. Software defined networks. Network function virtualization.. A0M32PST
- Principles of secure system design. Design and analysis of secure communication protocols, e.g. TLS, mobile telephony and others. Distributed system security. B4M36KBE

## Computer Engineering

- Design and implementation of in-chip integrated systems, application specific systems. B4M34ISC
- Advanced architectures of processors, memory and peripheral circuits and multiprocessor computers. B4M35PAP
- I/O and network interfaces of computer and embedded systems, hardware and software implementation. B4M38KRP
- ARM based microcontrollers and signal processors; their functionality. Design and implementation of embedded systems for typical application areas. B4M38AVS
- Parallel and distributed algorithms. Communication within parallel algorithms. Parallel algorithms for linear algebra. B4M35PAG
- Efficient algorithms and their optimization. Data structures, synchronization and multi-thread programming. B4M36ESW

## Bioinformatics

- Chemical composition of living matter, experimental models and methods, genetic code. B4M36MBG
- Modeling and analysis of biological sequences. B4M36BIN
- Image representation for computer vision. Segmentation and image preprocessing methods. B4M33DZO
- Statistical analysis, models and their assessment. Dimensionality reduction. Clustering. B4M36SAN
- Learnability models: PAC and online. Learnability of conjunctions and disjunctions. Bayesian networks. Reinforcement learning. BE4M36SMU