Jdi na navigaci předmětu

BIE-TI

Computer Science

topics are valid since SFE in June 2020

LabelTopicCourse
BIE-TI-1Transformations of context free grammars and their normal forms. The CYK algorithm.BIE-AAG
BIE-TI-2Implementation of finite automata, lexical analyzer.BIE-AAG
BIE-TI-3Higher 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-4Network 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-5Planar graphs and graphs coloring: Euler formula. Kuratowski theorem. Chromatic number of a graph, chromatic number of planar graphs.BIE-AG2
BIE-TI-6Advanced data structures: The Fibonacci heaps and complexity of their operations in the worst case. (a, b)-trees.BIE-AG2
BIE-TI-7Eulerian and Hamiltonian graphs: Eulerian trail, Eulerian graphs, minimum coverage by trails. Hamiltonian circle, Chvátal closure, Chvátal’s theorem.BIE-AG2
BIE-TI-8Distances in graphs: Floyd-Warshall algorithm. Traveling Salesperson Problem, definition and an approximation algorithm.BIE-AG2
BIE-TI-9Geometric 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-10Instruction 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-11Memory 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-12Virtualization 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-13Principles 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-14Microarchitecture 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-15Linear 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-16Linear codes: basics of coding theory, generator and check matrices, coding and decoding.BIE-LIN
BIE-TI-17OOP abstraction and class hierarchy - packages, classes, fields, methods, constructors, traits, equivalence and identity, superclass, subclass, inheritance, static and dynamic dispatch .BIE-OOP
BIE-TI-18OOP polymorphism - subtyping, generics, bounds and variance.BIE-OOP
BIE-TI-19OOP 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-20Top-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-21Formalisms 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-22Intermediate representation of programs, abstract syntax tree, translation of basic constructs of programming languages.BIE-PJP
BIE-TI-23Structure of memory in implementations of programming languages: static part, stack, heap. Activation records, mechanism of function calls.BIE-PPA
BIE-TI-24Lambda calculus: definition of basic notions, operations, representation of numbers.BIE-PPA
BIE-TI-25Functional programming, high-order functions, Lisp: S-expressions, cons cells, functions, recursion, mapping functionals.BIE-PPA
BIE-TI-26Logic programming, Prolog: facts, rules, queries, evaluation of queries, unification of queries, unification, cut operator.BIE-PPA
BIE-TI-27Linear regression, ridge regression (L2 regularisation).BIE-VZD
BIE-TI-28KNN (k nearest neighbors) method, clustering.BIE-VZD
BIE-TI-29Decision trees.BIE-VZD
BIE-TI-30Logistic regression.BIE-VZD

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