Questions B-IVV Informatics in education

Curriculum Minor

1. Propositional 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. (IB113, IB114)
4. Graphs. Graph types, trees, vertex degrees, oriented graphs, graph representations. Algorithms for searching a graph in depth and breadth and their use. Components of context. (IB114)
5. Classification. Basic algorithms, heap sorting, merging, splitting algorithms. (IB114)
6. 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)
7. Determinism. Concept of algorithmic problem and algorithm. Turing machine and halting problem. Decidability and partial decidability, undecidability. Reduction method. (IB110)
8. Complexity. Algorithm complexity versus problem complexity. Complexity classes (P, NP) 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)

1. Computer Systems I. Number systems, relationships between systems, representation of integers in the computer, arithmetic. Codes, internal, external, detection and correction. Processors, their parameters and architectures (PB150).
2. Programming. Structured programming in imperative languages, data and control structures of programming languages, data types, procedures and functions, block and modular program structure. (IB113).
3. Operating systems. Operating system architectures, operating system interfaces. Processes, process synchronization, stuckness and methods of stuckness protection. Memory handling, logical and physical address space, memory management and methods of memory management. Scheduling in operating systems. (PB153)
4. 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)
5. Database I. Relational model, relational schema, keys of relational schemas, integrity constraints, relational algebra, relational coupling. (PB168)
6. Database II. SQL query language (select statement, session joins, aggregation functions). Query processing. Basic principles, example. Indexing. Transactions. Features of transaction processing.
7. Software engineering. Software development. Requirements specification, system analysis and design, testing, verification and validation, system operation. Use of UML in software development. (PB007)