Algoritmy II

Typ studia	bakalářské
Jazyk výuky	čeština
Kód	460-2003/04
Zkratka	ALG II
Název předmětu česky	Algoritmy II
Název předmětu anglicky	Algorithms II
Kreditů	5
Garantující katedra	Katedra informatiky
Garant předmětu	doc. Mgr. Jiří Dvorský, Ph.D.

Osnova předmětu

Strategie řešení transformuj a vyřeš. Předtřídění dat. Gaussova eliminační metoda. AVL stromy.
Strategie řešení změnou reprezentace. Halda a třídění haldou. Hornerovo pravidlo. Výpočet mocniny.
Strategie řešení redukcí problému. Redukce na grafové problémy.
Záměna paměťové a časové složitosti (Space-time trade-off). Hašování. B-stromy.
Dynamické programování. Problém batohu. Floydův algoritmus.
Hladové algoritmy. Primův algoritmus. Dijkstrův algoritmus. Huffmanovo kódování.
Strategie řešení iterativním zlepšováním. Simplexová metoda.
Meze možností algoritmického řešení problémů. P, NP a NP-úplné problémy.
Prohledávání s návratem. Problém osmi dam.
Aproximační algoritmy pro NP-těžké problémy.

Náplň cvičení
Gaussova eliminační metoda. AVL stromy.
Implementace haldy, třídění haldou.
Hašovací tabulky.
B-tromy.
Dynamické programování. Floydův algoritmus
Hladové algoritmy. Primův algoritmus. Dijkstrův algoritmus.
Huffmanovo kódování.
Simplexová metoda.
Prohledávání s návratem. Problém osmi dam.
Aproximační algoritmy pro NP-těžké problémy.

Povinná literatura

LEVITIN, Anany. Introduction to the Design and Analysis of Algorithms. 3rd ed. Boston: Pearson, 2012. .
CORMEN, Thomas H. Introduction to algorithms. 2nd ed. Cambridge, Mass.: MIT Press, 2001. ISBN 02-620-3293-7.
SEDGEWICK, Robert. Algoritmy v C. Praha: SoftPress, 2003. ISBN 80-864-9756-9.
WRÓBLEWSKI, Piotr. Algoritmy. Brno: Computer Press, 2015. .
WIRTH, N. Algoritmy a štruktúry údajov, Alfa, Bratislava 1989.
Studijní opora (skripta), dostupné na stránkách garanta předmětu, www.cs.vsb.cz/dvorsky

Doporučená literatura

STROUSTRUP, Bjarne. C++ programovací jazyk. Praha: Softwarové Aplikace a Systémy, 1997. ISBN 80-901-5072-1.
VIRIUS, Miroslav. Pasti a propasti jazyka C++. 2., aktualiz. a rozš. vyd. Brno: CP Books, 2005. ISBN 80-251-0509-1.
SCHILDT, Herbert. Nauč se sám C++: [poznej, vyzkoušej, používej]. Praha: SoftPress, 2001. ISBN 80-864-9713-5.
ECKEL, Bruce. Myslíme v jazyku C++. Praha: Grada, 2000. Knihovna programátora (Grada). ISBN 80-247-9009-2.

zpět na vyhledávání