Compulsory Topics (BIE21)

topics are valid since SFE in June 2024

Label	Topic	Course
BIE-SPOL.21-1	Regular languages: Deterministic and nondeterministic finite automata. Determinization of a finite automaton. Minimization of a deterministic finite automaton. Operations on ﬁnite automata. Regular grammars, expressions, and equations.	BIE-AAG.21
BIE-SPOL.21-2	Context-free languages, context-free grammars, pushdown automata and its variants. Models of parsing of context-free languages.	BIE-AAG.21
BIE-SPOL.21-3	Basic notions of graph theory. Graph algorithms: breadth-first search, connected components, topological sort, distances in graphs, and algorithms for minimum spanning tree construction and shortest paths in edge-weighted graphs.	BIE-AG1.21
BIE-SPOL.21-4	Binary heaps, binomial heaps. Binary search trees and their balancing. Hashing.	BIE-AG1.21
BIE-SPOL.21-5	Relational databases and relational algebra as a query language. The SQL language (SELECT, DDL, DML, DCL, TCL). Declaration of integrity constraints in DDL.	BIE-DBS.21
BIE-SPOL.21-6	Trasactions and their properties – ACID.	BIE-DBS.21
BIE-SPOL.21-7	Propositional logic, formulas and their satisfiability, logical equivalence and consequence. Universal systems of connectives, disjunctive and conjunctive normal forms, full forms.	BIE-DML.21
BIE-SPOL.21-8	Fundamentals of number theory, divisibility, EEA and Diophantine equations, prime numbers. Modular arithmetic, Fermat’s little theorem, Euler’s theorem. Linear congruences, Chinese remainder theorem.	BIE-DML.21
BIE-SPOL.21-9	Asymmetric cryptosystems (RSA encryption, Diffie-Hellman, RSA digital signature), hash functions (SHA2, HMAC), digital signature. Certificates, certification authorities.	BIE-KAB.21
BIE-SPOL.21-10	Symmetric ciphers - block and stream, basic properties, operation modes of block ciphers (description and vulnerabilities).	BIE-KAB.21
BIE-SPOL.21-11	Systems of linear equations: Frobenius theorem and related notions, properies and characterization of sets of solutions, Gauss elimination method.	BIE-LA1.21
BIE-SPOL.21-12	Matrices: matrix-matrix multiplication, regular matrices, inverse matrices and their calculation, matrix eigenvalues and their calculation, matrix diagonalisation.	BIE-LA1.21
BIE-SPOL.21-13	Limit of a sequence, limit and continuity of a real-valued functions of one real variable, methods of computation of a limits, asymptotic behavior of functions and sequences (lower, upper, and tight asymptotic bounds, asymptotic equivalence).	BIE-MA1.21
BIE-SPOL.21-14	Differential calculus of a real-valued functions of one real variable: derivative and its geometric meaning, relation of derivatives and monotonicity and convexity, local extrema of real-valued functions of one real variable, asymptotes of a function.	BIE-MA1.21
BIE-SPOL.21-15	Integral calculus of real-valued functions of one real variable (indefinite integral, Riemann definite integral, methods of integration by parts and substitution), real number series and criteria of their convergence.	BIE-MA2.21
BIE-SPOL.21-16	Multivariate functions: differential calculus of multivariate functions (limit, partial derivative, total derivative, gradient, Hessian matrix), types of definitiness of a matrix, necessary conditions and sufficient conditions for existence of local extrema of multivariate functions (without constraints).	BIE-MA2.21
BIE-SPOL.21-17	Processes and threads, their implementation, mechanisms for thead synchronization. Classical synchronization problems. Thread deadlocks, allocation of resources, Coffman’s conditions, strategies of handling deadlocks.	BIE-OSY.21
BIE-SPOL.21-18	Virtualization of main memory by paging, principles of logical-to-physical address translation, structure of page tables, page replacement algorithms.	BIE-OSY.21
BIE-SPOL.21-19	Data types in programming languages. Statically and dynamically allocated variables, linked lists. Modular programming, procedures and functions, input and output parameters. Compiler, linker, debugger.	BIE-PA1.21
BIE-SPOL.21-20	Time and space complexity. Algorithms for searching in number sequences (sequential, interval halving), merging and sorting (BubbleSort, SelectSort, InsertSort, MergeSort, QuickSort). Lower bound for sorting in the comparison model. Sorting in linear time.	BIE-PA1.21 + BIE-AG1.21
BIE-SPOL.21-21	Recursive decomposition of a problem to subproblems using the Divide-and-Conquer method. Recursion vs. iteration. Dynamic programming.	BIE-PA1.21 + BIE-AG1.21
BIE-SPOL.21-22	Object-oriented programming in C ++, encapsulation, inheritance, instance and static attributes and methods, virtual methods, polymorphism, abstract classes, exceptions, templates, operator overloading, shallow and deep copy.	BIE-PA2.21
BIE-SPOL.21-23	Abstract data types, specification and implementation. Stack, queue, array, list, table, and set. Implementation using linked structures, trees, and arrays.	BIE-PA2.21
BIE-SPOL.21-24	ISO/OSI model, data encapsulation and decapsulation, IP addressing principle. Link layer, sublayers LLC and MAC, devices, switching principle. Virtual networks (VLANs). Network layer, routers, routing principle, protocols IPv4 and IPv6, static and dynamic routing.	BIE-PSI.21
BIE-SPOL.21-25	Transport layer, protocol TCP, packet delivery reliability, congestion, comparison with protocol UDP. Network address translation (NAT) at the network layer and at the transport layer. Domain Name System (DNS).	BIE-PSI.21
BIE-SPOL.21-26	Rules for calculating probabilities, Bayes' formula. Random variables, common examples of distributions, cumulative distribution function, probability density function, moments. Independence of events and random variables. Central limit theorem, laws of large numbers.	BIE-PST.21
BIE-SPOL.21-27	Basics of mathematical statistics, random samples, point estimates of the expectation and variance, interval estimates for the expectation, testing of statistical hypotheses regarding the expectation.	BIE-PST.21
BIE-SPOL.21-28	Combinational and sequential logic circuits (Mealy, Moore), their specification and implementation at the gate level. Logic function minimisation using map representations.	BIE-SAP.21
BIE-SPOL.21-29	Architecture of a digital computer, instruction cycle, basic types of the instruction set architectures (ISA). Computer memory subsystem, memory hierarchy, cache memory.	BIE-SAP.21
BIE-SPOL.21-30	Representation of signed numbers and implementation of arithmetic operations (parallel adders/subtractors, arithmetic shifters, decoders, multiplexors, counters). Floating point number representations.	BIE-SAP.21

