|
Vyučující
|
-
Jančar Petr, prof. RNDr. CSc.
-
Šebela Marek, prof. Mgr. Dr.
|
|
Obsah předmětu
|
Binární vyhledávací stromy; průměrný čas hledání, průměrná výška. Catalanova čísla. Optimální binární vyhledávací stromy, algoritmus. Hashování; řešení kolizí a průměrný čas operací. Univerzální hashování a dokonalé hashování. Pagerank. R-stromy, R*-stromy, R+-stromy. Hilbertovy stromy a statické R-stromy. Optimalizační problémy, aproximační algoritmy, základní pojmy a příklady. Třídy NPO a PO, NP-těžké optimalizační problémy, příklady, vlastnosti. Problém pokrytí množiny (SET-COVER): aproximační algoritmy a jejich vlastnosti. Problém obchodního cestujícího a jeho varianty: aproximační algoritmy a jejich vlastnosti. Aproximační schémata a jejich příklady. Lineární programování: definice, varianty, obtížnost, princip duality. Metoda relaxace k lineárnímu programování: princip a příklad jejího použití.
|
|
Studijní aktivity a metody výuky
|
Dialogická (diskuze, rozhovor, brainstorming)
- Příprava na zkoušku
- 50 hodin za semestr
|
|
Výstupy z učení
|
Zkouška má za cíl prověřit znalosti, dovednosti a schopnost kritického zhodnocení a řešení problému v rámci zkoušeného oboru.
|
|
Předpoklady
|
Úspěšné zvládnutí požadavků navazujícího magisterského studia
|
|
Hodnoticí metody a kritéria
|
Ústní zkouška
Požadavkem je prokázat na základě teoretického i praktického studia znalosti a schopnost orientace v problematice zkoušeného oboru.
|
|
Doporučená literatura
|
-
Literatura uvedená u odpovídajícího předmětu.
|