PVA questions
Single-subject curriculum
Theoretical Foundations of Computer Science and Mathematics- 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, affine transformations (MB141).
- Basic mathematical analysis. Solution and representation, properties of real functions, polynomials, continuous functions and limits, derivatives, indefinite and definite integral, geometric meaning. Differential calculus. (IB000, MB142)
- Descriptive statistics. Descriptive statistics, mean, median, variance, correlation. Estimation of statistics and their reliability. Distribution functions, distribution of random variables and examples. (MB143)
- Graphs and their search. Types of graphs, trees, degrees of vertices, oriented graphs, graph representations. Algorithms for depth and breadth search of graphs and their applications. Components of context. (IB000, IB002)
- 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.
- Tree data structures. Binary search trees, B-trees, red-black trees, heaps, related operations and their complexity. Typical implementations, examples of use. (IB002)
- 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)
- 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)
- 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. (IB110)
- Determinism. Concept of algorithmic problem and algorithm. Turing machine and halting problem. Decidability and partial decidability, undecidability. Reduction method, diagonalization. (IB110)
- 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. (IB110)
- Structuring and controlling program execution. Subroutines, name ranges, value passing, exceptions, event-driven programming. Object-oriented programming. Encapsulation, inheritance, polymorphism - principles, use and implementation. Implementation in C#, C++ or Java (optional). (PB006)
- 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).
- 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)
- 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)
- 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).
- 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)
- 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)
- 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, link setup and termination. Transport protocols. (PB156)
- 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)
- 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)
- Information security. Identity and access management. Privacy - concepts and methods. Network attacks. Secure programming and software development. Applied security. (PV080)
- Applied Information Systems. Definition of AIS, IS application areas. Architectures of large-scale information systems. Methods of managing large-scale projects. (PV028)
- Digital systems. Theory of data representation and information coding including operations. Algebraic, graphical and algorithmic minimization methods. Optimization based on - delay minimization, logic minimization, testability. Combinational design elements of digital systems - arithmetic circuits, comparators, multiplexers and demultiplexers, encoders and decoders. Sequential circuits - encoding of internal states and its effect on design. Types and properties of flip-flop circuits. Basic sequential design elements of digital systems - registers, counters, comparators, controllers and sequencers. (PV170)
- Parallel systems. Basic methods in the design of parallel algorithms - decomposition, mapping, communication primitives. Performance analysis of parallel algorithms. Parallel algorithms in shared memory environment. OpenMP standard. POSIX Threads. Lock-free access. Parallel algorithms in a distributed memory environment. Message Passing Interface (MPI). (IB109)
- Modern markup languages. Basic standards of the XML family. XML applications for documents and data. Document Object Model (DOM). XML Schema languages. Navigation and querying in XML data (XPath, XQuery). XML transformation (XSLT). (PB138)