Label

Topic

Course

BIE-SPOL.21-1

Regular languages: Deterministic and nondeterministic finite automata. Determinization of a finite automaton. Minimization of a deterministic finite automaton. Operations on ﬁnite automata. Regular grammars, expressions, and equations.

BIE-AAG.21

BIE-SPOL.21-2

Context-free languages, context-free grammars, pushdown automata and its variants. Models of parsing of context-free languages.

BIE-AAG.21

BIE-SPOL.21-3

Basic notions of graph theory. Graph algorithms: breadth-first search, connected components, topological sort, distances in graphs, and algorithms for minimum spanning tree construction and shortest paths in edge-weighted graphs.

BIE-AG1.21

BIE-SPOL.21-4

Binary heaps, binomial heaps. Binary search trees and their balancing. Hashing.

BIE-AG1.21

BIE-SPOL.21-5

Relational databases and relational algebra as a query language. The SQL language (SELECT, DDL, DML, DCL, TCL). Declaration of integrity constraints in DDL.

BIE-DBS.21

BIE-SPOL.21-6

Trasactions and their properties – ACID.

BIE-DBS.21

BIE-SPOL.21-7

Propositional logic, formulas and their satisfiability, logical equivalence and consequence. Universal systems of connectives, disjunctive and conjunctive normal forms, full forms.

BIE-DML.21

BIE-SPOL.21-8

Fundamentals of number theory, divisibility, EEA and Diophantine equations, prime numbers. Modular arithmetic, Fermat’s little theorem, Euler’s theorem. Linear congruences, Chinese remainder theorem.

BIE-DML.21

BIE-SPOL.21-9

Asymmetric cryptosystems (RSA encryption, Diffie-Hellman, RSA digital signature), hash functions (SHA2, HMAC), digital signature. Certificates, certification authorities.

BIE-KAB.21

BIE-SPOL.21-10

Symmetric ciphers - block and stream, basic properties, operation modes of block ciphers (description and vulnerabilities).

BIE-KAB.21

BIE-SPOL.21-11

Systems of linear equations: Frobenius theorem and related notions, properies and characterization of sets of solutions, Gauss elimination method.

BIE-LA1.21

BIE-SPOL.21-12

