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
prof. RNDr. Ondřej Čepek, Ph.D.
Department of Computer Science and Mathematics – Departments – University of Finance and Administration
Contact Person: Ing. Barbora Ptáčková
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
  • Michal Černý. Výpočty. Třídílná monografie vydaná VŠE.
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.
The course is also listed under the following terms Winter 2014, Winter 2015, Winter 2017, Winter 2018, Winter 2019, Winter 2020, Winter 2021, Winter 2022, Winter 2023.
  • Enrolment Statistics (Winter 2016, recent)
  • Permalink: https://is.vsfs.cz/course/vsfs/winter2016/N_VSA