Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2020/2021

Algoritmy a grafy 1

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
BIK-AG1.21 Z,ZK 5 14KP+4KC česky
Přednášející:
Cvičící:
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:

Předmět pokrývá to nejzákladnější z efektivních algoritmů, datových struktur a teorie grafů, které by měl znát každý informatik. Studenti se naučí techniky důkazů korektnosti jednotlivých algoritmů a techniky asymptotické matematiky pro určování jejich složitostí v nejlepším, nejhorším, či průměrném případě (předmět zahrnuje i základy teorie pravděpodobnosti nutné pro pochopení randomizovaných algoritmů). V rámci cvičení se studenti seznamují s použitím vysvětlovaných algoritmů pro řešení praktických problémů.

Požadavky:
Osnova přednášek:

1. Motivation, graph definition, important types of graphs, undirected graphs, graph representation, subgraphs.

2. Connectivity, connected components, DFS, directed graphs, trees.

3. Spanning trees, distances in graphs, BFS, topological ordering.

4. Basic sorting algorithms with the quadratic time complexity. Binary heap as a partial ordered structure, HeapSort.

5. Extendable array, amortized complexity. Binomial Heaps.

6. Operations and properties of binary search trees, balancing strategies, AVL trees.

7. Randomized algorithms. Introduction to probability theory. Hash tables and strategies of collision resolving.

8. Recursive algorithms and Divide and Conquer algorithms.

9. QuickSort. Lower bound of complexity for sorting problem in the comparison model. Special sorting algorithms.

10. Dynamic programming.

11. Minimum spanning trees of edge-labelled graphs. Jarník’s algorithm and Kruskal’s algorithm and their implementations.

12. [2] Shortest paths algorithms on edge-labelled graphs.

Osnova cvičení:
Cíle studia:

Předmět pokrývá to nejzákladnější z efektivních algoritmů, datových struktur a teorie grafů, které by měl znát každý informatik.Spolupracuje se souběžně vyučovanými předměty BI-AAG a BI-ZDM, ve kterých studenti získají znalosti a dovednosti nezbytné pro vyhodnocování operační a paměťové složitosti algoritmů a naučí se prakticky používat asymptotickou matematiku.

Studijní materiály:

[1] Cormen, T. H. - Leiserson, C. E. - Rivest, R. L. - Stein, C.: Introduction to Algorithms, 3rd Edition, MIT Press, 2009, 978-0262033848,

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/BIK-AG1/

Další informace:
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 18. 1. 2021
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet6546606.html