Navrhování a analýza algoritmů
Kód předmětu: 128YNAA |
Anotace | (semestr ) |
---|---|
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 (NG201900GM), skupina Geodézie a kartografie, spec. Geomatika, PV předměty, 2. semestr (NH20180002_1), dop. semestr 2 (tento studijní plán platil do akademického roku 2021/22 ) - 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 ) - studijní plán Geodézie a kartografie, specializace Geomatika (NG2023GMP), skupina Geodézie a kartografie, spec. Geomatika, PV předměty, 2. semestr (NH20180002_1), dop. semestr 2 (přechod na nový studijní plán, platí pro nástup 2021 a 2022 ) |