Matrices: matrix-matrix multiplication, regular matrices, inverse matrices and their calculation, matrix eigenvalues and their calculation, matrix diagonalisation.

BIE-LA1.21

BIE-SPOL.21-13

Limit of a sequence, limit and continuity of a real-valued functions of one real variable, methods of computation of a limits, asymptotic behavior of functions and sequences (lower, upper, and tight asymptotic bounds, asymptotic equivalence).

BIE-MA1.21

BIE-SPOL.21-14

Differential calculus of a real-valued functions of one real variable: derivative and its geometric meaning, relation of derivatives and monotonicity and convexity, local extrema of real-valued functions of one real variable, asymptotes of a function.

BIE-MA1.21

BIE-SPOL.21-15

Integral calculus of real-valued functions of one real variable (indefinite integral, Riemann definite integral, methods of integration by parts and substitution), real number series and criteria of their convergence.

BIE-MA2.21

BIE-SPOL.21-16

Multivariate functions: differential calculus of multivariate functions (limit, partial derivative, total derivative, gradient, Hessian matrix), types of definitiness of a matrix, necessary conditions and sufficient conditions for existence of local extrema of multivariate functions (without constraints).

BIE-MA2.21

BIE-SPOL.21-17

Processes and threads, their implementation, mechanisms for thead synchronization. Classical synchronization problems. Thread deadlocks, allocation of resources, Coffman’s conditions, strategies of handling deadlocks.

BIE-OSY.21

BIE-SPOL.21-18

Virtualization of main memory by paging, principles of logical-to-physical address translation, structure of page tables, page replacement algorithms.

BIE-OSY.21

BIE-SPOL.21-19

Data types in programming languages. Statically and dynamically allocated variables, linked lists. Modular programming, procedures and functions, input and output parameters. Compiler, linker, debugger.

BIE-PA1.21

BIE-SPOL.21-20

Time and space complexity. Algorithms for searching in number sequences (sequential, interval halving), merging and sorting (BubbleSort, SelectSort, InsertSort, MergeSort, QuickSort). Lower bound for sorting in the comparison model. Sorting in linear time.

BIE-PA1.21 + BIE-AG1.21

BIE-SPOL.21-21

Recursive decomposition of a problem to subproblems using the Divide-and-Conquer method. Recursion vs. iteration. Dynamic programming.

BIE-PA1.21 + BIE-AG1.21

BIE-SPOL.21-22

Object-oriented programming in C ++, encapsulation, inheritance, instance and static attributes and methods, virtual methods, polymorphism, abstract classes, exceptions, templates, operator overloading, shallow and deep copy.

BIE-PA2.21

BIE-SPOL.21-23

Abstract data types, specification and implementation. Stack, queue, array, list, table, and set. Implementation using linked structures, trees, and arrays.

BIE-PA2.21

BIE-SPOL.21-24

ISO/OSI model, data encapsulation and decapsulation, IP addressing principle. Link layer, sublayers LLC and MAC, devices, switching principle. Virtual networks (VLANs). Network layer, routers, routing principle, protocols IPv4 and IPv6, static and dynamic routing.

BIE-PSI.21

BIE-SPOL.21-25

Transport layer, protocol TCP, packet delivery reliability, congestion, comparison with protocol UDP. Network address translation (NAT) at the network layer and at the transport layer. Domain Name System (DNS).

BIE-PSI.21

BIE-SPOL.21-26

Rules for calculating probabilities, Bayes' formula. Random variables, common examples of distributions, cumulative distribution function, probability density function, moments. Independence of events and random variables. Central limit theorem, laws of large numbers.

BIE-PST.21

BIE-SPOL.21-27

Basics of mathematical statistics, random samples, point estimates of the expectation and variance, interval estimates for the expectation, testing of statistical hypotheses regarding the expectation.

BIE-PST.21

BIE-SPOL.21-28

Combinational and sequential logic circuits (Mealy, Moore), their specification and implementation at the gate level. Logic function minimisation using map representations.

BIE-SAP.21

BIE-SPOL.21-29

Architecture of a digital computer, instruction cycle, basic types of the instruction set architectures (ISA). Computer memory subsystem, memory hierarchy, cache memory.

BIE-SAP.21

BIE-SPOL.21-30

Representation of signed numbers and implementation of arithmetic operations (parallel adders/subtractors, arithmetic shifters, decoders, multiplexors, counters). Floating point number representations.

BIE-SAP.21

📄 The table is available also in CSV (semicolon-separated values). 🔙 History of changes is on GitLab.