460-4115/01 – Selected Topics of Theoretical Computer Science (VPTI)

Gurantor departmentDepartment of Computer ScienceCredits4
Subject guarantordoc. Ing. Zdeněk Sawa, Ph.D.Subject version guarantordoc. Ing. Zdeněk Sawa, Ph.D.
Study levelundergraduate or graduateRequirementOptional
Year2Semestersummer
Study languageCzech
Year of introduction2015/2016Year of cancellation
Intended for the facultiesFEIIntended for study typesFollow-up Master
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 14+0

Subject aims expressed by acquired skills and competences

On successful completion of the course, the student, e.g., - is able to evaluate the possible extent of using the methods of approximation and probabilistic algorithms for sloving practical problems, and is able to design, analyse and compare such algorithms. - is able to exactly explain further notions and methods in advanced areas of the theoretical background of computer science

Teaching methods

Lectures
Tutorials

Summary

In the course we deal with selected methods and results of some advanced topics in theoretical computer science, e.g. in the area of approximation algorithms, probabilistic algorithms, verification of concurrent systems.

Compulsory literature:

[1] P. Jančar: a working text for the course "Selected Topics of Theoretical Computer Science"

Recommended literature:

[2] Kozen, D.: Theory of computation, Springer 2006 [3] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009. [4] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993. [5] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003. [6] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.

Way of continuous check of knowledge in the course of semester

Every student prepares a report on a specified topic from theoretical computer science, and presents it. The course is finished with an exam. This exam has an oral 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:

Lectures: 1.-2. Approximation algorithms and the related complexity classes 3. Probabilistic algorithms and the related complexity classes 4.-5. Parallel algorithms and the related complexity classes 6.-7. Distributed algorithms; communication complexity 8. Quantum computing; DNA computing 9. Concurrent systems, Petri nets 10. Verification of systems (temporal logic, model checking) Exercises: 1. Design and analysis of concrete approximation algorithms. algoritmů. (2 sessions) 2. Design and analysis of concrete probabilistic algorithms. 3. Design and analysis of concrete parallel algorithms. (2 sessions) 4. Design and analysis of concrete distributed algorithms. (2 sessions) 5. Analysis of a selected quantum or DNA algorithm. (1 session) 6. Description and analysis of concrete concurrent systems. (1 sessions) 7. Specification of simple system properties in temporal logic and algorithms of their verification. (1 sessions)

Conditions for subject completion

Part-time form (validity from: 2015/2016 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 45  20
        Examination Examination 55  6 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.

Show history

Occurrence in study plans

Academic yearProgrammeBranch/spec.Spec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2024/2025 (N0613A140034) Computer Science TI P Czech Ostrava 2 Choice-compulsory type B study plan
2024/2025 (N0613A140034) Computer Science TI K Czech Ostrava 2 Choice-compulsory type B study plan
2024/2025 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2024/2025 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2023/2024 (N0613A140034) Computer Science TI K Czech Ostrava 2 Choice-compulsory type B study plan
2023/2024 (N0613A140034) Computer Science TI P Czech Ostrava 2 Choice-compulsory type B study plan
2023/2024 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2023/2024 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2022/2023 (N0613A140034) Computer Science TI K Czech Ostrava 2 Choice-compulsory type B study plan
2022/2023 (N0613A140034) Computer Science TI P Czech Ostrava 2 Choice-compulsory type B study plan
2022/2023 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2022/2023 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2021/2022 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2021/2022 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2020/2021 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2020/2021 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2020/2021 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2020/2021 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2019/2020 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2019/2020 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner

Assessment of instruction



2022/2023 Summer