|
|
|
||
|
For many optimization problems it is impossible to find an optimal solution fast. In such case, it is important to
study approximation algorithms that work faster, but the solution they find is not necessarily an optimal one.
Sometimes, we also have to react to partial input without knowledge of the complete input, by building a solution
step by step. Such algorithms are called on-line. The subject of the course is the study of these two classes of
algorithms. We assume knowledge on the level of the Bc. course NDMI084 Introduction to approximation and
randomized algorithms.
Last update: IUUK (11.05.2015)
|
|
||
|
Teach the students selected techniques of design and analysis of approximation and online algorithms. Last update: IUUK (11.05.2015)
|
|
||
|
To pass the tutorials it is required to get at least a half of total points for homeworks assigned during the semester conditioned on regular attendance. If the student does not attend the tutorials regularly, two thirds of total points will be required. Due to the requirements, additional attempts to pass the tutorial are not allowed.
The exam is oral. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam. Last update: Sgall Jiří, prof. RNDr., DrSc. (04.03.2018)
|
|
||
Last update: IUUK (11.05.2015)
|
|
||
|
The exam is oral with time for written preparation. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam. Last update: Sgall Jiří, prof. RNDr., DrSc. (22.06.2019)
|
|
||
|
Techniques covered:
Problems and algorithms covered:
Last update: IUUK (11.05.2015)
|