Terminated in academic year 2018/2019

Introduction to Theoretical Computer Science

Type of study	Bachelor
Language of instruction	Czech
Code	460-2005/01
Abbreviation	UTI
Course title	Introduction to Theoretical Computer Science
Credits	6
Coordinating department	Department of Computer Science
Course coordinator	doc. Ing. Zdeněk Sawa, Ph.D.

Subject syllabus

Lectures:
- Introduction. Logic. Proofs. Logical connectives.
- Other logical connectives. Syntax and semantics in logic.
- Table method. Equivalent transformations. Predicate logic.
- Quantifiers. Naive set theory.
- Formal languages - basic notions (an alphabet, a word, a language). Operations
on languages. Finite automata.
- Construction of finite automata. Nondeterinistic finite automata.
- Transformation of nondeterministic finite automata to deterministic.
Regular expressions.
- Context-free grammar and languages.
- Algorithmic problems. Models of computation (Turing machines and RAM machines).
- Asymptotic notation. Complexity of algorithms.
- Complexity of problems. Complexity classes. Reductions between problems. NP-complete
problems.
- Algorithmically undecidable problems.

Tutorials:
- Recalling of basics of the set theory, relations, functions and the graph theory.
- Propositional and predicate logic.
- Analysis of sentences of a natural language in the language of propositional and predicate logic.
- Deduction of consequences. Set theoretical / semantic proofs.
- Resolution method.
- Operations with languages.
- Construction of finite automata.
- Transformation of nondeterministic automata to deterministic.
- Regular expressions.
- Context-free grammars.
- Turing machines and RAM machines.
- Asymptotic notation. Complexity of algorithms.
- Complexity of problems. Complexity classes.

Literature

- Sawa, Z.: Introduction to Theoretical Computer Science (available on http://www.cs.vsb.cz/sawa/uti/slides/uti-en.pdf)

Advised literature

- 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.

back to search page