Last update: RNDr. Ondřej Pangrác, Ph.D. (14.02.2018)
This course covers techniques for design and analysis of algorithms, demonstrated on concrete
combinatorial problems. For many optimization problems it is impossible (or NP-hard) to design
algorithms that find an optimal solution fast. In such a case we study approximation algorithms that work
faster, at the cost that we find a good solution, not necessarily an optimal one. Often we use randomness
in design of algorithms, which allows to solve problems more efficiently or even
to solve problems that are otherwise intractable.
Recommended for the 3rd year of Bc. studies.
Last update: RNDr. Ondřej Pangrác, Ph.D. (14.02.2018)
Přednáška probírá středně pokročilé techniky pro návrh a analýzu algoritmů a ilustruje je na
konkrétních kombinatorických problémech. Pro mnohé optimalizační problémy je obtížné navrhnout algoritmy,
které je vyřeší optimálně a zároveň rychle (např. pro NP-úplné problémy). V takovém případě studujeme tzv.
aproximační algoritmy, které pracují rychle, a najdou řešení více či méně blízké optimálnímu řešení. Často pro
návrh algoritmů (aproximačních i jiných) používáme náhodnost, což umožňuje řešit některé úlohy efektivněji nebo
řešit úlohy jinak neřešitelné.
Doporučeno pro 3. ročník Bc. studia.
Course completion requirements -
Last update: doc. Mgr. Petr Kolman, Ph.D. (29.09.2020)
To pass the tutorials it is required to get at least a half of total points for homeworks assigned during the semester. Due to the requirements, additional attempts to pass the tutorial are excluded.
The exam is oral. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam. If university attendance is limited, the exam may be held online.
Last update: Mgr. Pavel Veselý, Ph.D. (12.10.2017)
Pro získání je zápočtu je nutné získat polovinu z celkového počtu bodů za domácí úkoly zadané během semestru. Povaha kontroly studia neumožňuje opakování zápočtu.
Zkouška je ústní. Požadavky odpovídají sylabu v míře pokryté přednáškami. Zápočet je nutnou podmínkou účasti u zkoušky.
Literature -
Last update: G_I (28.05.2012)
D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011.
J. Kleinberg, E. Tardos: Algorithm Design, Pearson, 2006.
M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis.
Requirements to the exam -
Last update: prof. RNDr. Jiří Sgall, DrSc. (22.06.2019)
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: prof. RNDr. Jiří Sgall, DrSc. (22.06.2019)
Zkouška je ústní s písemnou přípravou. Požadavky odpovídají sylabu v míře pokryté přednáškami. Zápočet je nutnou podmínkou účasti u zkoušky.
Syllabus -
Last update: doc. Mgr. Petr Kolman, Ph.D. (29.09.2020)