460-4115/02 – 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 graduate
Study languageEnglish
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
Combined Credit and Examination 10+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:

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

Recommended literature:

D. Kozen: Theory of computation, Springer 2006

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

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 45  20
        Examination Examination 55  6
Mandatory attendence parzicipation:

Show history
Combined 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 45  20
        Examination Examination 55  6
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2019/2020 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P English Ostrava 2 Optional study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 2 Optional study plan
2019/2020 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K English Ostrava 2 Optional study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P English Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K English Ostrava 2 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P English Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K English Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 2 Optional study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P English Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K English Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 2 Optional study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P English Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K English Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava 2 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava 2 Optional study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner