| Anotace | (semestr B242) |
|---|
| Předmět poskytuje obecný pohled na problematiku návrhu a analýzy vlastností algoritmů (specifikace, důkazy správnosti, časová a paměťová složitost, jejich měření a dokazování). Výklad není zaměřen na konkrétní programovací jazyk. Probírají se základní modely výpočtu, základní datové struktury, třídění, vybrané grafové algoritmy a další.
Třídy úloh P a NP. |
| Obsah | |
|---|
Algoritmická úloha, modely výpočtu, existence algoritmicky neřešitelných úloh,
časové odhady, asymptotické vyjádření složitosti, složitost v nejhorším a průměrném případě,
dokazování správnosti a časového odhadu algoritmů na příkladech,
datové struktury pro implementaci množin a seznamů čísel,
hashování, datová struktura trie,
halda, datová struktura pro operace union-find,
třídění, mergesortt, heapsort, quicksort, časový odhad zdola,
amortizovaná složitost,
randomizace,
rekurze, složitost rekurzivních algoritmů,
třída úloh NP, Cookova věta,
důkazy NP úplnosti vybraných úloh
důkazy NP úplnosti dalších úloh |
| Literatura | |
|---|
Povinná literatura:
[1] Demel, J.: Grafy a jejich aplikace, 2002, Academia Praha, ISBN 80-200-0990-6; 2. vydání vlastním nákladem 2015, ISBN 80-260-7684-1
Doporučená literatura:
[2] Kozen, D.: The Design and Analysys of Algorithms, Springer, 1991, 978-0-387-97687-7.
[3] Aho, Hopcroft, Ullman, Design and analysys of Computer Algorithms, Addison-Wesley, 1974, ISBN 0201000296.
|
| Návaznosti | |
|---|
| -- |
| Studijní plány | |
|---|
Předmět je zařazen do následujících studijních plánů:
- studijní plán Geodézie a kartografie, specializace Geomatika (NG2023GM), skupina Geodézie a kartografie, spec. Geomatika, PV předměty, 2. semestr (NH20230002_1), dop. semestr 2 (platí pro nástup od akad. roku 2023/24 )
|
