460-2005/04 – Introduction to Theoretical Computer Science (UTI)

A student understands the basic terms of theoretical computer science, and can use them in programming. Moreover, the subject gives necessary background for further study of computer science at higher levels.

The subject is an indroductory course of some basic areas of theoretical computer science. Students get acquainted with essentials of logic, formal languages, automata, and computational complexity, together with some of their applications for solving problems in programming. In particular, students will learn essentials of propositional and predicate logic. They will be able to formalize propositions in terms of these logics and to use some of methods of logical deduction. They will learn about the use of finite automata, regular expressions and context-free grammars in the construction of compilers (in lexical and syntax analysis) and also for searching in text data. Students will learn some basics of the theory of computation and of the complexity theory. They will be able to analyze the computational complexity of algorithms and to use the asymptotic notation. Also the computational complexity of algorithmic problems and complexity classes will be mentioned briefly. Students will learn that some problems are computationally undecidable and how this can be proved.

- 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. - Huth, M., Ryan, M.: Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge University Press, 2004.- Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993. - Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison Wesley, 2006. - Gruska, J.: Foundation of Computing. International Thomson Computer Press, 1997. - Suppes, P.: Introduction to Logic, Dover Publications, 1999. - Tarski, A.: Introduction to Logic and to the Methodology of Deductive Sciences, Dover Publications, 1995. - Devlin, K.: Introduction to Mathematical Thinking, Keith Devlin, 2012.

There will be one bigger written test during a semester, together will several shorter tests. The course is finished with an exam (of the written form).