460-4065/04 – 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 graduateRequirementCompulsory
Year2Semesterwinter
Study languageEnglish
Year of introduction2022/2023Year 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
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

There will be a written test during a semester. Every students also prepares a report on a selected topic from theoretical computer science during semester and presents it. The course is finished with an exam. This exam has a written form.

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:

1. Introduction. Models of computation (Turing machines, random-access machines, ...), recalling computational complexity of algorithms. 2. Complexity classes. Classes P and NP, reduction between problems, NP-completeness, classical NP-complete problems. 3. Other complexity classes - PSPACE, EXPTIME, EXPSPACE, polynomial hierarchy. 4. Undecidable problems, Rice's theorem. 5. Advanced techniques for analysis and design of algorithms: amortized complexity, average-case complexity of algorithms (probabilistic analysis). 6. Randomized algorithm, approximation algorithms. 7. Computational complexity of parallel algorithms: computational models for parallel algorithms (PRAM). 8. Analysis of computational complexity of parallel algorithms, class NC, correspondence with circuits (circuit complexity). 9. Distributed algorithms: models of computation for distributed algorithms, communication complexity. 10. Kolmogorov complexity. 11. Semantics of programming languages: formal descriptions of semantics (operational semantics, denotational semantics). 12. Methods of proving correctness of programs, Hoare logic. 13. Quantum computing.

Conditions for subject completion

Full-time form (validity from: 2022/2023 Winter 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 35 (35) 15
                Written test Written test 20  10
                Presentation Other task type 15  1
        Examination Examination 65  25 3
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
2024/2025 (N0613A140035) Computer Science INF P English Ostrava 2 Compulsory study plan
2023/2024 (N0613A140035) Computer Science INF P English Ostrava 2 Compulsory study plan
2023/2024 (N2647) Information and Communication Technology (2612T059) Mobile Technology P English Ostrava 1 Optional study plan
2022/2023 (N0613A140035) Computer Science INF P English Ostrava 2 Compulsory study plan
2022/2023 (N2647) Information and Communication Technology (2612T059) Mobile Technology P English Ostrava 1 Optional 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í.