Skip to main content
Skip header
VSB-TUO ›Study ›Exchange students ›List of Exchange Courses ›Faculty of Electrical Engineering and Computer Science

Faculty of Electrical Engineering and Computer Science

ECTS Course Overview



Introduction to Theoretical Computer Science

* Exchange students do not have to consider this information when selecting suitable courses for an exchange stay.

Course Unit Code460-2005/06
Number of ECTS Credits Allocated6 ECTS credits
Type of Course Unit *Optional
Level of Course Unit *First Cycle
Year of Study *
Semester when the Course Unit is deliveredSummer Semester
Mode of DeliveryFace-to-face
Language of InstructionEnglish
Prerequisites and Co-Requisites Course succeeds to compulsory courses of previous semester
Name of Lecturer(s)Personal IDName
SAW75doc. Ing. Zdeněk Sawa, Ph.D.
Summary
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.
Learning Outcomes of the Course Unit
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.

Course Contents
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.
Recommended or Required Reading
Required Reading:
- Sawa, Z.: Introduction to Theoretical Computer Science (available on http://www.cs.vsb.cz/sawa/uti/slides/uti-en.pdf)
- doc. Ing. Zdeněk Sawa, Ph.D.: Úvod do teoretické informatiky - slidy (k dispozici na adrese http://www.cs.vsb.cz/sawa/uti/slides/uti-cz.pdf,
anglická verze na adrese http://www.cs.vsb.cz/sawa/uti/slides/uti-en.pdf)
- doc. Ing. Zdeněk Sawa, Ph.D.: Úvod do teoretické informatiky - logika a algoritmy, (k dispozici na adrese http://www.cs.vsb.cz/sawa/uti/materialy/uti-2014.02.09.pdf)
- prof. RNDr. Petr Jančar, CSc.: Úvod do teoretické informatiky - učební
text, 2007, (k dispozici na adrese http://www.cs.vsb.cz/sawa/uti/materialy/uti.pdf).
- doc. RNDr. Marie Duží, CSc.: Matematická logika, (k dispozici na adrese
http://www.cs.vsb.cz/sawa/uti/materialy/Matlogika.pdf).
Recommended Reading:
- 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.
- 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.
- 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.
- Huth, M., Ryan, M.: Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge University Press, 2004.
- Švejdar, V.: Logika - neúplnost, složitost a nutnost, Academia, 2002.
- 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.
Planned learning activities and teaching methods
Lectures, Tutorials
Assesment methods and criteria
Tasks are not Defined