BIE-TI.21
Computer Science
topics are valid since SFE in June 2024
| Label | Topic | Course |
|---|---|---|
| BI-TI.21-1 | Chomsky hierarchy of formal languages and grammars. Turing machines, universal Turing machine, recursive-enumerable and recursive languages. The P, NP, and NP-complete classes of problems. | BIE-AAG.21 |
| BIE-TI.21-2 | Transformations of context free grammars and their normal forms. The CYK algorithm. | BIE-AAG.21 |
| BIE-TI.21-3 | Implementation of finite automata, lexical analyzer. | BIE-AAG.21 + BIE-PJP.21 |
| BIE-TI.21-4 | Higher connectivity of graphs, vertex, edge connectivity, and their relations, Menger’s theorem. Bridges, strongly connected components of an oriented graph, and searching for them. Network flows, relationship between flow size and cut capacity, Ford-Fulkerson’s algorithm. Matching, searching for a maximum matching in a bipartite graph, Hall’s theorem and its corollaries. | BIE-AG2.21 |
| BIE-TI.21-5 | Planar graphs, Euler’s formula and its corollaries, Kuratowski’s theorem. Chromatic number of a graph, chromatic number of planar graphs. Convex hull of points in plane, determination of angle orientation. The sweep-line technique and fast calculation of intersections of line segments. | BIE-AG2.21 |
| BIE-TI.21-6 | Fibonacci heaps and amortized and worst-case complexity of their operations. (a, b)-trees. | BIE-AG2.21 |
| BIE-TI.21-7 | Eulerian tour, characterization of Eulerian graphs, minimum coverage by trails. Hamiltonian cycle, Chvátal’s closure, Bondy-Chvátal’s theorem. Traveling Salesperson Problem, approximation algorithms. | BIE-AG2.21 |
| BIE-TI.21-8 | Instrukční cyklus počítače a zřetězené zpracování instrukcí. Mikroarchitektura skalárního procesoru se zřetězeným zpracováním instrukcí, datové a řídicí hazardy při zřetězeném zpracování instrukcí a způsoby jejich ošetření. | BIE-APS.21 |
| BIE-TI.21-9 | Paměťová hierarchie se skrytou pamětí (cache memory), principy lokality a fungování skryté paměti. Architektura přímé, částečně asociativní, plně asociativní skryté paměti. | BIE-APS.21 |
| BIE-TI.21-10 | HW podpora virtualizace hlavní paměti stránkováním, funkce MMU (Memory Management Unit) a překlad virtuálníchch adres na fyzické adres pomocí TLB (Translation Lookaside Buffer), ošetření výpadku stránky. | BIE-APS.21 |
| BIE-TI.21-11 | Binary relations, their properties and representations. Equivalences and partitions. Partial and total orders. | BIE-DML.21 |
| BIE-TI.21-12 | Lineární zobrazení: definice a vlastnosti (hodnost, jádro, defekt, injektivita, surjektivita), matice lineárního zobrazení. | BIE-LA2.21 |
| BIE-TI.21-13 | Skalární součin a norma vektoru: definice, vlastnosti a příklady. | BIE-LA2.21 |
| BIE-TI.21-14 | Ortogonalita a ortogonální báze: definice, vlastnosti, využití při počítání vzdáleností lineárních variet. | BIE-LA2.21 |
| BIE-TI.21-15 | LU rozklad matic, řešení soustavy lineárních rovnic pomocí LU rozkladu. | BIE-LA2.21 |
| BIE-TI.21-16 | Logical consequence and equivalence in propositional and predicate logic. Disjunctive and conjunctive normal forms. Resolution method. Semantic tree method. | BIE-LOG.21 |
| BIE-TI.21-17 | Theory, model, logical consequence. Axiomatic system of logic. Correctness, completeness, indisputability. Gödel’s incompleteness theorem. | BIE-LOG.21 |
| BIE-TI.21-18 | OOP polymorphismus – subtyping, generics, bounds a variance. | BIE-OOP.21 |
| BIE-TI.21-19 | 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.21 |
| BIE-TI.21-20 | Formalisms for syntax-directed translation – translation grammars, attribute grammars, attribute translation grammars. LL-attributed translation grammars, implementation by recursive-descent functions with parameters. | BIE-PJP.21 |
| BIE-TI.21-21 | Intermediate representation of programs, abstract syntax tree, translation of basic constructs of programming languages. | BIE-PJP.21 |
| BIE-TI.21-22 | Memory allocation when implementing programming languages: static parts, stack, heap. Activation records, function call implementation mechanism. | BIE-PPA.21 |
| BIE-TI.21-23 | Functional programming, higher-order functions, Lisp: S-expressions, cons cells, functions, recursion, mapping functionals. | BIE-PPA.21 |
| BIE-TI.21-24 | Logic programming, Prolog: facts, rules, queries, evaluation of queries, unification, cut operator. | BIE-PPA.21 |
| BIE-TI.21-25 | Heuristic state space search, heuristics for path cost estimation, greedy search, algorithm A*. | BIE-ZUM.21 |
📄 The table is available also in CSV (semicolon-separated values). 🔙 History of changes is on GitLab.