Příprava studijního programu Informatika je podporována projektem financovaným z Evropského sociálního fondu a rozpočtu hlavního města Prahy.

Praha & EU: Investujeme do vaší budoucnosti

# | Label | Topic | Subject |
---|---|---|---|

1. | BIE-TI-1 | Transformations of context free grammars and their normal forms. The CYK algorithm. | BIE-AAG |

2. | BIE-TI-2 | Implementation of finite automata, lexical analyzer. | BIE-AAG |

3. | 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 |

4. | 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 |

5. | BIE-TI-5 | Planar graphs and graphs coloring: Euler formula. Kuratowski theorem. Chromatic number of a graph, chromatic number of planar graphs. | BIE-AG2 |

6. | BIE-TI-6 | Advanced data structures: The Fibonacci heaps and complexity of their operations in the worst case. (a, b)-trees. | BIE-AG2 |

7. | 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 |

8. | BIE-TI-8 | Distances in graphs: Floyd-Warshall algorithm. Traveling Salesperson Problem, definition and an approximation algorithm. | BIE-AG2 |

9. | 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 |

10. | BIE-TI-10 | Quantitative principles of computer architectures (the Amdahl's law, CPU performance equation), computer performance evaluation. | BIE-APS.1 |

11. | BIE-TI-11 | Pipelined instruction processing. Pipeline stages, controlling the flow of instructions between stages, hazards, their classification and handling. | BIE-APS.1 |

12. | BIE-TI-12 | Performance parameters of a memory system with caches. Multi-level caches. HW support for virtual memory. | BIE-APS.1 |

13. | BIE-TI-13 | Parallel architectures with shared memory, memory coherence and consistency. Instruction set primitives for process synchronization. | BIE-APS.1 |

14. | BIE-TI-14 | Instruction-level parallelism. Superscalar, superpipeline, and VLIW processors. Vector computers. | BIE-APS.1 |

15. | 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 |

16. | BIE-TI-16 | Linear codes: basics of coding theory, generator and check matrices, coding and decoding. | BIE-LIN |

17. | BIE-TI-17 | Pure object-oriented programming paradigm: basic notions, abstraction, behaviour. | BIE-OOP |

18. | BIE-TI-18 | Pure object-oriented programming paradigm: principles of OO systems. | BIE-OOP |

19. | BIE-TI-19 | Pure object-oriented programming paradigm: quality of proposals of OO design. | BIE-OOP |

20. | 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 |

21. | 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 |

22. | BIE-TI-22 | Intermediate representation of programs, abstract syntax tree, translation of basic constructs of programming languages. | BIE-PJP |

23. | BIE-TI-23 | Structure of memory in implementations of programming languages: static part, stack, heap. Activation records, mechanism of function calls. | BIE-PPA |

24. | BIE-TI-24 | Lambda calculus: definition of basic notions, operations, representation of numbers. | BIE-PPA |

25. | BIE-TI-25 | Functional programming, high-order functions, Lisp: S-expressions, cons cells, functions, recursion, mapping functionals. | BIE-PPA |

26. | BIE-TI-26 | Logic programming, Prolog: facts, rules, queries, evaluation of queries, unification of queries, unification, cut operator. | BIE-PPA |

27. | BIE-TI-27 | Data, information, and knowledge. Data sources and formats, data matrix. Nominal and numeric variables. Visualization and data exploration. | BIE-VZD |

28. | BIE-TI-28 | The nearest neighbour method, distance measures. Clustering methods (k-means, agglomerative clustering). | BIE-VZD |

29. | BIE-TI-29 | Neural networks, multilayered perceptrons and training principles. Self organizing maps. | BIE-VZD |

30. | BIE-TI-30 | Decision trees and their applications. Random forest classifiers and boosted trees. | BIE-VZD |