|
Lecturer(s)
|
-
Jančar Petr, prof. RNDr. CSc.
|
|
Course content
|
The course deals with hard algorithmic problems, methods and algorithms for their solving, and the corresponding theoretical background. Optimization problems, basic notions, examples, the classes NPO, PO, NP-hard optimization problems. Approximation algorithms, basic notions, PTAS, FPTAS, and other important subclasses of NPO, stability. Selected problems and approximation algorithms: set cover and its variants, vertex cover, maximal cut, knapsack problem, travelling salesman problem. Non-approximability: reduction from NP-hard optimization problems, reduction from provably hard optimization problems, PCP theorem and its application. Introduction to randomized algorithms. Basic notions, classification of algorithms, randomized optimization algorithms, RPTAS, RFPTAS, examples of randomized algorithms, methods of their design. Introduction to parameterized complexity. Basic notions, problem parameterization, fixed parameter tractability, example problems and respective algorithms. Heuristics, simulated annealing, genetic algorithms, schema theorem and basic theoretical results.
|
|
Learning activities and teaching methods
|
|
Dialogic Lecture (Discussion, Dialog, Brainstorming), Work with Text (with Book, Textbook)
|
|
Learning outcomes
|
Students get familiar with algorithms for hard problems, with respective methods and theoretical background.
1. Knowledge Describe and thoroughly understand the principles of solving hard algorithmic problems.
|
|
Prerequisites
|
Students are assumed to know the basic parts of computabiliy and complexity from bachelor and master studies (decision problems, P, NP, and other complexity classes, NP-completeness).
|
|
Assessment methods and criteria
|
Oral exam
Completing the assignments. Passing the exam.
|
|
Recommended literature
|
-
Downey R.G., Fellows M.R. (1999). Parameterized Complexity. Springer.
-
Hromkovič J. (2003). Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics.. Springer.
-
Korte B., Vygen J. (2018). Combinatorial Optimization (Theory and Algorithms). Springer.
-
Kučera, L. (1989). Kombinatorické algoritmy. SNTL Praha.
|