Studenti budou umět:

budou mít důkladný přehled efektivních algoritmů pro řešení standardních problémů.

pracovat s asymptotickou notací používanou při vyjadřování složitosti.

budou rozumět algoritmům pro řazení o složitosti O(n.log n), pro speciální řazení s lineární složitostí a pro řazení ve vnějších pamětech, algoritmům asociativního a adresního vyhledávání (vyhledávací stromy, rozptýlené tabulky, vícerozměrné vyhledávací stromy).

znát a používat pokročilé datové struktury.

ovládat metody používané pro analýzu paměťové a operační složitosti algoritmů.

Students will be able to:

Understand a set of well-known standard algorithms

Recognize a proper algorithm variant for any specific usage

Use learn basic methods of algorithm analysis to be used as a main efficiency criterion

Z:Cormen, T. H., Leiserson, C. E., Rivest, R. L. Introduction to Algorithms. The MIT Press, 2001. ISBN 0262032937.

R:Cormen, T. H., Leiserson, C. E., Rivest, R. L. Introduction to Algorithms. The MIT Press, 2001. ISBN 0262032937.

https://edux.fit.cvut.cz/courses/BI-EFA/

(nutné přihlášení)

https://edux.fit.cvut.cz/courses/BI-EFA/

(login necessary)

1. Datové struktury 1: Základní ADT.

2. Datové struktury 2: Rozptylovací tabulky.

3. Algoritmy řazení 1.^

4. Datové struktury 3: Stromy, haldy.

5. Algoritmy řazení 2.

6. Datové struktury 4: Pokročilé haldy.

7. Vyhledávání a vyhledávací stromy.

8. Rekurzivní algoritmy.

9. B-stromy a jejich varianty.

10. Vyvažované vyhledávací stromy.

11. Dynamické programování.

12. Algoritmy výpočetní geometrie.

1. Data structures I: Fundamental ADTs.

2. Data structures II: Hash tables.

3. Sorting algorithms I.

4. Data structures III: Trees, heaps.

5. Sorting algorithms II.

6. Data structures IV: Advanced heaps.

7. Searching and search trees.

8. Recursive algorithms.

9. B-trees and their variants.

10. Balanced search trees.

11. Dynamic programming.

12. Computational geometry algorithms.

Předpokládá se schopnost aktivního algoritmického řešení základních typů úloh, znalost nějakého vyššího programovacího jazyka (Java, C++) a znalost základních pojmů z matematické analýzy a kombinatoriky.

An ability to solve basic algorithmic problems actively, to express the algorithmic solution in a high-level programming language (Java, C++), and knowledge of basic notions from calculus and combinatorics is assumed.