|
Vyučující
|
-
Novotný Lukáš, doc. Ing. Ph.D.
|
|
Obsah předmětu
|
1. Jazyky. Reducibilita. Výpočetní modely. Gramatiky. 2. Turingovy stroje. Míry výpočetní složitosti. 3. Třídy časové složitosti. Třída P. 4. Třída NP. Struktura třídy NP. 5. Parametrizovaná složitost. 6. Neuniformní výpočetní složitost. 7. Výpočetní složitost optimalizačních úloh. Aproximovatelnost. 8. Booleovská a polynomiální hierarchie. 9. Třídy paměťové složitosti. 10. Pravděpodobnostní algoritmy a třídy složitosti. 11. Interaktivní důkazové systémy. PCP třídy. 12. Paralelní výpočetní složitost. 13. Složitost logických teorií. Základy Kolmogorovy teorie složitosti. 14. Kvantové výpočty.
|
|
Studijní aktivity a metody výuky
|
Přednáška s aktivizací, Přednáška, Cvičení
- Kontaktní výuka
- 52 hodin za semestr
- Příprava na zkoušku [10-60]
- 56 hodin za semestr
- Příprava na souhrnný test [6-30]
- 35 hodin za semestr
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| popsat výpočetní model počítače s libovolným přístupem (RAM) |
| formulovat základní polynomiálně řešitelné úlohy |
| formulovat základní úlohy řešitelné nedeterministicky v polynomiálním čase |
| Odborné dovednosti |
|---|
| aplikovat algoritmy pro základní polynomiálně řešitelné úlohy |
| vyřešit jednoduchou úlohu lineárního programování |
| Obecné způsobilosti |
|---|
| bc. studium: kriticky přistupuje ke zdrojům informací, informace tvořivě zpracovává a využívá při svém studiu a praxi, |
| mgr. studium: samostatně a odpovědně se na základě rámcového zadání rozhodují v souvislostech jen částečně známých, |
| bc. studium: rozpozná problém, objasní jeho podstatu, rozčlení ho na části, |
| Výsledky učení |
|---|
| Odborné znalosti |
|---|
| definovat složitostní třídy optimalizačních úloh |
| popsat pravděpodobnostní třídy výpočetní složitosti |
| popsat výpočetní model Turingova stroje |
| vysvětlit aproximační algoritmy pro standardní úlohy |
| Odborné dovednosti |
|---|
| odhadnout výpočetní složitost dané úlohy |
| odhadnout aproximovatelnost dané optimalizační úlohy |
| navrhnout jednoduchý pravděpodobnostní algoritmus pro danou úlohu |
| Obecné způsobilosti |
|---|
| mgr. studium: srozumitelně a přesvědčivě sdělují odborníkům i širší veřejnosti vlastní odborné názory, |
| bc. studium: samostatně a odpovědně se na základě rámcového zadání rozhodují v souvislostech jen částečně známých, |
| Vyučovací metody |
|---|
| Odborné znalosti |
|---|
| Přednáška založená na výkladu, |
| Přednáška s aktivizací studentů, |
| Cvičení (praktické činnosti), |
| Odborné dovednosti |
|---|
| Cvičení (praktické činnosti), |
| Obecné způsobilosti |
|---|
| Přednáška s aktivizací studentů, |
| Hodnotící metody |
|---|
| Odborné znalosti |
|---|
| Ústní zkouška, |
| Test, |
| Individuální prezentace, |
| Odborné dovednosti |
|---|
| Demonstrace dovedností (praktická činnost), |
| Obecné způsobilosti |
|---|
| Ústní zkouška, |
|
Doporučená literatura
|
-
Bovet, Daniel Pierre; Crescenzi, Pierluigi. Introduction to the theory of complexity. 1994. ISBN 0-13-915380-2.
-
Hromkovič, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. 2nd ed. Berlin : Springer, 2003. ISBN 3-540-44134-4.
-
Rothe, Jörg. Complexity theory and cryptology : an introduction to cryptocomplexity. 2005. ISBN 3-540-22147-6.
-
Sedgewick, Robert; Flajolet, Philippe. An introduction to the analysis of algorithms. Boston : Addison-Wesley, 1996. ISBN 0-201-40009-X.
-
Sipser, Michael. Introduction to the theory of computation. 2nd ed. Boston : Thomson Course Technology, 2006. ISBN 0-534-95097-3.
-
Vazirani, Vijay V. Approximation algorithms. Berlin : Springer, 2001. ISBN 3-540-65367-8.
|