|
Vyučující
|
-
Jančar Petr, prof. RNDr. CSc.
|
|
Obsah předmětu
|
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říklady problémů a příslušných algoritmů. Heuristiky, simulované žíhání, genetické algoritmy, věta o schématech a základní teoretické výsledky.
|
|
Studijní aktivity a metody výuky
|
|
Dialogická (diskuze, rozhovor, brainstorming), Metody práce s textem (učebnicí, knihou)
|
|
Výstupy z učení
|
Studenti se seznámí s algoritmy pro těžké problémy, s příslušnými metodami a teoretickými základy.
1. Znalost Popsat a důkladně pochopit principy řešení algoritmicky těžkých problémů.
|
|
Předpoklady
|
Předpokládá se znalost základních partií vyčíslitelnosti a složitosti na úrovni kurzů z bakalářské a magisterské etapy (rozhodovací problémy, P, NP a další třídy složitosti, NP-úplnost).
|
|
Hodnoticí metody a kritéria
|
Ústní zkouška
Plnění zadaných úkolů. Složení zkoušky.
|
|
Doporučená literatura
|
-
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.
|