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

Gurantor departmentDepartment of Computer ScienceCredits6
Subject guarantorprof. RNDr. Marie Duží, CSc.Subject version guarantorprof. RNDr. Marie Duží, CSc.
Study levelundergraduate or graduateRequirementOptional
Year1Semesterwinter
Study languageCzech
Year of introduction2015/2016Year of cancellation
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
Combined 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:

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

Recommended literature:

- Michael Sipser: Introduction to the Theory of Computation, Thomson 2006 - T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms; The MIT Press, 1990

Way of continuous check of knowledge in the course of semester

E-learning

Další požadavky na studenta

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)
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 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
                první část Written test 31  11
                druhá část Written test 31  11
Mandatory attendence parzicipation: 80% attendance at the exercises

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
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