BIE-TI
Computer Science
topics are valid since SFE in June 2020
| Label | Topic | Course |
|---|---|---|
| BIE-TI-1 | Transformations of context free grammars and their normal forms. The CYK algorithm. | BIE-AAG |
| BIE-TI-2 | Implementation of finite automata, lexical analyzer. | BIE-AAG |
| BIE-TI-3 | Higher connectivity of graphs: Vertex and edge k-connectivity, their determination and relations, Menger and Ford-Fulkerson theorem. Bridges, cut vertices and searching for them. Strongly connected components of an oriented graph and searching for them. | BIE-AG2 |
| BIE-TI-4 | Network flows: Network, flow, cut, relationship between flow size and cut capacity, Ford-Fulkerson algorithm. Matching, searching for a maximum matching in a bipartite graph, Hall’s theorem and its consequences. | BIE-AG2 |
| BIE-TI-5 | Planar graphs and graphs coloring: Euler formula. Kuratowski theorem. Chromatic number of a graph, chromatic number of planar graphs. | BIE-AG2 |
| BIE-TI-6 | Advanced data structures: The Fibonacci heaps and complexity of their operations in the worst case. (a, b)-trees. | BIE-AG2 |
| BIE-TI-7 | Eulerian and Hamiltonian graphs: Eulerian trail, Eulerian graphs, minimum coverage by trails. Hamiltonian circle, Chvátal closure, Chvátal’s theorem. | BIE-AG2 |
| BIE-TI-8 | Distances in graphs: Floyd-Warshall algorithm. Traveling Salesperson Problem, definition and an approximation algorithm. | BIE-AG2 |
| BIE-TI-9 | Geometric algorithms: Convex hull of points in plane, determination of angle orientation. The sweep-line technique and fast calculation of intersections of line segments in plane. | BIE-AG2 |
| BIE-TI-10 | Instruction cycle and pipelined instruction processing. Microarchitecture of a scalar processor with instruction pipelining, controlling the flow of instructions between instruction pipeline stages. Data, control, and structural hazards in instruction pipelining and methods to resolve them. | BIE-APS.1 |
| BIE-TI-11 | Memory hierarchy with caches and principle of locality. Working principles of cache memories. Architectures of direct-mapped, fully associative, set-associative cache memories. The role of a cache memory in the instruction cycle and impact of a cache memory on program execution. | BIE-APS.1 |
| BIE-TI-12 | Virtualization of main memory using the technique of paging and its HW support. MMU (Memory Management Unit) and virtual-to-physical address translation using TLB (Translation Lookaside Buffer). | BIE-APS.1 |
| BIE-TI-13 | Principles of cache memory coherence protocols in multicore and multiprocessor systems with shared memory bus. Instructions for synchronization of accesses to shared memory. | BIE-APS.1 |
| BIE-TI-14 | Microarchitecture of superscalar processors, instruction-level parallelism, out-of-order execution, speculative instruction processing, register renaming, static and dynamic branch prediction, load bypassing ad forwarding. | BIE-APS |
| BIE-TI-15 | Linear mapping and matrix of linear mapping: definition and fundamental properties (matrix of composed/inverse mapping, relation between rank of the mapping and rank of its matrix), transition matrix (change of basis). | BIE-LIN |
| BIE-TI-16 | Linear codes: basics of coding theory, generator and check matrices, coding and decoding. | BIE-LIN |
| BIE-TI-17 | OOP abstraction and class hierarchy - packages, classes, fields, methods, constructors, traits, equivalence and identity, superclass, subclass, inheritance, static and dynamic dispatch . | BIE-OOP |
| BIE-TI-18 | OOP polymorphism - subtyping, generics, bounds and variance. | BIE-OOP |
| BIE-TI-19 | OOP error handling and reflection - signalling exceptional state, execeptions, stack trace, total functions, design by contract, object model and dynamic code invocation. | BIE-OOP |
| BIE-TI-20 | Top-down parser, formalisms for its specification – context free grammars, pushdown automata, relationships between them. LL(1) grammars, transformations of grammars. Implementation of LL(1) parser. | BIE-PJP |
| BIE-TI-21 | Formalisms for syntax-directed translation – translation grammars, attribute grammars, attribute translation grammars. LL-attributed translation grammars, implementation by recursive-decent functions with parameters. | BIE-PJP |
| BIE-TI-22 | Intermediate representation of programs, abstract syntax tree, translation of basic constructs of programming languages. | BIE-PJP |
| BIE-TI-23 | Structure of memory in implementations of programming languages: static part, stack, heap. Activation records, mechanism of function calls. | BIE-PPA |
| BIE-TI-24 | Lambda calculus: definition of basic notions, operations, representation of numbers. | BIE-PPA |
| BIE-TI-25 | Functional programming, high-order functions, Lisp: S-expressions, cons cells, functions, recursion, mapping functionals. | BIE-PPA |
| BIE-TI-26 | Logic programming, Prolog: facts, rules, queries, evaluation of queries, unification of queries, unification, cut operator. | BIE-PPA |
| BIE-TI-27 | Linear regression, ridge regression (L2 regularisation). | BIE-VZD |
| BIE-TI-28 | KNN (k nearest neighbors) method, clustering. | BIE-VZD |
| BIE-TI-29 | Decision trees. | BIE-VZD |
| BIE-TI-30 | Logistic regression. | BIE-VZD |
📄 The table is available also in CSV (semicolon-separated values). 🔙 History of changes is on GitLab.