Theoretical Foundations of Computer Science
From the first three following courses, those who have mathematics combined do not take the exam.
- Sets and Sessions (Impressions, Functions, Decompositions, and Equivalences)
- Elementary combinatorics (variations, combinations and permutations)
- Arrangements (arrangement sessions, ordered sets and associations, numerical fields)
- Explained logic (syntax, semantics, derivation system of propositional logic, propositional statements, veracity and veracity of logical formulas, resolution)
- Predicate First Order Logic (syntax, semantics, prenexitation, scholemization, unification, resolution)
- Prolog (SLD-resolutions, SLD-trees, Prolog computational mechanism, basics of Prolog programming)
- Proof of programs (demonstration of program properties, inductive methods, invariants of cycles)
- Recursion (recursive definition of functions, higher order function, partial application, currying, definition of functions recursively and using combinators, definition of higher functions without using formal parameters)
- Expression of expressions (order of evaluation, strict and normal reduction, lazy reduction, efficiency of endless data structure, definition of functions over infinite structures)
- Regular languages (regular languages, ways of their representation, regular language properties, relation between finite automata and regular grammar)
- Finite automata (definition, finite automation construction, minimization of the final automaton, transfer of a non-deterministic finite automaton to a deterministic automaton)
- Context-free languages (definitions, properties, ways of their representation, construction of context-free grammar and stack automaton, normal forms of context-free grammars, use of insertion lemma for context-free languages, closure properties of context-free languages)
- Buffer automata (definitions, transfer of context-free grammar to a slot machine). Syntactic analysis (top-down and bottom-to-bottom syntax, analysis of the given word).
- Data structures and their implementation (list, stack, queue, binary tree, common tree, search trees and their modifications, implementation of binary and search trees and operations above them)
- Sorting (basic algorithms, heap sorting algorithms, merging, distribution)
- Graph algorithms (depth and width chart crawling, chart crawl complexity)
Program, information and computing systems
- Computational systems I (numerical systems, relations between numerical systems, display of numbers in computer, principles of arithmetic operations, Boolean, Sheffer and Pierc algebra, combinational and sequential logic circuits).
- Computational Systems II (Processors, their Parameters and Architectures, Intel Architecture, Internal and External Memory and Principles of Their Function, Computer Input and Output Devices, and Their Connection)
- Programming (structured programming in imperative language, data and control structures of programming languages, data types, procedures and functions, block and modular structure of the program)
- Object oriented programming (basic concepts of PPE, encapsulation, inheritance, polymorphism, object programming in imperative language, object collaboration, events controlled by programming, exceptions)
- Operating systems (operating system architectures, operating system interfaces, processes, process synchronization, deadlocks and methods of mismatch) Memory, logical and physical address space, memory management and how to implement it.
- Scheduling in Operating Systems (Process Management and Planning, File Systems, I / O Device Management and Planning)
- Computer Networks (Topology, Access Methods and Computer Network Architectures (Ethernet, Fast Ethernet, Token Ring, ATM, ...) Wireless Communication Technologies, OSI Model, TCP / IP, Computer Networking and Information Routing)
- Database I (relational model, relational schema, relational schema keys, integrity constraints, relational algebra, session combining)
- Database II (Functional dependencies, relational schema keys, Armstrong axioms, relational schema decomposition, normal forms in general, 1NF, 2NF, 3NF, Boyce-Coddova NF, relations between NF, relational schema transfers to NF)
- SQL (command syntax and semantics, built-in functions, triggers, stored procedures, data definition commands, transaction processing, atomic operations, query optimization)
- Fundamentals of data modeling (design of data structures, ER diagrams, entities, attributes, relations, graphical expressions)
prof. RNDr. Jiří Barnat, Ph.D.