Složitost algoritmů
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
X33SLA | KZ | 4 | 2+2s | česky |
- Přednášející:
- Cvičící:
- Předmět zajišťuje:
- katedra kybernetiky
- Anotace:
-
Cílem předmětu je seznámit studenty s důležitou problematikou matematického pohledu na algoritmy a jejich složitost. Hlavní pozornost je věnována úlohám z oblasti teorie grafů a na nich jsou demonstrovány a vysvětlovány problémy složitosti a odpovídající třídy úloh včetně pojmu NP-úplná úloha. Budou vysvětleny heuristiky používané při řešení častých NP-úplných úloh, Cookova věta, algoritmicky neřešitelné úlohy, apod. Cvičení se pak v bezprostřední návaznosti na přednášky věnují procvičování látky a prohlubování znalostí.
- Požadavky:
- Osnova přednášek:
-
1. Algoritmus, správnost algoritmu, časová a paměťová složitost
2. Asymptotický růst funkcí, značení O (f(x)), o(f(x))
3. Rekursivní algoritmy, výpočet složitosti rekursivních algoritmů
4. Topologické uspořádání vrcholů a hran
5. Minimální kostra, hladové algoritmy
6. Nejkratší cesty z daného vrcholu, mezi všemi dvojicemi vrcholů
7. Aplikace algoritmů nejkratších cest
8. Toky v sítích
9. Třídy úloh P a NP
10. NP-úplné úlohy: obchodní cestující, barevnost grafu
11. Heuristiky pro NP-úplné úlohy
12. Cookova věta, převody úloh
13. Algoritmicky neřešitelné úlohy
14. Rezerva - shrnutí obsahu předmětu.
- Osnova cvičení:
-
1. Algoritmus, správnost algoritmu, časová a paměťová složitost
2. Asymptotický růst funkcí, značení O(f(x)), o(f(x))
3. Rekursivní algoritmy, výpočet složitosti rekursivních algoritmů
4. Topologické uspořádání vrcholů a hran
5. Minimální kostra, hladové algoritmy
6. Nejkratší cesty z daného vrcholu, mezi všemi dvojicemi vrcholů
7. Aplikace algoritmů nejkratších cest
8. Toky v sítích
9. Třídy úloh P a NP
10. NP-úplné úlohy: obchodní cestující, barevnost grafu
11. Heuristiky pro NP-úplné úlohy
12. Cookova věta, převody úloh
13. Algoritmicky neřešitelné úlohy
14. Zápočet, rezerva
- Cíle studia:
- Studijní materiály:
-
Harel, D.: Alogorithmics: The Spirit of Computing, Addison-Wesley Inc.,
Reading MA 1992 Gruska, J.: Foundations of Computing, Int. Thompson
Computer Press, London 1997
- Poznámka:
-
Rozsah výuky v kombinované formě studia: 14+4
Typ cvičení: s, c
Předmět je nabízen také v anglické verzi.
- Další informace:
- Pro tento předmět se rozvrh nepřipravuje
- Předmět je součástí následujících studijních plánů:
-
- Kybernetika a měření - řídicí technika- strukturované studium (povinně volitelný předmět)
- Kybernetika a měření - umělá inteligence- strukturované studium (povinně volitelný předmět)
- Kybernetika a měření - měřicí a přístrojové systémy- strukturované studium (povinně volitelný předmět)
- Kybernetika a měření - letecké informační a řídicí systémy- strukturované studium (povinně volitelný předmět)