 Machine-translated page for increased accessibility for English questioners.

# INF questions

### Single-disciplinary curriculum

Theoretical foundations of informatics and mathematics

1. Linear algebra. Operation with vectors and matrices, properties of linear operations and scalar product. Gauss elimination, determinant. Eigenvalues and vectors, their geometric meaning, inverse matrix, vector subspaces, vector bases, affine transformations. (MB151)
2. Fundamentals of mathematical analysis. Relations and mappings, properties of real functions, polynomials, continuous functions and limits, derivatives, indeterminate and definite integral, geometric meaning. Differential equations and their meaning. (IB000, MB152)
3. Combinatorics and probability. Elementary combinatorics (combination, permutation, variation), solving simple combinatorial problems. Probability, conditional probability (Bayes theorem). (IB000, MB153)
4. Descriptive statistics. Descriptive statistics, mean, median, variance, correlation. Estimates of statistics and their reliability. Distribution functions, distribution of random variables and their examples. (MB153)
5. Elementary number theory. Divisibility, Euclidean algorithm, modular operations, prime and its testing, application of number theory (RSA, DSA, linear and polynomial codes). (MB154)
6. Graphs and their search. Graph types, trees, vertices, oriented graphs, graph representation. Depth and width graph search algorithms and their use. Context components. (IB000, IB002)
7. Graph algorithms. Evaluated graphs, shortest path definitions, minimal graph skeletons, shortest path search algorithms (Dijkstr, Bellman-Ford algorithm) and minimal skeletons in a graph. (IB000, IB002)
8. Tree data structures. Binary search trees, B-trees, red-black trees, heaps, related operations, and their complexity. Typical implementations, examples of use. (IB002)
9. Algorithm design. The divide and rule method, the advantages and disadvantages of using recursion, removing recursion. Explanation of principles and implementation of sorting recursive algorithms. Relation between recursion and mathematical induction. (IB002, IB015)
10. Functional programming. Functional programming paradigm (principle of calculation, reduction step, reduction strategies and their properties, examples). Higher order functions and their use. Unnamed features. Ability of elementary programming in Haskell. (IB015)
11. Regular languages. Chomsky's hierarchy of formal languages. Regular languages, their representations and conversions between them. Variants of finite automata. Nondeterminism and determination of automata. Closure properties of regular languages. (IB005)
12. Context-free languages and their representation. Variants of pushdown automata (acceptance methods, determinism and nondeterminism, extended pushdown automata). Non-deterministic parsing. Closure properties of context-free languages. (IB005)
13. Decision-making. Concept of algorithmic problem and algorithm. Turing machine and problem of stopping. Decidability and partial decidability, undecidability. Reduction method, diagonalization. (IB107)
14. Complexity. Complexity of algorithm versus problem complexity. Complexity classes (P, NP, PSPACE) and relations between them, examples of problems from individual classes. Difficulty and completeness of the problem in a given class, polynomial reduction of problems, NP-complete problems. (IB107)
15. Principles of Machine Learning. Teaching with a teacher, without a teacher, evaluating the results. Learning decision trees. Lazy learning, method to nearest neighbors. (naive) Bayesian classifier. Anomaly Detection. (IB031)
16. Machine Learning Methods. Linear regression, least squares method, support vectors method (SVM). Hierarchical clustering, k-means algorithm. (IB031)
17. Neural networks. Model of artificial neuron, transfer function. Multilayer network and backward promotion. Limits of using neural networks. (IB031, PB016)
18. Artificial Intelligence. Definition of artificial intelligence, Turing test. State space search - uninformed and heuristic. Constraint problems. Games and basic game strategies in artificial intelligence (minimax, alpha-beta, evaluation functions). (PB016)
19. Mathematical logic. Propositional logic, predicate logic, intensional logic. Satisfiability, truthfulness, provability. Evidence methods, resolution method. Representation and deduction of knowledge. (PB016)
Program, computing and information systems

