B-INF Informatics questions

Single-subject curriculum

1. Linear Algebra. Operations with vectors and matrices, properties of linear operations and scalar product. Gaussian elimination, determinant. Eigenvalues and vectors, their geometric meaning, inverse matrices, vector subspaces, vector bases, linear transformations.
2. Fundamentals of mathematical analysis. Solution and representation, properties of real functions, polynomials, continuous functions and limits, derivatives, indefinite and definite integral, geometric meaning. Differential calculus. (IB000, MB152)
3. Combinatorics and probability. Elementary combinatorics (combinations, permutations, variations), solving simple combinatorial problems. Probability, conditional probability (Bayes' theorem). ( IB000, MB153)
4. Descriptive statistics. Descriptive statistics, mean, median, variance, correlation. Estimation of statistics and their reliability. Distribution functions, distribution of random variables and examples. (MB153)
5. Elementary number theory. Divisibility, Euclidean algorithm, modular operations, prime number and its testing, applications of number theory (RSA, DSA, linear and polynomial codes).
6. Graphs and their search. Graph types, trees, vertex degrees, oriented graphs, graph representations. Algorithms for graph search in depth and breadth and their use. Components of context. (IB000, IB002)
7. Graph algorithms. Evaluated graphs, definition of shortest paths, minimal skeletons of a graph, algorithms for finding shortest paths (Dijkstra, Bellman-Ford algorithm) and minimal skeletons in a graph.
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. Design of algorithms. Divide and conquer, advantages and disadvantages of using recursion, elimination of recursion. Explanation of the principles and implementation of ranked recursive algorithms. Relationship between recursion and mathematical induction. (IB002, IB015)
10. Functional programming. Functional programming paradigm (principle of computation, reduction step, reduction strategies and their properties, examples). Higher order functions and their use. Unnamed functions. The 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. Non-determinism and determinism of automata. Closure properties of regular languages. (IB005)
12. Context-free languages and their representations. Variants of stack automata (acceptance methods, determinism and nondeterminism, extended stack automata). Non-deterministic syntactic analysis. Closure properties of context-free languages. (IB005)
13. Determinism. Concept of algorithmic problem and algorithm. Turing machine and halting problem. Decidability and partial decidability, undecidability. Reduction method, diagonalization. (IB107)
14. Complexity. Algorithm complexity versus problem complexity. Complexity classes (P, NP, PSPACE) and relations between them, examples of problems from each class. Difficulty and completeness of a problem in a given class, polynomial reduction problems, NP-complete problems. (IB107)
15. Principles of machine learning. Learning with teacher, without teacher, evaluation of results. Decision tree learning. The k nearest neighbor method.(naive) Bayesian classifier. Anomaly detection. (IB031)
16. Machine learning methods. Linear regression, least squares method, support vector machine (SVM). Hierarchical clustering, k-means algorithm. (IB031)
17. Neural networks. Artificial neuron model, transfer functions. Multilayer network and back propagation. Limits of 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. Feasibility, truth, provability. Proof methods, resolution method. Knowledge representation and inference. (IB000, PB016)

1. Structuring and control of program execution. Subroutines, name ranges, value passing, exceptions. Object-oriented programming. Encapsulation, inheritance, polymorphism - principles, use and implementation. Implementation in C#, C++ or Java (at your choice). (PB006)
2. Principles of low-level programming. Program memory model; memory management, dynamic allocation, working with user data structures. Low-level memory handling, pointer, array and pointer arithmetic. Debugging methods ( PB071).
3. Architectures. Number systems, relationships between systems, integer representation in the computer, arithmetic. Codes, internal, external, detection and correction. Circuits and memories: parameters, architecture. Processor, programming, microprogramming. Architectures: RISC/CISC, caches. (PB150)
4. Databases. Relational model of data, relational schema, keys of relational schemas, relational algebra (projection, selection, aggregation, renaming), linking of relations. Functional dependencies, normal forms (1NF, 2NF, 3NF, Boyce-Codd NF), relations between normal forms. Decomposition of relational schemas, normalization of schemas. (PB154)
5. SQL, transactions and query processing. Syntax and semantics of statements. Commands for querying and updating data, 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).
6. Operating systems. Operating system architecture, kernel architecture, basic processor modes. Programming interfaces, libraries. User, access rights, virtualization. Virtual memory, process and page tables. Threads, thread and process scheduling. Concurrency, deadlock, resource allocation. Process creation and program execution in 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. Layer models of computer networks (ISO/OSI, TCP/IP): layer functionality and interaction, addressing. Physical layer, signals and their encoding, media access control. Interconnection of computer networks. Network protocols, switching and routing, multicast. Secured data transmission, connection setup and termination. Transport protocols. (PB156)
9. Network applications and security. Basic application protocols: mail delivery, file transfer, web, name service. Principles of service description and quality assurance, application to multimedia. Network communication security, authentication and encryption, security at the protocol layer. (PB156)
10. Fundamentals of information security. Basic security functions and their assurance - confidentiality, integrity, availability, undeniability of origin. Cryptographic primitives, protocols. Risk management, auditing, security operations, standards, security assessment. (PV080)
11. Information security. Identity and access management. Privacy - concepts and methods. Network attacks. Secure programming and software development. Applied security. (PV080)

Curriculum Major

• Questions 1 through 12 from the single-subject curriculum.

• Questions 1 to 11 from the single-subject curriculum.

Minor curriculum

1. Sentential logic. Syntax, semantics, inference system of propositional logic, proofs in propositional logic, truth and provability of logical formulas. (IB000)
2. Functions and recursion. Recursive function definitions, recursive data types (lists, trees), functions over recursive data types.
3. Data structures and their implementation. Abstract data types: list, array, stack, queue, binary tree, general tree, search tree. Implementation of binary and search trees and operations on them. (IB114)
4. Graphs. Graph types, trees, vertex degrees, oriented graphs, graph representations. Algorithms for searching a graph in depth and width and their use. Components of context. (IB114)
5. Classification. Basic algorithms, heap sorting, merging, splitting algorithms. (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. Definitions, construction of finite automata, minimization of finite automata, conversion of nondeterministic finite automata to deterministic automata. (IB110)
8. Enumerability. Turing machine as a universal computational model. The halting problem. Decidability and partial decidability, undecidability. Diagonalization. (IB110)
9. Complexity. Algorithm complexity versus problem complexity. Complexity classes (P, NP, PSPACE) and relationships between them, examples of problems from each class. Difficulty and completeness of a problem in a given class, polynomial reduction problems, NP-complete problems. (IB110)

1. Programming. Structured programming in imperative languages, data and control structures of programming languages, data types, functions. (IB113).
2. Operating systems. Operating system architectures, operating system interfaces. Processes, process synchronization, stuckness and stuckness protection methods. Working with memory, logical and physical address space, memory management and methods of memory management. Scheduling in operating systems. (PB153)
3. Computer networks. Topologies, access methods and architectures of computer networks (Ethernet, Fast Ethernet, Token-ring, ATM, etc.). Wireless communication technologies. OSI model. TCP/IP protocol. Interconnecting computer networks and routing information. (PB156)
4. Database I. Relational model, relational schema, keys of relational schemas, integrity constraints, relational algebra, relational coupling. (PB168)
5. Database II. SQL query language (select statement, relational joins, aggregation functions). Query processing. Basic principles, example. Indexing. Transactions. Features of transaction processing.
6. Software engineering. Software development. Requirements specification, system analysis and design, testing, verification and validation, system operation. Use of UML in software development. (PB007)