460-6004/01 – Theory of Computation (TA)

Gurantor departmentDepartment of Computer ScienceCredits10
Subject guarantorprof. RNDr. Petr Jančar, CSc.Subject version guarantorprof. RNDr. Petr Jančar, CSc.
Study levelpostgraduateRequirementChoice-compulsory
YearSemesterwinter + summer
Study languageCzech
Year of introduction2010/2011Year of cancellation2021/2022
Intended for the facultiesUSP, FEIIntended for study typesDoctoral
Instruction secured by
LoginNameTuitorTeacher giving lectures
JAN59 prof. RNDr. Petr Jančar, CSc.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Examination 28+0
Part-time Examination 28+0

Subject aims expressed by acquired skills and competences

On successful completion of the course, the student - understands the notions from theory of computability and complexity - is able to design algorithms suitable for practical problems - is able to analyse complexity of algorithms and categorize problems according to their complexity - masters design and analysis of approximation, probabilistic and parallel algorithms, - is able by self-study to master and present an advanced topic in theory of algorithms

Teaching methods

Lectures
Individual consultations
Project work

Summary

The course first concisely repeats the basics of the comutability and complexity theory, which are usually covered in the master studies; an emphasis is put on the rigorous approach and deeper understanding. The course is then devoted to some advanced parts in these and further areas, including, e.g., deciding logical theories, approximation algorithms, probabilistic algorithms, parallel computation, etc.

Compulsory literature:

M.Sipser: Introduction to the Theory of Computation (2nd ed.), Thomson 2006

Recommended literature:

D. Kozen: Automata and Computability, Springer 1997 D. Kozen: Theory of Computation; Springer 2006 I. Wegener: Complexity Theory; Springer 2005 Handbook of theoretical computer science (ed. Leeuwen J.); Vol. A : Algorithms and complexity; North-Holland 1990

Way of continuous check of knowledge in the course of semester

The student writes a concise, cogent and understandable article about a selected advanced topic, which he/she presents during the course.

E-learning

Other requirements

There are not defined other requirements for student.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

The intuitive notion of algorithm and effectively computable function. Various mathematical formalizations of these notions (Turing machines, partially recursive functions). The idea of the universal algorithm. Main ideas showing the equivalence of the above formalizations, Church-Turing thesis. Halting problem, Post Correspondence problem, and further undecidable problems. Universal function, Kleene's Normal Form Theorem, recursive and recursively enumerable sets, Post's Theorem. Recursion Theorem, Rice's Theorem. Recursive reducibility. Creative sets. Decidability of logical theories. Time and space complexity of algorithms and problems. The P-NP question. NP-completeness and PSPACE-completeness. EXPTIME, EXPSPACE, provably intractable problems. Approximation algorithms, probabilistic algorithms. Parallel and distributed algorithms. Further topics (alternation, cryptography, ...).

Conditions for subject completion

Full-time form (validity from: 2013/2014 Winter semester, validity until: 2021/2022 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)		Min. number of pointsMax. počet pokusů
Examination Examination   3
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
2021/2022 (P0541D170005) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory type B study plan
2021/2022 (P0541D170005) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory type B study plan
2021/2022 (P0613D140020) Computational Science K Czech Ostrava Choice-compulsory type B study plan
2021/2022 (P0613D140020) Computational Science P Czech Ostrava Choice-compulsory type B study plan
2021/2022 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2021/2022 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2021/2022 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2021/2022 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2021/2022 (P2658) Computational Sciences (2612V078) Computational Sciences P Czech Ostrava Choice-compulsory study plan
2021/2022 (P2658) Computational Sciences (2612V078) Computational Sciences K Czech Ostrava Choice-compulsory study plan
2020/2021 (P0541D170005) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory type B study plan
2020/2021 (P0541D170005) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory type B study plan
2020/2021 (P0613D140020) Computational Science K Czech Ostrava Choice-compulsory type B study plan
2020/2021 (P0613D140020) Computational Science P Czech Ostrava Choice-compulsory type B study plan
2020/2021 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2020/2021 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2020/2021 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2020/2021 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2020/2021 (P2658) Computational Sciences (2612V078) Computational Sciences P Czech Ostrava Choice-compulsory study plan
2020/2021 (P2658) Computational Sciences (2612V078) Computational Sciences K Czech Ostrava Choice-compulsory study plan
2019/2020 (P0541D170005) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory type B study plan
2019/2020 (P0541D170005) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory type B study plan
2019/2020 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2019/2020 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2019/2020 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2019/2020 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2019/2020 (P2658) Computational Sciences (2612V078) Computational Sciences P Czech Ostrava Choice-compulsory study plan
2019/2020 (P2658) Computational Sciences (2612V078) Computational Sciences K Czech Ostrava Choice-compulsory study plan
2019/2020 (P0613D140020) Computational Science P Czech Ostrava Choice-compulsory type B study plan
2019/2020 (P0613D140020) Computational Science K Czech Ostrava Choice-compulsory type B study plan
2018/2019 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2018/2019 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2018/2019 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2018/2019 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2018/2019 (P2658) Computational Sciences (2612V078) Computational Sciences P Czech Ostrava Choice-compulsory study plan
2018/2019 (P2658) Computational Sciences (2612V078) Computational Sciences K Czech Ostrava Choice-compulsory study plan
2017/2018 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2017/2018 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2017/2018 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2017/2018 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2017/2018 (P2658) Computational Sciences (2612V078) Computational Sciences P Czech Ostrava Choice-compulsory study plan
2017/2018 (P2658) Computational Sciences (2612V078) Computational Sciences K Czech Ostrava Choice-compulsory study plan
2016/2017 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2016/2017 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2016/2017 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2016/2017 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2016/2017 (P2658) Computational Sciences (2612V078) Computational Sciences P Czech Ostrava Choice-compulsory study plan
2016/2017 (P2658) Computational Sciences (2612V078) Computational Sciences K Czech Ostrava Choice-compulsory study plan
2015/2016 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2015/2016 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2015/2016 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2015/2016 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2015/2016 (P2658) Computational Sciences (2612V078) Computational Sciences P Czech Ostrava Choice-compulsory study plan
2015/2016 (P2658) Computational Sciences (2612V078) Computational Sciences K Czech Ostrava Choice-compulsory study plan
2014/2015 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2014/2015 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2014/2015 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2014/2015 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2014/2015 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K English Ostrava Choice-compulsory study plan
2013/2014 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2013/2014 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2013/2014 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2013/2014 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2012/2013 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2012/2013 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2012/2013 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2012/2013 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2011/2012 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2011/2012 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2011/2012 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2011/2012 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2010/2011 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2010/2011 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2010/2011 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2010/2011 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2010/2011 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2010/2011 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner

Assessment of instruction

Předmět neobsahuje žádné hodnocení.