[1] Sawa, Z.: Teorie algoritmů (slidy k předmětu), VŠB-TU, Ostrava, 2025 (dostupné z web-stránky předmětu).
[2] Sipser, M.: Introduction to the Theory of Computation, Thomson 2006.
[3] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
Teorie algoritmů
| Jazyk výuky | angličtina, čeština |
|---|---|
| Kód | 460-4167 |
| Zkratka | TA |
| Název předmětu česky | Teorie algoritmů |
| Název předmětu anglicky | Theory of Algorithms |
| Garantující katedra | Katedra informatiky |
| Garant předmětu | doc. Ing. Zdeněk Sawa, Ph.D. |
Anotace
Předmět se zabývá studiem algoritmů z teoretického hlediska a podává obecný přehled řady teoretických výsledků z této oblasti.
Na začátku se nejprve zabývá otázkou, co je to algoritmus a algoritmický problém, a ukazuje příklady různých výpočetních modelů a jejich vzájemných simulací. Dále jsou studovány otázky týkající se vyčíslitelnosti a algoritmické rozhodnutelnosti a je ukázáno, že existuje řada algoritmicky nerozhodnutelných problémů.
Dále jsou studovány otázky týkající výpočetní složitosti. Jsou ukázány některé pokročilejší techniky analýzy výpočetní složitosti algoritmů, jako jsou například analýza výpočetní složitosti rekurzivních algoritmů, amortizovaná složitost či analýza složitosti v průměrném případě. Dále je studována výpočetní složitost problémů a různé třídy složitosti. Zvláště důležitou roli zde hrají NP-úplné problémy, ale jsou diskutovány i některé další třídy složitosti.
Jsou rovněž studovány některé techniky používané při návrhu efektivních algoritmů.
Dále jsou studovány některé specifické druhy algoritmů, jako jsou například randomizované či aproximační algoritmy.
Speciální pozornost je věnována paralelním a distribuovaným algoritmům a analýze a návrhu těchto algoritmů.
Výsledky učení:
- Porozumět tomu, co je to výpočetní složitost algoritmů a být schopen tuto výpočetní složitost analyzovat.
- Rozumět tomu, že některé problémy mohou být algoritmicky nerozhodnutelné, a ty, které jsou algoritmicky řešitelné, mohou mít různou výpočetní složitost.
- Získat základní povědomí o různých třídách složitosti.
- Osvojit si některé základní techniky používané při návrhu efektivních algoritmů.
- Rozumět pojmům jako jsou aproximační algoritmy, pravděpodobnostní algoritmy apod. a umět vyhodnotit možnosti jejich použití v praxi.
- Znát některé základní techniky používané při návrhu paralelních a distribuovaných algoritmů a být schopen analyzovat výpočetní složitost těchto algoritmů.
Na začátku se nejprve zabývá otázkou, co je to algoritmus a algoritmický problém, a ukazuje příklady různých výpočetních modelů a jejich vzájemných simulací. Dále jsou studovány otázky týkající se vyčíslitelnosti a algoritmické rozhodnutelnosti a je ukázáno, že existuje řada algoritmicky nerozhodnutelných problémů.
Dále jsou studovány otázky týkající výpočetní složitosti. Jsou ukázány některé pokročilejší techniky analýzy výpočetní složitosti algoritmů, jako jsou například analýza výpočetní složitosti rekurzivních algoritmů, amortizovaná složitost či analýza složitosti v průměrném případě. Dále je studována výpočetní složitost problémů a různé třídy složitosti. Zvláště důležitou roli zde hrají NP-úplné problémy, ale jsou diskutovány i některé další třídy složitosti.
Jsou rovněž studovány některé techniky používané při návrhu efektivních algoritmů.
Dále jsou studovány některé specifické druhy algoritmů, jako jsou například randomizované či aproximační algoritmy.
Speciální pozornost je věnována paralelním a distribuovaným algoritmům a analýze a návrhu těchto algoritmů.
Výsledky učení:
- Porozumět tomu, co je to výpočetní složitost algoritmů a být schopen tuto výpočetní složitost analyzovat.
- Rozumět tomu, že některé problémy mohou být algoritmicky nerozhodnutelné, a ty, které jsou algoritmicky řešitelné, mohou mít různou výpočetní složitost.
- Získat základní povědomí o různých třídách složitosti.
- Osvojit si některé základní techniky používané při návrhu efektivních algoritmů.
- Rozumět pojmům jako jsou aproximační algoritmy, pravděpodobnostní algoritmy apod. a umět vyhodnotit možnosti jejich použití v praxi.
- Znát některé základní techniky používané při návrhu paralelních a distribuovaných algoritmů a být schopen analyzovat výpočetní složitost těchto algoritmů.
Povinná literatura
Doporučená literatura
[4] Kozen, D.: Automata and Computability, Undergraduate Text in Computer Science, Springer-Verlag, 1997.
[5] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
[6] Kozen, D.: Theory of computation, Springer 2006.
[7] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.
[8] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003.
[9] Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity, Dover Publications Inc, 2000.
[10] Gibbons, A., Rytter, W.: Efficient Parallel Algorithms, Cambridge University Press, 1989.
[5] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
[6] Kozen, D.: Theory of computation, Springer 2006.
[7] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.
[8] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003.
[9] Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity, Dover Publications Inc, 2000.
[10] Gibbons, A., Rytter, W.: Efficient Parallel Algorithms, Cambridge University Press, 1989.