[1] Sawa, Z.: Theory of algorithms (slides for the course), VŠB-TU, Ostrava, 2025 (available on the web-page of the course).
[2] Michael Sipser: Introduction to the Theory of Computation, Thomson 2006.
[3] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
Theory of Algorithms
| Language of instruction | angličtina, čeština |
|---|---|
| Code | 460-4167 |
| Abbreviation | TA |
| Course title | Theory of Algorithms |
| Coordinating department | Department of Computer Science |
| Course coordinator | doc. Ing. Zdeněk Sawa, Ph.D. |
Summary
The main topic of the course is a study of algorithms from theoretical point of view. It gives a general overview of theoretical results in this area.
It starts with discussing questions like what is an algorithm and algorithmic problem. Several examples of models of computation are shown, together with ways how they can simulate each other. Further, questions concerning computability and algorithmic decidability are studied. It is shown that there exist many problems that are algorithmically undecidable.
Next topic are questions dealing with computational complexity. Some more advanced approaches to analysis of computational complexity are discussed, such as for example analysis of recursive algorithms, amortized analysis, and analysis of complexity in average case.
There is also studied computational complexity of problems and different complexity classes. NP-complete problems have a rather prominent role here but some other complexity classes are also discussed.
One of topics are also techniques used in design of efficient algorithms.
Some specific types of algorithms are also studied, like for example randomized and approximation algorithms.
Also parallel and distributed algorithms are studied in detail, and analysis and design of such algorithms is discussed.
Results of learning:
- To understand what the computational complexity is, and be able to analyse this complexity.
- Understand that some problems can be algorithmically undecidable, and those that are decidable can have different computational complexity.
- To know some basic complexity classes.
- To know some basic techniques that are often used in design efficient algorithms.
- To understand notions such as approximation algorithms, randomized algorithms, and be able to evaluate how efficient they are when used in practice.
- To know some techniques used in the design of parallel and distributed algorithms and be able to analyze computational complexity of such algorithms.
It starts with discussing questions like what is an algorithm and algorithmic problem. Several examples of models of computation are shown, together with ways how they can simulate each other. Further, questions concerning computability and algorithmic decidability are studied. It is shown that there exist many problems that are algorithmically undecidable.
Next topic are questions dealing with computational complexity. Some more advanced approaches to analysis of computational complexity are discussed, such as for example analysis of recursive algorithms, amortized analysis, and analysis of complexity in average case.
There is also studied computational complexity of problems and different complexity classes. NP-complete problems have a rather prominent role here but some other complexity classes are also discussed.
One of topics are also techniques used in design of efficient algorithms.
Some specific types of algorithms are also studied, like for example randomized and approximation algorithms.
Also parallel and distributed algorithms are studied in detail, and analysis and design of such algorithms is discussed.
Results of learning:
- To understand what the computational complexity is, and be able to analyse this complexity.
- Understand that some problems can be algorithmically undecidable, and those that are decidable can have different computational complexity.
- To know some basic complexity classes.
- To know some basic techniques that are often used in design efficient algorithms.
- To understand notions such as approximation algorithms, randomized algorithms, and be able to evaluate how efficient they are when used in practice.
- To know some techniques used in the design of parallel and distributed algorithms and be able to analyze computational complexity of such algorithms.
Literature
Advised literature
[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.