460-4043/01 – 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
Year2Semesterwinter
Study languageCzech
Year of introduction2010/2011Year of cancellation2014/2015
Intended for the facultiesFEIIntended for study typesFollow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
JAN59 prof. RNDr. Petr Jančar, CSc.
MEC059 Ing. Ondřej Meca, 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 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
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 "Selected Topics of Theoretical Computer Science"

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

Additional requirements are placed on the student.

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: 2010/2011 Winter semester, validity until: 2014/2015 Summer 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
        Exercises evaluation Credit 30 (30) 15
                Report Other task type 30  15
        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
2014/2015 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2014/2015 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2014/2015 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2014/2015 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2013/2014 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2013/2014 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2013/2014 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2013/2014 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2012/2013 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2012/2013 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2012/2013 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2012/2013 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2011/2012 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2011/2012 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2010/2011 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2010/2011 (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

Předmět neobsahuje žádné hodnocení.