| Název předmětu | Algoritmy a složitost |
|---|---|
| Kód předmětu | KBC/SZZM1 |
| Organizační forma výuky | bez kontaktní výuky |
| Úroveň předmětu | Magisterský |
| Rok studia | nespecifikován |
| Semestr | Zimní a letní |
| Počet ECTS kreditů | 0 |
| Vyučovací jazyk | Čeština |
| Statut předmětu | Povinný |
| Způsob výuky | Kontaktní |
| Studijní praxe | Nejedná se o pracovní stáž |
| Doporučené volitelné součásti programu | Není |
| Vyučující |
|---|
|
| 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 |
| nespecifikováno |
| 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 |
|
nespecifikováno
|
| Hodnoticí metody a kritéria |
|
nespecifikováno
|
| Doporučená literatura |
|
|
| Studijní plány, ve kterých se předmět nachází |
| Fakulta | Studijní plán (Verze) | Kategorie studijního oboru/specializace | Doporučený semestr | |
|---|---|---|---|---|
| Fakulta: Přírodovědecká fakulta | Studijní plán (Verze): Bioinformatika (2021) | Kategorie: Informatické obory | 2 | Doporučený ročník:2, Doporučený semestr: Letní |