456-0335/02 – Selected Topics of Theoretical Computer Science (VPTI)
| Gurantor department | Department of Computer Science | Credits | 6 |
| Subject guarantor | prof. RNDr. Petr Jančar, CSc. | Subject version guarantor | prof. RNDr. Petr Jančar, CSc. |
| Study level | undergraduate or graduate | Requirement | Optional |
| Year | 3 | Semester | winter |
| | Study language | Czech |
| Year of introduction | 2006/2007 | Year of cancellation | 2009/2010 |
| Intended for the faculties | FEI | Intended for study types | Follow-up Master |
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 solving 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
Project work
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
Recommended literature:
Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela, Protasi: Complexity
and Approximation; Springer 1999
Clarke, Grumberg, Peled: Model Checking, MIT Press 1999
T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms; The MIT Press,
1990
Gibbons, Rytter: Efficient parallel algorithms; 1988, Cambridge Univ.Press,
J.Gruska: Foundation of Computing. International Thomson Computer Press 1997.
Gruska, Jozef: Quantum Computing, Mc Graw Hill 1999
Hromkovič J.: Communication complexity and parallel computing; Springer 1997
Lynch N.A.: Distributed Algorithms; Morgan Kaufmann 1996
Reisig, Rosenberg (eds.): Lectures on Petri nets I, II, Springer 1998
M. Sipser: Introduction to the Theory of Computation; PWS 1997
Way of continuous check of knowledge in the course of semester
E-learning
Other requirements
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)
Projects:
Individual study and written elaboration of a given topic,
which usually includes oral presentation.
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction