460-4065/01 – Theoretical Computer Science (TI)

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 graduateRequirementOptional
Year1Semesterwinter
Study languageCzech
Year of introduction2015/2016Year of cancellation2022/2023
Intended for the facultiesFEIIntended for study typesFollow-up Master
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 3+3
Part-time Credit and Examination 15+0

Subject aims expressed by acquired skills and competences

On successful completion of the course, the student - is able to evaluate the possible extent of using the methods of finite automata, context-free grammars etc. by solving concrete practical problems, and is able to design, analyse and compare the respective solutions - is able to analyse computational complexity of practical problems, and to design algorithms for their solution - understands the notions like approximation algorithms, probabilistic algorithms, etc. and can evaluate the possibilities of their use in concrete practical situations

Teaching methods

Lectures
Tutorials

Summary

The course extends the theoretical background for computer science gained in bachelor studies, in particular in the areas of automata, languages, computability and complexity.

Compulsory literature:

[1] Michael Sipser: Introduction to the Theory of Computation, Thomson 2006

Recommended literature:

[2] Kozen, D.: Automata and Computability, Undergraduate Text in Computer Science, Springer-Verlag, 1997. [3] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009. [4] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993. [5] Kozen, D.: Theory of computation, Springer 2006. [6] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001. [7] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003. [8] Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages, and Computation, (3rd edition), Addison Wesley, 2006.

Way of continuous check of knowledge in the course of semester

E-learning

Other requirements

No additional requirements are placed on students.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: 1. Course overview. Recalling basic set theory notions, equivalence relations and orders, graphs, formalisms of propositional and predicate logics, proofs by induction and by contradiction. (All these notions and methods will be used during the whole course.) 2. Formal languages, operations on languages, regular expressions as language representations, a pattern-search algorithm presented as (deterministic) finite automaton. Modular design of finite automata (FA). 3. Deterministic and nondeterministic finite automata, operations with finite automata, transforming nondeterministic FA to deterministic ones, constructing an FA to a given regular expression (RE). 4. Minimization of DFA, the canonical form, automata isomorphism. FA and RE define the same class, so called regular languages. Characterizations of regular languages enabling to show non-regularity. 5. Context-free grammars, their (un)ambiguity, using for specifications of (fragments of) programming languages. (Nondeterministic) pushdown automata (PDA). Syntactic analysis (by recursive descent). 6. Context-free languages and their subclass defined by deterministic PDA. A basic compiler (constructing an FA to a given RE). 7. Non-context-free languages, Chomsky hierarchy. Formal languages as computational problems. The notion of algorithms, computational models (Turing machine, RAM). 8. Church-Turing thesis. Universal machine. (Algorithmic) undecidability, the halting problem, reductions among problems. Rice's Theorem (each nontrivial input/output property of programs is undecidable). 9. Computational complexity of algorithms, general methods of designing polynomial algorithms: "clever" search, the "divide-and-conquer" method, greedy algorithms for optimization problems, dynamic programming. 10. Computational complexity of problems, complexity classes, polynomial reducibility. Problem SAT (satisfiability of boolean formulas) and nondeterministic polynomial algorithms. Class NPTIME. NP-completeness. 11. Class PSPACE=NPSPACE, PSPACE-complete problems, higher complexity classes. 12. Approximation algorithms, i.e., polynomial algorithms approximating optimal solutions of optimization problems. (Non)approximability of concrete problems. 13. Randomized algorithms, e.g. for primality, which is a basis of cryptographic algorithms. 14. Examples of parallel algorithms and of non-parallelizable (inherently sequential) problems. Exercises: The topics of relevant lectures are subjecy of concrete exercises.

Conditions for subject completion

Full-time form (validity from: 2015/2016 Winter semester, validity until: 2022/2023 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 38 (38) 8
                referát Other task type 10  1
                záp. písemka Written test 21  7
                aktivita na cvičení Other task type 7  0
        Examination Examination 62 (62) 25 3
                první část Written test 31  11
                druhá část Written test 31  11
Mandatory attendence participation: Attendance on exercises is mandatory and it is examined. The guarantor of the course will inform students about the extent of the mandatory attendance at the beginning of a semester.

Show history

Conditions for subject completion and attendance at the exercises within ISP: Completion of all mandatory tasks within individually agreed deadlines. A student will have an agreement on the extent of attendance on exercises at the beginning of a semester.

Show history

Occurrence in study plans

Academic yearProgrammeBranch/spec.Spec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2022/2023 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2022/2023 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2021/2022 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 1 Optional study plan
2021/2022 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 1 Optional study plan
2021/2022 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2021/2022 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2020/2021 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2020/2021 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 1 Optional study plan
2020/2021 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2020/2021 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 1 Optional study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2019/2020 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 1 Optional study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2019/2020 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 1 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2018/2019 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 1 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2018/2019 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 1 Optional study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2017/2018 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 1 Optional study plan
2017/2018 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 1 Optional study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2016/2017 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 1 Optional study plan
2016/2017 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 1 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 1 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 1 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner

Assessment of instruction



2022/2023 Winter
2021/2022 Winter
2020/2021 Winter
2019/2020 Winter
2018/2019 Winter
2017/2018 Winter
2016/2017 Winter
2015/2016 Winter