Gurantor department | Department of Computer Science | Credits | 10 |

Subject guarantor | prof. RNDr. Petr Jančar, CSc. | Subject version guarantor | doc. Ing. Zdeněk Sawa, Ph.D. |

Study level | postgraduate | Requirement | Choice-compulsory type B |

Year | Semester | winter + summer | |

Study language | Czech | ||

Year of introduction | 2019/2020 | Year of cancellation | |

Intended for the faculties | USP, FEI | Intended for study types | Doctoral |

Instruction secured by | |||
---|---|---|---|

Login | Name | Tuitor | Teacher giving lectures |

SAW75 | doc. Ing. Zdeněk Sawa, Ph.D. |

Extent of instruction for forms of study | ||
---|---|---|

Form of study | Way of compl. | Extent |

Full-time | Examination | 28+0 |

Combined | Examination | 28+0 |

On successful completion of the course, the student
- understands the notions from theory of computability and complexity
- is able to design algorithms suitable for practical problems
- is able to analyse complexity of algorithms and categorize problems according to their complexity
- masters design and analysis of approximation, probabilistic and parallel algorithms,
- is able by self-study to master and present an advanced topic in theory of algorithms

Lectures

Individual consultations

Project work

The course first concisely repeats the basics of the comutability and complexity theory, which are usually covered in the master studies; an emphasis is put on the rigorous approach and deeper understanding. The course is then devoted to some advanced parts in these and further areas, including, e.g., deciding logical theories, approximation algorithms, probabilistic algorithms, parallel computation, etc.

M.Sipser: Introduction to the Theory of Computation (2nd ed.), Thomson 2006

D. Kozen: Automata and Computability, Springer 1997
D. Kozen: Theory of Computation; Springer 2006
I. Wegener: Complexity Theory; Springer 2005
Handbook of theoretical computer science (ed. Leeuwen J.); Vol. A : Algorithms and complexity; North-Holland 1990

The student writes a concise, cogent and understandable article about a selected advanced topic, which he/she presents during the course.

There are not defined other requirements for student.

Subject has no prerequisities.

Subject has no co-requisities.

The intuitive notion of algorithm and effectively computable function.
Various mathematical formalizations of these notions (Turing machines, partially recursive functions).
The idea of the universal algorithm. Main ideas showing the equivalence of the above formalizations, Church-Turing thesis.
Halting problem, Post Correspondence problem, and further undecidable problems.
Universal function, Kleene's Normal Form Theorem, recursive and recursively enumerable sets, Post's Theorem.
Recursion Theorem, Rice's Theorem. Recursive reducibility. Creative sets.
Decidability of logical theories.
Time and space complexity of algorithms and problems. The P-NP question.
NP-completeness and PSPACE-completeness.
EXPTIME, EXPSPACE, provably intractable problems.
Approximation algorithms, probabilistic algorithms.
Parallel and distributed algorithms.
Further topics (alternation, cryptography, ...).

Task name | Type of task | Max. number of points
(act. for subtasks) | Min. number of points |
---|---|---|---|

Examination | Examination |

Show history

Academic year | Programme | Field of study | Spec. | Form | Study language | Tut. centre | Year | W | S | Type of duty | |
---|---|---|---|---|---|---|---|---|---|---|---|

2019/2020 | (P0613D140005) Computer Science | P | Czech | Ostrava | Choice-compulsory type B | study plan | |||||

2019/2020 | (P0613D140005) Computer Science | K | Czech | Ostrava | Choice-compulsory type B | study plan |

Block name | Academic year | Form of study | Study language | Year | W | S | Type of block | Block owner |
---|