Obsahem předmětu jsou těžké problémy, přístupy k jejich řešení, algoritmy a související teoretické základy. Optimalizační problémy, základní pojmy, příklady problémů a jejich typy, třídy NPO, PO, NP-těžké optimalizační problémy. Aproximační algoritmy, základní pojmy, PTAS, FPTAS, důležité podtřídy třídy NPO, stabilita. Vybrané problémy a aproximační algoritmy: pokrytí množiny a jeho varianty, vrcholové pokrytí a jeho varianty, maximální řez, problém ruksaku, problém obchodního cestujícího a jeho varianty. Neaproximovatelnost: redukce na NP-těžké rozhodovací problémy, redukce na prokazatelně těžké optimalizační problémy, PCP teorém a jeho použití. Úvod do randomizovaných algoritmů. Základní pojmy, klasifikace algoritmů, randomizované optimalizační algoritmy, RPTAS, RFPTAS, příklady randomizovaných algoritmů, metody jejich návrhu. Úvod do parametrizované složitosti. Základní pojmy, parametrizace problému, problém schůdný s pevným parametrem, příkad problémů a příslušných algoritmů. Heuristiky, simulované žíhání, genetické algoritmy, přístupy, věta o schématech a základní teoretické výsledky.
|
-
Ausiello G. et al. (1999). Complexity and Approximation. Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin.
-
Hlum J., Grohe M. (2006). Parameterized Complexity Theory. Springer.
-
Hromkovič J. (2003). Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. 2nd Edition. Springer.
-
Vazirani, Vijay V. (2003). Approximation Algorithms. Springer.
|