Předmět je základní jednotka výuky, jejímž prostřednictvím si student osvojí ucelenou část souboru znalostí a dovedností, potřebnou pro zvládnutí studijního oboru/specializace. Za věcný obsah předmětu zodpovídá garant předmětu. Časovou náročnost předmětu zhruba vyjadřuje atribut předmětu rozsah kontaktní výuky. Například rozsah = 2+2  značí, že předmět bude mít týdně dvě hodiny přednášek a dvě hodiny cvičení týdně. Na závěr semestru musí vyučující provést vyhodnocení, nakolik si ten který student osvojil poznatky a dovednosti, kterých měl během výuky nabýt. Jakým způsobem toto hodnocení vyučující provedou určuje atribut způsob zakončení. U předmětu lze definovat, že předmět je zakončen pouze zápočtem(Z), klasifikovaným zápočtem(KZ), pouze zkouškou(ZK), nebo zápočtem a zkouškou(Z,ZK). Náročnost úspěšného absolvování předmětu je vyjádřena ECTS kreditními body. Výuka předmětu probíhá během semestru. Opakovaně se předmět vyučuje vždy v zimním(Z), nebo v letním(L) semestru každého akademického roku. Výjimečně může předmět být nabízen studentům v obou semestrech(Z,L). Za organizační zajištění výuky zodpovídá přiřazená katedra, která zejména vytvoří časový rozvrh předmětu a zajistí pro předmět vyučující. Někteří přednáší a zkouší, jiní vedou cvičení a udělují zápočty.
Obsahová náplň a další organizační informace, týkající se předmětu je popsána pomocí různých popisných textů(anotace, týdenní osnova, literatura, apod.)
$DODATEK_POPIS

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

Osnovy přednášek:

1.		Motivace, definice grafu, důležité grafy, neorientované grafy, reprezentace grafů, podgrafy.
2.		Souvislost, komponenty, DFS, zavedení orientovaného grafu, stromy.
3.		Kostry, vzdálenosti, BFS, topologické řazení.
4.		Přehled základních algoritmů řazení s kvadratickou složitostí. Zavedení pojmu binární halda jako částečně uspořádané struktury. HeapSort.
5.		Nafukovací pole, amortizovaná složitost. Binomiální haldy.
6.		Operace a vlastnosti binárních vyhledávacích stromů, způsoby jejich vyvažování, podrobnější diskuze AVL stromů.
7.		Randomizované algoritmy, základy pravděpodobnosti, hešování a strategie řešení kolizí.
8.		Rekurzivní algoritmy a metoda Rozděl a panuj.
9.		QuickSort. Dolní mez složitosti řazení v porovnávacím modelu. Speciální algoritmy řazení.
10.		Dynamické programování.
11.		Minimální kostra ohodnoceného grafu. Jarníkův a Kruskalův algoritmus a jejich implementace.
12.		[2] Algoritmy hledání nejkratších cest v ohodnoceném grafu.

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. 1. progtest
4.		Řadící algoritmy O(n^2). Binární haldy.
5.		Nafukovací pole, amortizovaná složitost, binomiální haldy.
6.		Vyhledávací stromy a jejich vyvažování. 2. progtest
7.		Pravděpodobnostní algoritmy a jejich složitost. QuickSort.
8.		Rozptylování (hešování) a vyhledávací tabulky.
9.		Rekurzivní algoritmy a metoda Rozděl a panuj.
10.		Semestrální písemka.
11.		Dynamické programování. 3. progtest
12.		Minimální kostry a nejkratší cesty v grafech.

Literatura:

1.		Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. : Introduction to Algorithms (3rd Edition). MIT Press, 2016. ISBN 978-0262033848.
2.		Wengrow J. : A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills (2nd Edition). Pragmatic Bookshelf, 2020. ISBN 978-1680507225.
3.		Sedgewick R. : Algorithms (4th Edition). Addison-Wesley, 2011. ISBN 978-0321573513.
4.		Deo N. : Graph Theory with Applications to Engineering and Computer Science. Dover Publications, 2016. ISBN 978-048680793.
5.		Bickle A. : Fundamentals of Graph Theory. AMS, 2020. ISBN 978-1470453428.

Požadavky:
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. Předmět předpokládá, že student souběžně studuje BI-AAG a BI-ZDM.

Chybí některá textová pole,vyplněny mají být anotace, požadavky, osnova (sylabus), osnova cvičení, studijní materiály, klíčová slova, CZ i EN, webová strana předmětu

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr BIK-IB.21 Informační bezpečnost 2021 PP 3 BIK-SPOL.21 Nespecifikovaný/á obor/specializace studia - Unspecified Branch/Specialisation of Study PP 3 BIK-PV.21 Počítačové systémy a virtualizace 2021 PP 3 BIK-PS.21 Počítačové sítě a Internet 2021 PP 3 BIK-SI.21 Softwarové inženýrství 2021 PP 3