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.

Z:Handbook of Graph Theory, 2nd Edition (Discrete Mathematics and Its Applications). Chapman and Hall/CRC, 2013. ISBN 978-1439880180.

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

R:Handbook of Graph Theory, 2nd Edition (Discrete Mathematics and Its Applications). Chapman and Hall/CRC, 2013. ISBN 978-1439880180.

Osnovy přednášek:

1. Motivace a úvod do teorie grafů

2. Základní definice a pojmy teorie grafů I 3. Základní definice a pojmy teorie grafů II

4. Řadící algoritmy O(n^2). Binární haldy a HeapSort.

5. Nafukovací pole, amortizovaná složitost, binomiální haldy

6. Vyhledávací stromy a jejich vyvažování

7. Pravděpodobnostní algoritmy a jejich složitost. QuickSort.

8. Rekurzivní algoritmy a metoda Rozděl a panuj. Lineární řazení

9. Rozptylování (hešování) a vyhledávací tabulky

10. Dynamické programování

11. Minimální kostry grafu

12. Nejkratší cesty v grafech

13. Rezerva

Osnovy cvičení:

1. Motivace a úvod do teorie grafů

2. Základní definice a pojmy teorie grafů I 3. Základní definice a pojmy teorie grafů II

4. Řadící algoritmy O(n^2). Binární haldy a HeapSort.

5. Nafukovací pole, amortizovaná složitost, binomiální haldy

6. Vyhledávací stromy a jejich vyvažování

7. Pravděpodobnostní algoritmy a jejich složitost. QuickSort.

8. Rekurzivní algoritmy a metoda Rozděl a panuj. Lineární řazení

9. Rozptylování (hešování) a vyhledávací tabulky

10. Dynamické programování

11. Minimální kostry grafu

12. Nejkratší cesty v grafech

13. Rezerva

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.