1. Program runtime and control. Subprograms, name ranges, value passing, exceptions, event-driven programming. Object-oriented programming. Encapsulation, inheritance, polymorphism - principles, usage and implementation. Realization in C #, C ++ or Java (of your choice). (PB006)
2. Principles of low-level programming. Program memory model; memory management, dynamic allocation, work with user data structures. Low-level memory handling, pointer, array and pointer arithmetic. Debugging methods. (PB071)
3. Architecture. Numerical systems, relations between systems, displaying an integer in a computer, arithmetic. Codes, internal, external, detection and correction. Circuits and memories: parameters, architecture. Processor, programming, microprogramming. Architectures: RISC / CISC, buffers. (PB150)
4. Database. Relational model of data, relational scheme, key of relational schemes, relational algebra (projection, selection, aggregation, renaming), connection of relations. Functional dependencies, normal forms (1NF, 2NF, 3NF, Boyce-Codd NF), relationships between normal forms. Decomposition of relational schemes, schema normalization. (PB154)
5. SQL, transaction and query processing. Command syntax and semantics. Data query and update commands, aggregation functions, triggers and stored procedures, data definition, integrity constraints. Transaction processing, its properties. Basic principles of query evaluation (cost of query evaluation, use of indexing and hashing). (PB154)
6. Operating system. Operating system architecture, kernel architecture, basic processor modes. Programming interface, library. User, access rights, virtualization. Virtual memory, process and page tables. Fiber, fiber and process planning. Concurrency, deadlock, resource allocation. Process creation and program execution on POSIX systems, copy-on-write. (PB152)
7. File systems. Block device, block layer, I / O scheduler, RAID, disk encryption. Ordinary files, free space allocation, fragmentation. Directory structure and its representation on disk. Memory-mapped input and output. (PB152)
8. Networking. Computer network layer models (ISO / OSI, TCP / IP): layer functionality and interoperability, addressing. Physical layer, signals and their coding, media access control. Interconnection of computer networks. Network protocols, switching and routing, multicast. Secure data transfer, assemble and end connections. Transport protocols. (PB156)
9. Network applications and security. Basic application protocols: mail delivery, file transfer, web, name service. Principles of description and quality assurance, use for multimedia. Security of network communication, authentication and encryption, security on individual protocol layers. (PB156)
10. Basics of information security. Basic security functions and their security - confidentiality, integrity, availability, undeniable origin. Cryptographic primitives, protocols. Risk management, audit, security operations, standards, security assessment. (PV080)
11. Information security. Identity and Access Management. Privacy - concepts and methods. Network Attacks. Safe programming and SW development. Applicable safety. (PV080)

### Major Study Plan

Theoretical foundations of informatics and mathematics
• Questions 1 to 14 from a single-subject study plan.
Program, computing and information systems
• Questions 1 to 11 from a single-subject study plan.

### Minor Study Plan

Theoretical foundations of informatics

1. Propositional logic. Syntax, semantics, derivation system of propositional logic, proofs in propositional logic, truthfulness and provability of logic formulas. (IB000)
2. Functions and recursion. Recursive function definitions, recursive data types (lists, trees), functions over recursive data types. (IB114)
3. Data structures and their implementation. Abstract data types: list, array, stack, queue, binary tree, generic tree, search tree. Implementation of binary and search trees and operations over them. (IB113, IB114)
4. Graphs. Graph types, trees, vertices, oriented graphs, graph representation. Depth and width graph search algorithms and their use. Context components. (IB114)
5. Sorting. Basic algorithms, algorithms for sorting by heap, merging, splitting. (IB114)
6. Regular languages. Regular languages, regular grammars, regular expressions, finite automata. Properties of regular languages, relation between finite automata and regular grammars. (IB110)
7. Finite automata. Definition, finite automaton construction, finite automaton minimization, nondeterministic finite automaton to deterministic automaton. (IB110)
8. Computability. Turing machine as a universal computational model. Stop problem. Decidability and partial decidability, undecidability. Diagonalization. (IB110)
9. Complexity. Complexity of algorithm versus problem complexity. Complexity classes (P, NP, PSPACE) and relations between them, examples of problems from individual classes. Difficulty and completeness of the problem in a given class, polynomial reduction of problems, NP-complete problems. (IB110)
Program, computing and information systems

1. Computational systems I. Numerical systems, relations between systems, display of integer in computer, arithmetic. Codes, internal, external, detection and correction. Processors, their parameters and architectures. (PB150)
2. Programming. Structured programming in imperative language, data and control structures of programming languages, data types, procedures and functions, block and modular structure of a program. (IB113).
3. Operating system. Operating system architectures, operating system interfaces. Processes, process synchronization, deadlocks, and deadlock protection methods. Working with memory, logical and physical address space, memory management and its execution. Planning on operating systems. (PB153)
4. Computer networks. Topology, access methods and computer network architectures (Ethernet, Fast Ethernet, Token-ring, ATM, etc.). Wireless communication technology. OSI model. TCP / IP. Interconnection of computer networks and routing of information. (PB156)
5. Database I. Relational model, relational scheme, relational schema keys, integrity constraints, relational algebra, relation joining. (PB168)
6. Database II. SQL Query Language (select statement, relation join, aggregate function). Query Processing. Basic principles, example. Indexing. Transaction. Transaction processing properties.
7. Software Engineering. Software development. Requirements specification, system analysis and design, testing, verification and validation, system operation. UML usage in software development. (PB007)