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

Gurantor departmentDepartment of Computer ScienceCredits6
Subject guarantorprof. RNDr. Petr Jančar, CSc.Subject version guarantorprof. RNDr. Petr Jančar, CSc.
Study levelundergraduate or graduateRequirementOptional
Year3Semesterwinter
Study languageCzech
Year of introduction2006/2007Year of cancellation2009/2010
Intended for the facultiesFEIIntended for study typesFollow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
JAN59 prof. RNDr. Petr Jančar, CSc.
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 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 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

Full-time form (validity from: 2006/2007 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of pointsMax. počet pokusů
Exercises evaluation and Examination Credit and Examination 100 (100) 51 3
        Exercises evaluation Credit 30 (30) 15 1
                Projekt Project 30  15 1
        Examination Examination 70  25 3
Mandatory attendence participation:

Show history

Conditions for subject completion and attendance at the exercises within ISP:

Show history

Occurrence in study plans

Academic yearProgrammeBranch/spec.Spec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2009/2010 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2009/2010 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2009/2010 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Optional study plan
2008/2009 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Optional study plan
2008/2009 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2008/2009 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2008/2009 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Optional study plan
2007/2008 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Optional study plan
2007/2008 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Optional study plan
2007/2008 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2007/2008 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2006/2007 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Optional study plan
2006/2007 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Optional study plan
2006/2007 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2006/2007 (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



2009/2010 Winter