# Topics for the Final State Examination of the Bachelor Study Program Open Informatics (accreditation before 2016 - running out)

## Common theoretical part

1. Linear dependence and independence, basis, dimension. Linear projection, kernel and rank, range of values, scalar and vector products. (AE0B01LAG)

2. Matrices, determinant, invertible matrix, eigenvalues and eigenvectors of a matrix. Systems of linear equations. (AE0B01LAG)

3. Integer properties (divibility, primes) and Euclid's algorithm. Binary relations, especially equivalence and ordering, and their representation. Modulo arithmetic. (AE4B01DMA)

4. Combinatorics (combination numbers, the principle of inclusion and exclusion); Application of mathematical induction; recursive relations (solution of equations, estimate of algorithmic complexity). (AE4B01DMA)

5. Imperative programming, software, compiler, interpreter, internal format, programming languages, syntax, semantics, variables, expressions, input, output, control structures, simple data types, alignment, functions, procedures, parameters, problem decomposition, recursion and iteration. (AE0B36PR1)

6. Object oriented approach principles, class as: program unit, source of functions, data type; structure of an object, constructors, type change, instance of a class, class hierarchy, inheritance, composition; abstract classes, polymorphism, interface, interface as a variable type, type interface. (AE0B36PR1)

7. Linked lists, linear lists, general linked structures, trees, their properties, binary trees, implementation. (AE0B36PR1)

8. Limit of a function and a sequence, especially rate of growth at infinity and l'Hopital's rule. Derivatives and partial derivatives: their evaluation and meaning (rate of change, monotonicity, extremas of functions, gradient). (AE4B01MA2)

9. The meaning of an integral, basic methods of evaluation and an indefinite integral; series and their convergence (meaning, examples of use, geometrical series), Taylor's polynomial and series. (AE4B01MA2)

10. Syntax and semantics of propositional and predicate logics. Semantic implication and tautological equivalence. Boolean calculus. Resolution method. (AE0B01LGR)

11. Directed and undirected graphs, connectivity, strong connectivity, trees and skeletons, Euler's graphs, Hamilton's graphs, independent sets, graph colouring. (AE0B01LGR)

12. Programming in JAVA: structure of the classes and program. Events, events source and listener, transmission of events, own events, multiple sources and listeners, sources identification. Exceptions and their processing, exceptions propagation, exceptions hierarchy, controlled and uncontrolled exceptions. (AE0B36PR2)

13. Foundations of C programming, language characteristics, compilation model, program structure, macros, conditional compilation, language syntax, structures, unions, enumerated types, preprocessor, basic libraries, basic input and output, pointers, dynamic memory management, fields and masks, functions and pointers. (AE0B36PR2)

14. Asymptotic time and memory compexity of algorithms, order of growth of functions (AE4B33ALG)

15. Main sorting algorithms (mergesort, quicksort, heapsort, radixsort) and binary search; their complexities. (AE4B33ALG)

16. Data types, list, stack, queue, operations on them, their complexities. Search and decision trees (binary, AVL, B), their specific use, efficiency of operations, choice of hash functions for specific types of data. (AE4B33ALG)

17. Open and closed hash tables, efficiency of operations, choice of hash functions for specific types of data. (AE4B33ALG)

18. Recursion, basic scheme, basic properties, relationship of recursion and iteration, implementation properties, efficiency (AE4B33ALG)

19. Random variable and random vector. Distribution function, density and random variable probability function. The mean and variance of the random variable and their estimation. Joint characteristics of the random vector. Correlation and independence of the random variables. Method of maximum likelihood. Basic principles of statistical hypothesis testing. Markov chains, states classification. (AE0B01PSI)

20. Entropy, mutual entropy and conditional entropy of discrete and continuous partitions, basic properties and meaning. Message coding, Kraft-MacMillan inequality. Relation between entropy and mean length of the codeword. Codes with optimal mean length. Information channel and its capacity. (AE0B01PSI)

21. Deterministic finite automata, language accepted by a finite automaton. (AE4B01JAG)

22. Regular expressions and regular languages, Kleen's theorem. Algorithmic complexity of problems related to regular languages. (AE4B01JAG)

23. Grammars, regular grammars and context-free grammars, context-free languages. Stack automata and their relationship to context-free languages. Properties of context-free grammars, insertion lemma. (AE4B01JAG)

24. Combination logic circuits, hazards. Minimalisation of logic functions. Boolean circuits of computing technology: multiplexors, demultiplexors, decoders, comparators, adders, circuits of speeded up transmission. Programmable logic circuits. (AE0B35SPS)

25. Finite automaton and its minimalisation. Synthesis of asynchronous sequential logical circuits as a combination of circuits with feedback. Structure of basic synchronous flip-flop circuits. Synthesis of sequential logic circuits used in computers. (AE0B35SPS)

26. Fixed and programmable control unit. Microprogram automaton. Classical computer architecture, von Neumann and Harvard architecture. Structure of the CPU, data and address registers, instructions counter, stack pointer, types of instructions. (AE0B35SPS)

