|
Vyučující
|
-
Geyer Jakub, Mgr. Ph.D.
-
Valdman Jan, XXX MSc.
|
|
Obsah předmětu
|
Témata: 1.Úvod do algoritmů, definice, základní přístupy. 2.Časová a prostorová složitost. 3.Datové struktury: kompaktní a spojové seznamy, zásobník, fronta, halda. 4.Algoritmy řazení a vyhledávání. 5.Vyhledávací stromy: BST, AVL, Red-Black stromy. 6.Grafové algoritmy: reprezentace grafu v počítači, procházení grafu, nejkratší cesta. 7.Grafové algoritmy: minimální kostra, toky v grafu. 8.Vyhledávání v textu. 9.Návrh algoritmů: Rozděl a panuj. 10.Návrh algoritmů: Hladový algoritmus. 11.Návrh algoritmů: Dynamické programování. 12.Těžké problémy: NP-úplné problémy, Aproximační algoritmy. Obsah cvičení/semináře: Obsah semináře odpovídá tématům z přednášek.
|
|
Studijní aktivity a metody výuky
|
Monologická (výklad, přednáška, instruktáž), E-learning
- Semestrální práce
- 70 hodin za semestr
- Příprava na zápočet
- 40 hodin za semestr
- Příprava na zkoušku
- 40 hodin za semestr
|
|
Výstupy z učení
|
Cílem předmětu je seznámení se základními algoritmy a metodami návrhu algoritmů. Studenti si v rámci předmětu aktivně osvojí základní algoritmické konstrukce a postupy pro návrh algoritmů. Během kurzu se seznámí se základními abstraktními datovými typy (pole, seznam, strom, slovník), s často používanými algoritmy (řazení, grafové algoritmy, vyhledávání v textu) a dále s metodami návrhu algoritmů (rozděl a panuj, hladový algoritmus, dynamické programování).
Absolvent kurzu bude rozumět základním principům algoritmů, bude schopen vytvářet jednodušší algoritmy a používat je při vytváření svých programů.
|
|
Předpoklady
|
Předpoklady: Základní znalost matematiky v rozsahu učiva střední školy
|
|
Hodnoticí metody a kritéria
|
Písemná zkouška
Účast na cvičení, zprácování úloh na cvičení, vypracování seminární práce (vytvoření programu v libovolném programovacím jazyce zahrnující zadaný algoritmus), absolvování písemného závěrečného testu.
|
|
Doporučená literatura
|
-
CORMEN, Thomas H. Algorithms unlocked. Cambridge, MA: MIT Press, 2013. ISBN 978-0262518802..
-
EDMONDS, J. How to Think about Algorithms, Cambridge: Cambridge University Press, 2008. ISBN 978-0521614108..
-
ERICKSON, Jeff. Algorithms. 1. Urbana-Champaign, USA: Independently published. (dostupné na https://jeffe.cs.illinois.edu/teaching/algorithms/). ISBN 978-1792644832..
-
KLEINBERG, J., TARDOS, E. Algorithm design. 3. vyd. Boston: Pearson, 2011. ISBN 978-0273752332..
-
MAREŠ, M. a T. VALLA. Průvodce labyrintem algoritmů. Praha: CZ.NIC, z.s.p.o., 2017. CZ.NIC. (dostupné na: https://knihy.nic.cz/files/edice/pruvodce_labyrintem_algoritmu.pdf). ISBN 978-80-88168-19-5..
-
MILKOVÁ, E., BERÁNEK, L., VOBORNÍK, P. Algortihms: Explanation, Exercises and Visualization of the Basic Algorithmic Constructions. Gaudeamus, Hradec Králové, 2009. ISBN 978-80-7041-635-8..
-
PROKOP, Jiří. Algoritmy v jazyku C a C++. 3., aktualizované a rozšířené vydání. Praha: Grada, 2015. Průvodce (Grada). ISBN 978-80-247-5467-3..
-
SEDGEWICK, Robert. Algoritmy v C. Praha: SoftPress, 2003. ISBN 80-86497-56-9..
-
WRÓBLEWSKI, Piotr. Algoritmy. Brno: Computer Press. 2015. ISBN 978-80-251-4126-7..
|