Parameterized algorithmics analyzes the runtime in finer detail than classical complexity theory: instead of
expressing the runtime as a function of the input size only, the dependence on a parameter of the input is taken
into account. The aim is to isolate any fast growth of the runtime to a parameter, while the remaining growth of the
time is kept low. Apart from giving a deeper theoretical understanding of the complexity of a problem, this can also
lead to efficient (practical) algorithms if the parameter describes a property of the inputs, for which the parameter is
typically small.
Last update: doc. RNDr. Martin Balko, Ph.D. (11.09.2023)
Parametrizovaná výpočetní složitost analyzuje dobu běhu algoritmů podrobněji než klasická teorie složitosti:
namísto vyjádření doby běhu pouze jako funkce velikosti vstupu se bere v úvahu závislost na vhodném dalším
parametru vstupu. Cílem je, aby případný rychlý (exponenciální) růst doby běhu závisel jen na parametru, zatímco
závislost na velikosti vstupu je nízká (polynomiální). Kromě hlubšího teoretického pochopení složitosti problému to
může vést i k efektivním a praktickým algoritmům, je-li zvolený parametr pro obvyklé vstupy malý.
Course completion requirements - Czech
Last update: doc. RNDr. Jiří Fiala, Ph.D. (07.09.2023)
Osvojení látky v rozsahu syllabu a schopnost je aplikovat na úlohy z oboru.
Zápočet je podmínkou pro konání zkoušky.
Literature - Czech
Last update: doc. Mgr. Jan Kynčl, Ph.D. (30.04.2019)
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer 2015, ISBN 978-3-319-21274-6
Syllabus -
Last update: doc. Andreas Emil Feldmann, Dr. (24.09.2020)
kernelization
bounded search trees
iterative compression
treewidth
the W-hierarchy
the exponential-time hypothesis
parameterized approximation
Last update: doc. RNDr. Jiří Fiala, Ph.D. (07.09.2023)