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

Gurantor departmentDepartment of Computer ScienceCredits5
Subject guarantordoc. Ing. Zdeněk Sawa, Ph.D.Subject version guarantordoc. Ing. Zdeněk Sawa, Ph.D.
Study levelundergraduate or graduateRequirementCompulsory
Year2Semestersummer
Study languageCzech
Year of introduction2019/2020Year of cancellation
Intended for the facultiesFEIIntended for study typesBachelor
Instruction secured by
LoginNameTuitorTeacher giving lectures
KOT06 Ing. Martin Kot, Ph.D.
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+3
Part-time Credit and Examination 0+21

Subject aims expressed by acquired skills and competences

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.

Teaching methods

Lectures
Tutorials

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.

Compulsory literature:

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

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

Way of continuous check of knowledge in the course of semester

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

E-learning

Other requirements

There are no additional requirements.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: 1. Introduction. What are the main topics of theoretical computer science (algorithms, algorithmic problems, formal languages, ...). 2. Formal languages - basic notions (alphabet, word, language). Operations on languages. Regular expressions. 3. Deterministic finite automata (DFA). Construction of DFA. Some language operations on DFA. 4. Nondeterministic finite automata (NFA). Transformation of NFA to DFA. Language operations on NFA. Relation between regular expressions and finite automata. 5. Context-free grammars and languages. 6. Pushdown automata and their relation to context-free grammars. Chomsky hierarchy. 7. Algorithmic problems. Models of computation (Turing machines and RAM machines). Church-Turing thesis. 8. Correctness of algorithms. Methods for proving correctness of algorithms. 9. Computational complexity of algorithms. Asymptotic notation. Analysis of computational complexity of algorithms (iterative and recursive). 10. General techniques used in design of algorithms - brute-force solution, divide-and-conquer, backtracking, greedy algorithms, dynamic programming. 11. Complexity of problems. Complexity classes (in particular classes P and NP). Reductions between problems. NP-complete problems. 12. Examples of NP-complete problems and reductions between problems. 13. Undecidable problems (e.g., halting problem). Tutorials: (Remark: The topics of tutorials correspond to the topics of lectures.) 1. Recalling basics of logic, set theory, relations, functions, and graph theory. 2. Operations on languages. Regular expressions. 3. Construction of deterministic finite automata (DFA). Operation on these automata. 4. Construction of nondeterministic finite automata (NFA). Transformation of NFA to DFA. Transformations between regular expressions and finite automata. 5. Construction of context-free grammars. Operations on these grammars. 6. Pushdown automata. 7. Algorithmic problems. Turing machines and RAM machines. 8. Proving correctness of algorithms. 9. Asymptotic notation. Analysis of computational complexity of algorithms. 10. Techniques of design of algorithms. 11. Complexity of problems. Complexity classes. Reductions between problems. 12. Proving NP-completeness of problems. 13. Proving undecidability of problems.

Conditions for subject completion

Part-time form (validity from: 2019/2020 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Credit and Examination Credit and Examination 100 (100) 51
        Credit Credit 30 (30) 15
                Test Written test 24  12
                Activity on tutorials Other task type 6  3
        Examination Examination 70 (70) 30
                Languages and automata Written examination 35  12
                Computability and complexity Written examination 35  12
Mandatory attendence parzicipation: obligatory participation at all tutorials, 2 apologies are accepted

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2021/2022 (B0613A140014) Computer Science TZI P Czech Ostrava 2 Compulsory study plan
2021/2022 (B0613A140014) Computer Science TZI K Czech Ostrava 2 Compulsory study plan
2020/2021 (B0613A140014) Computer Science TZI K Czech Ostrava 2 Compulsory study plan
2020/2021 (B0613A140014) Computer Science TZI P Czech Ostrava 2 Compulsory study plan
2020/2021 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2020/2021 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2020/2021 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2020/2021 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2020/2021 (B0541A170008) Computational and Applied Mathematics P Czech Ostrava 2 Compulsory study plan
2020/2021 (B0541A170008) Computational and Applied Mathematics K Czech Ostrava 2 Compulsory study plan
2019/2020 (B0541A170008) Computational and Applied Mathematics P Czech Ostrava 2 Compulsory study plan
2019/2020 (B0541A170008) Computational and Applied Mathematics K Czech Ostrava 2 Compulsory study plan
2019/2020 (B0613A140014) Computer Science TZI P Czech Ostrava 2 Compulsory study plan
2019/2020 (B0613A140014) Computer Science TZI K Czech Ostrava 2 Compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner