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

Gurantor departmentDepartment of Computer ScienceCredits6
Subject guarantordoc. Ing. Zdeněk Sawa, Ph.D.Subject version guarantordoc. Ing. Zdeněk Sawa, Ph.D.
Study levelundergraduate or graduateRequirementCompulsory
Year2Semestersummer
Study languageEnglish
Year of introduction2015/2016Year of cancellation2018/2019
Intended for the facultiesFEIIntended for study typesBachelor
Instruction secured by
LoginNameTuitorTeacher giving lectures
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+2
Part-time Credit and Examination 10+0

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

Requirements during a semester: - A written test during a semester (for 22 points) Requirements for a credit: - To get a credit, a student must obtain from the written test at least 7 points. The exam: - The exam is of a written form. The exam consists of three parts devoted to the following areas: - introduction to logic - theory of formal languages and automata - computability and complexity It is possible to get 78 points for the exam. To pass out the exam it is necessary to get at least 10 points from each of its parts.

E-learning

Other requirements

Additional requirements are placed on the student.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

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.

Conditions for subject completion

Full-time form (validity from: 2015/2016 Winter semester, validity until: 2015/2016 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of pointsMax. počet pokusů
Credit and Examination Credit and Examination 100 (100) 51
        Credit Credit 22 (22) 12
                Test Written test 22  12
        Examination Examination 78 (78) 30 3
                Logic Written examination 26  10
                Languages and Automata Written examination 26  10
                Computability and Complexity Written examination 26  10
Mandatory attendence participation:

Show history

Conditions for subject completion and attendance at the exercises within ISP:

Show history

Occurrence in study plans

Academic yearProgrammeBranch/spec.Spec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2017/2018 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P English Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K English Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P English Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K English Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P English Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K English Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (2612R059) Mobile Technology P English Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (2612R059) Mobile Technology K English Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P English Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K English Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P English Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K English Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P English Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K English Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (2612R059) Mobile Technology P English Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (2612R059) Mobile Technology K English Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P English Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K English Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P English Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K English Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P English Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K English Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (2612R059) Mobile Technology P English Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (2612R059) Mobile Technology K English Ostrava 2 Compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner
V - ECTS - bc. 2018/2019 Full-time English Optional 401 - Study Office stu. block
V - ECTS - bc. 2017/2018 Full-time English Optional 401 - Study Office stu. block
V - ECTS - bc. 2016/2017 Full-time English Optional 401 - Study Office stu. block
V - ECTS - bc. 2015/2016 Full-time English Optional 401 - Study Office stu. block

Assessment of instruction



2016/2017 Summer
2015/2016 Summer