Tutor (for lectures and tutorials):
- doc. Ing. Zdeněk Sawa, Ph.D. (room: EA413, e-mail: zdenek.sawa@vsb.cz)
Recent information about the course Theoretical Computer Science will appear here during the semester.
The aim of the course is to introduce students to some basics of the following areas of theoretical computer science:
- theory of formal languages and automata,
- computability and complexity.
Preliminary Program of Lectures
- Introduction. Formal languages. Deterministic finite automata.
- Operations on Languages. Nondeterministic finite automata.
- Minimization of finite automata. Regular Expressions.
- Context-free grammars and languages.
- Pushdown automata. Construction of compilers.
- Algorithms and algorithmic problems. Models of computation. Church-Turing thesis.
- Asymptotic notation. Complexity of algorithms.
- Complexity of problems. Complexity classes. Classes P and NP.
- Reductions between problems. NP-complete problems.
- Class PSPACE=NPSPACE. PSPACE-complete problems. Other complexity classes.
- Algorithmically undecidable problems.
- Aproximation algorithms. Randomized algorithms.
Presentation
Topics for presentations will be published during the semester and each student will obtain an assigned topic.
To obtain a credit, it is necessary prepare the presentation in a written form and present it to a tutor. Students must show during these presentations that they understand the given topic. A particular term for the presentations will be specified during the semester.
It is possible to obtain up to 10 points for the presentation. It is necessary to obtain at least 5 points.
If some student does not obtain the necessary 5 points for his/her presentation, it is possible to do the presentation once again, however, the maximal number of points will be only 5 points in this case, while the required minimal number of points is 1 point.
Topics of presentations for the winter term 2021/22: topics.pdf
Written Test
There will be a written test during the semester. It will be possible to get up to 21 points from this test, while the minimum necessary to obtain a credit is 7 points.
The test will be written on some of tutorials. Particular date will be specified during the semester.
There will be some alternative date specified for students that due to some important reasons (e.g., illness) can not attend the written test in the regular date.
Students that do not obtain the necessary 7 points from the written test will have the possibility to obtain these points on a correcting test. However, it will be possible to obtain only a smaller number of points and it will be still necessary to obtain at least 7 point. (Points for a credit will be assigned according to the correcting test in this case.)
Activity on Tutorials
It is possible to obtain up to 7 points. The points for activity are added to the total number of obtained points but they are not required to obtain a credit.
It is possible to obtain up to 62 points for an exam. The exam will be in a written form.
The exam consists of two parts, it is possible to obtain up to 31 points from each part.
It is necessary to obtain at least 11 points from each of these two parts.
Slides from Lectures
Slides from lectures from the school year 2022/2023 will be published here during the semester.
- Lecture 1
– introduction, formal languages, operations on languages
tcs-slides-01.pdf- Lecture 2
– deterministic and nondeterministic finite automata
tcs-slides-02.pdf- Lecture 3
– regular expressions, nonregular languages
tcs-slides-03.pdf- Lecture 4
– context-free grammars
tcs-slides-04.pdf- Lecture 5
– pushdown automata
tcs-slides-05.pdf- Lecture 6
– limitations of context-free languages, closure properties of context-free languages
tcs-slides-06.pdf- Lecture 7
– Turing machines
tcs-slides-07.pdf- Lecture 8
– Random access machines (RAMs)
tcs-slides-08.pdf- Lecture 9
– Algorithms and algorithmic problems
tcs-slides-09.pdf- Lecture 10
– Undecidable problems
tcs-slides-10.pdf- Lecture 11
– Computational complexity of algorithms, asymptotic notation
tcs-slides-11.pdf- Lecture 12
– complexity classes, reductions between problems, NP-complete problems
tcs-slides-12.pdf- Lecture 13
– other complexity classes
tcs-slides-13.pdf
Exercises for tutorials
Exercises for tutorials for the school year 2022/2023 will be published during the semester:
- Tutorial 1: tcs-exercises-01.pdf
- Tutorial 2: tcs-exercises-02.pdf
- Tutorial 3: tcs-exercises-03.pdf
- Tutorial 4: tcs-exercises-04.pdf
- Tutorial 5: tcs-exercises-05.pdf
- Tutorial 6: tcs-exercises-06.pdf
- Tutorial 7: tcs-exercises-07.pdf
- Tutorial 8: tcs-exercises-08.pdf
- Tutorial 9: tcs-exercises-09.pdf
- Tutorial 10: tcs-exercises-10.pdf
- Tutorial 11: tcs-exercises-11.pdf
Animations
- Animations — animations illustrating some topics discussed in the course (in Czech)
- Sipser, M.: Introduction to the Theory of Computation, PWS Publishing Company, 1997.
- Kozen, D.: Automata and Computability, Undergraduate Text in Computer Science, Springer-Verlag, 1997.
- Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
- Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
- Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages, and Computation, (3rd edition), Addison Wesley, 2006.
- Cormen, T. H., Leiserson, R. L., Rivest, R. L., Stein, C.: Introduction to Algorithms, MIT Press, 2001.