Materiály jsou dostupné na webu pedagoga: https://www.cs.vsb.cz/sawa/ta
Konzultace prostřednictvím MS Teams.
Teorie algoritmů
| Typ studia | navazující magisterské |
|---|---|
| Jazyk výuky | čeština |
| Kód | 460-4167/01 |
| Zkratka | TA |
| Název předmětu česky | Teorie algoritmů |
| Název předmětu anglicky | Theory of Algorithms |
| Kreditů | 5 |
| Garantující katedra | Katedra informatiky |
| Garant předmětu | doc. Ing. Zdeněk Sawa, Ph.D. |
Osnova předmětu
Přednášky:
- Úvod. Algoritmy a algoritmické problémy. Výpočetní modely (např. stroje RAM, Turingovy stroje, ...). Churchova-Turingova teze.
- Algoritmicky nerozhodnutelné problémy.
- Výpočetní složitost algoritmů. Asymptotická notace. Příklady technik používaných při analýze výpočetní složitosti algoritmů.
Analýza výpočetní složitosti rekurzivních algoritmů.
- Třídy složitosti. Nedeterministické algoritmy. Třídy P a NP. Redukce mezi problémy. NP-úplnost.
- Příklady některých klasických problémů z oblasti kombinatorické optimalizace. Příklady toho, kdy některé z těchto problémů jsou v P a některé NP-úplné.
- Další třídy složitosti (PSPACE, EXPTIME, EXPSPACE, L, NL, ...). Příklady úplných problémů pro jednotlivé třídy.
- Příklady technik návrhu efektivních algoritmů. Příklady použití těchto technik pro řešení kombinatorických problémů.
Greedy algoritmy a jejich souvislost s matroidy. Metoda větvení a mezí (branch and bound).
- Složitost algoritmů v průměrném případě. Amortizovaná složitost. Příklady některých pokročilejších datových struktur a analýzy složitosti operací na těchto strukturách.
- Randomizované algoritmy.
- Aproximační algoritmy. Špatně aproximovatelné problémy.
- Paralelní algoritmy: výpočetní modely pro paralelní algoritmy (PRAM), výpočetní složitost paralelních algoritmů.
- Distribuované algoritmy: výpočetní modely pro distribuované algoritmy, komunikační složitost.
Cvičení:
- Algoritmy a algoritmické problémy. Výpočetní modely (např. stroje RAM, Turingovy stroje, ...). Churchova-Turingova teze.
- Algoritmicky nerozhodnutelné problémy.
- Výpočetní složitost algoritmů. Asymptotická notace. Příklady technik používaných při analýze výpočetní složitosti algoritmů.
Analýza výpočetní složitosti rekurzivních algoritmů.
- Třídy složitosti. Nedeterministické algoritmy. Třídy P a NP. Redukce mezi problémy. NP-úplnost.
- Příklady některých klasických problémů z oblasti kombinatorické optimalizace. Příklady toho, kdy některé z těchto problémů jsou v P a některé NP-úplné.
- Další třídy složitosti (PSPACE, EXPTIME, EXPSPACE, L, NL, ...). Příklady úplných problémů pro jednotlivé třídy.
- Příklady technik návrhu efektivních algoritmů. Příklady použití těchto technik pro řešení kombinatorických problémů.
Greedy algoritmy a jejich souvislost s matroidy. Metoda větvení a mezí (branch and bound).
- Složitost algoritmů v průměrném případě. Amortizovaná složitost. Příklady některých pokročilejších datových struktur a analýzy složitosti operací na těchto strukturách.
- Randomizované algoritmy.
- Aproximační algoritmy. Špatně aproximovatelné problémy.
- Paralelní algoritmy: výpočetní modely pro paralelní algoritmy (PRAM), výpočetní složitost paralelních algoritmů.
- Distribuované algoritmy: výpočetní modely pro distribuované algoritmy, komunikační složitost.
- Úvod. Algoritmy a algoritmické problémy. Výpočetní modely (např. stroje RAM, Turingovy stroje, ...). Churchova-Turingova teze.
- Algoritmicky nerozhodnutelné problémy.
- Výpočetní složitost algoritmů. Asymptotická notace. Příklady technik používaných při analýze výpočetní složitosti algoritmů.
Analýza výpočetní složitosti rekurzivních algoritmů.
- Třídy složitosti. Nedeterministické algoritmy. Třídy P a NP. Redukce mezi problémy. NP-úplnost.
- Příklady některých klasických problémů z oblasti kombinatorické optimalizace. Příklady toho, kdy některé z těchto problémů jsou v P a některé NP-úplné.
- Další třídy složitosti (PSPACE, EXPTIME, EXPSPACE, L, NL, ...). Příklady úplných problémů pro jednotlivé třídy.
- Příklady technik návrhu efektivních algoritmů. Příklady použití těchto technik pro řešení kombinatorických problémů.
Greedy algoritmy a jejich souvislost s matroidy. Metoda větvení a mezí (branch and bound).
- Složitost algoritmů v průměrném případě. Amortizovaná složitost. Příklady některých pokročilejších datových struktur a analýzy složitosti operací na těchto strukturách.
- Randomizované algoritmy.
- Aproximační algoritmy. Špatně aproximovatelné problémy.
- Paralelní algoritmy: výpočetní modely pro paralelní algoritmy (PRAM), výpočetní složitost paralelních algoritmů.
- Distribuované algoritmy: výpočetní modely pro distribuované algoritmy, komunikační složitost.
Cvičení:
- Algoritmy a algoritmické problémy. Výpočetní modely (např. stroje RAM, Turingovy stroje, ...). Churchova-Turingova teze.
- Algoritmicky nerozhodnutelné problémy.
- Výpočetní složitost algoritmů. Asymptotická notace. Příklady technik používaných při analýze výpočetní složitosti algoritmů.
Analýza výpočetní složitosti rekurzivních algoritmů.
- Třídy složitosti. Nedeterministické algoritmy. Třídy P a NP. Redukce mezi problémy. NP-úplnost.
- Příklady některých klasických problémů z oblasti kombinatorické optimalizace. Příklady toho, kdy některé z těchto problémů jsou v P a některé NP-úplné.
- Další třídy složitosti (PSPACE, EXPTIME, EXPSPACE, L, NL, ...). Příklady úplných problémů pro jednotlivé třídy.
- Příklady technik návrhu efektivních algoritmů. Příklady použití těchto technik pro řešení kombinatorických problémů.
Greedy algoritmy a jejich souvislost s matroidy. Metoda větvení a mezí (branch and bound).
- Složitost algoritmů v průměrném případě. Amortizovaná složitost. Příklady některých pokročilejších datových struktur a analýzy složitosti operací na těchto strukturách.
- Randomizované algoritmy.
- Aproximační algoritmy. Špatně aproximovatelné problémy.
- Paralelní algoritmy: výpočetní modely pro paralelní algoritmy (PRAM), výpočetní složitost paralelních algoritmů.
- Distribuované algoritmy: výpočetní modely pro distribuované algoritmy, komunikační složitost.
E-learning
Povinná literatura
[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.
[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.
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.