Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
XD33SLA Složitost algoritmů Rozsah výuky:14+4
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.
1. 2.
3. 4.
5. 

Požadavky:

Předmět je zahrnut do těchto studijních plánů:
Plán Obor Role Dop. semestr
MKM02-D Kybernetika a měření S 2
MKM04-D Kybernetika a měření S 2
MKM01-D Kybernetika a měření S 2
MKM03-D Kybernetika a měření S 2


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)