456-0335/01 – Selected Topics of Theoretical Computer Science (VPTI)

Gurantor departmentDepartment of Computer ScienceCredits5
Subject guarantorprof. RNDr. Petr Jančar, CSc.Subject version guarantorprof. RNDr. Petr Jančar, CSc.
Study levelundergraduate or graduateRequirementChoice-compulsory
Year3Semesterwinter
Study languageCzech
Year of introduction2003/2004Year of cancellation2006/2007
Intended for the facultiesFEIIntended for study typesMaster
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2
Combined Credit and Examination 2+2

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

Další požadavky na studenta

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) Projects: Individual study and written elaboration of a given topic, which usually includes oral presentation.

Conditions for subject completion

Combined form (validity from: 1960/1961 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (145) 51
        Examination Examination 100  0
        Exercises evaluation Credit 45  0
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2005/2006 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Optional study plan
2005/2006 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Optional study plan
2004/2005 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Choice-compulsory study plan
2004/2005 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Choice-compulsory study plan
2003/2004 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Choice-compulsory study plan
2003/2004 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner