X33SLA | Složitost algoritmů | Rozsah výuky: | 2+2 | ||
---|---|---|---|---|---|
Přednášející (garant): | Štěpánková O. | Typ předmětu: | S | Zakončení: | KZ |
Zodpovědná katedra: | 333 | Kreditů: | 3 | Semestr: | L |
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í.
Osnovy 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. |
Osnovy 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 |
Literatura Č:
Souhrnná literatura neexistuje. Doporučení k jednotlivým kapitolám dodá přednášející.
Literatura A:
There is no text-book covering the course completely; any book on modern operating systems can be used. The lecturer will hint resources to particular topics.
Požadavky:
|
Předmět je zahrnut do těchto studijních plánů:
|
Stránka vytvořena 25. 2. 2002, semestry: Z/2001-2, Z/2002-3, L/2001-2, L/2002-3, připomínky k informační náplni zasílejte správci studijních plánů | Návrh a realizace: I. Halaška (K336), J. Novák (K336) |