Složitost algoritmů

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 třídy úloh. Budou vysvětleny heuristiky pro NP-úplné úlohy, 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, ?, ?

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, ?, ?

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:

Souhrnná literatura neexistuje. Doporučení k jednotlivým kapitolám dodá přednášející.

Poznámka:

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)