VSFS:N_VSA Algorithmic Complexity

N_VSA Algorithmic Complexity

University of Finance and Administration
Winter 2016

Extent and Intensity

2/1. 6 credit(s). Type of Completion: zk (examination).

Teacher(s)

prof. RNDr. Ondřej Čepek, Ph.D. (seminar tutor)

Guaranteed by

Timetable of Seminar Groups

N_VSA/vAPH: Fri 30. 9. 15:45–17:15 S13, 17:30–19:00 S13, Fri 14. 10. 14:00–15:30 S13, 15:45–17:15 S13, Fri 11. 11. 14:00–15:30 S13, O. Čepek

Prerequisites

Basic knowledge of mathematical analysis, discrete mathematics, and programming.

Course Enrolment Limitations

The course is offered to students of any study field.

Course objectives

Students acquire a basic overwiev of the concepts related to time and space complexity of algorithms.

Syllabus

1. Time and space complexity, asymptotic notation, examples of use. 2. Determinism and non-determinism, examples of non-deterministic algorithms. 3. Classes P and NP, examples of problems from the class NP. 4. Polynomial transformations, examples of transformations among NP problems. 5. NP-hardness and NP-completeness, examples od optimization and decision problems from these classes. 6. Cook-Levin theorem (an existence of an NP-complete decision problem). 7. Strong NP-completeness, examples. 8. Pseudopolynomial algorithms. 9. Aproximation algorithms for NP-hard optimization problems. 10. Non-aproximability, examples of non-aproximable optimization problems. 11. Probabilistic algorithms (Las Vegas and Monte Carlo). 12. Space complexity, Savitch's theorem.

Literature

Teaching methods

Lectures to cover theory, practical exercises to study examples.

Assessment methods

Written test.

Language of instruction

Czech

Further comments (probably available only in Czech)

The course can also be completed outside the examination period.
Information on the extent and intensity of the course: 10 hodin KS/semestr.