27. Structures and hierarchies of memory. Addressing modes. Different widths of the CPU generated addresses (logical addresses) and physical addresses of memory. Mapping, paging, segmentation. Interrupts and exceptions. Sources of interrupts, interrupt vectors. DMA access. (AE0B35SPS)

28. Classical Mechanics - Newtons laws. Kinematics and dynamics of a point mass. Motion equations for inertial and uninertial relationship systems. Work and energy. Conservative force field, mechanical laws of conservation. I. a II. impulse theorems. Rotation motion of a solid body (moment of force, momentum, moment of inertia). Gravitation field and examples of its effects (gravitation law, intensity and potential of the gravitation field, intensity of the gravitation field inside and outside of a homogeneous sphere). Mechanics of an oscillating system. Undamped and dampded mechanical linear oscillator. (AE4B02FYZ)

29. Dynamics of physical systems - basic divisions of dynamical systems, phase portrait, stationary (fixed) body, dynamic flow. Investigation of linear systems stability, topological classification of linear systems (saddle point, stable and unstable spirals, stable and unstable knot, central point), attractor. Investigation of stability of non-linear systems, linearization. (AE4B02FYZ)

30. Computer Architecture. Concepts and techniques of CPU. Comparison of RISC a CISC approaches to processors architectures. Networks of processors and parallel architectures. Hierarchical concept of memories. Interrupt and input-output computer subsytems, control of inputs and outputs. (AE0B36APO)

31. Multilevel computer organisation, virtual machines. Classical register orientated architecture with compete instruction set. Standard system and I/O buses of computer systems. (AE0B36APO)

32. Linear programming (LP). Transforming various forms of LP to one another. Applications of LP. Simplex method. Duality. Convex sets and convex polyhedra. Convex functions. Convex optimization tasks. (AE4B33OPT)

33. Method of least squares. Analytical conditions on local optima of differentiable functions, both unconstrained and equality-constrained (by Lagrange multipliers). Numerical methods for unconstrained optimization (gradient, Newton, Gauss-Newton, Levenberg-Marquardt). (AE4B33OPT)

## Topics for the Branch Computer Science and Informatics

1. Operating system, process, thread, scheduling. Communication between processes and threads, time dependent errors, critical sections, synchronisation primitives, the deadlock problem, possible solutions. Memory management. Virtual memory - paging, algorithms for page eviction, segmentation. File systems, organisation of data in external memory, principles, solutions, protections. (AE4B33OSS)

2. Computer networks, the ISO/OSI hierarchical model. LANs, their topologies, technologies and addressing, interconnecting LANs with internet structures, addressing, routing. IP protocols (UDP, TCP, ICMP) and their applications in specific protocols (HTTP, SMTP, DNS). Network computation, client/server sockets. (AE4B33OSS)

3. Sources of errors in numerical computations, splines, least squares method. (AE4B01NUM)

4. Method for finding roots of functions, fixed point theorem. (AE4B01NUM)

5. Numerical integration, methods of solving differential equations, the effect of the step length. (AE4B01NUM)

6. Basic architecture types of information systems (client-server, multi-tier, thin client). Performance optimization of database systems, B-trees. Data recovery. Replication, system availability. On-line analytical processing. Basic techniques of spatial indexation for DB systems and GIS cooperation. (AE4B33DS)

7. Foundations of data modelling, E-R diagrams, relation model. Integrity restriction, normal forms. SQL basics, referential integrity, aggregation function, inner queries. Transactions, their serialisability, locking, degrees of isolation, transactions deadlock, its prevention and solution. Object-relational mapping, persistence of objects. (AE4B33DS)

8. The basic Lisp evaluation loop. Working with lists in Lisp. Destructive and non-destructive constructs. Lambda calculus, higher order functions, local variables, combining iteration constructs with recursion. Models of rule based programming. (AE4B33FLP)

9. Prolog: facts, rules, variables, functions. Interpretation and model. Queries and their evaluation using resolution and backtracking, decidability, cut, negation, the closed world assumption. (AE4B33FLP)

10. Problem solving using search. Uninformed search. Informed search. A* algorithm. Algorithms for playing two-player games (minimax, alpha/beta pruning). Knowledge representation using rules. (AE4B33ZUI)

11. Knowledge representation and models of reasoning using first order predicate logic. The principle of resolution. Representation of inexact knowledge using Markov models of inexact reasoning. Markov's decision processes. (AE4B33ZUI)

12. The Bayesian decision making problem, i.e. minimisation of expected (mean) loss. Non-bayesian decision problems (Neyman-Pearson, minimax). (AE4B33RPZ)

13. Linear classifiers and their advantages. The Perceptron learning algorithm. (AE4B33RPZ)

14. Classifier training methods Adaboost and SVM (Support Vector Machine). (AE4B33RPZ)

15. The EM (Expectation Maximisation) algorithm. (AE4B33RPZ)

[Otevrena informatika/Open Informatics]