Předmět je základní jednotka výuky, jejímž prostřednictvím si student osvojí ucelenou část souboru znalostí a dovedností, potřebnou pro zvládnutí studijního oboru/specializace. Za věcný obsah předmětu zodpovídá garant předmětu. Časovou náročnost předmětu zhruba vyjadřuje atribut předmětu rozsah kontaktní výuky. Například rozsah = 2+2  značí, že předmět bude mít týdně dvě hodiny přednášek a dvě hodiny cvičení týdně. Na závěr semestru musí vyučující provést vyhodnocení, nakolik si ten který student osvojil poznatky a dovednosti, kterých měl během výuky nabýt. Jakým způsobem toto hodnocení vyučující provedou určuje atribut způsob zakončení. U předmětu lze definovat, že předmět je zakončen pouze zápočtem(Z), klasifikovaným zápočtem(KZ), pouze zkouškou(ZK), nebo zápočtem a zkouškou(Z,ZK). Náročnost úspěšného absolvování předmětu je vyjádřena ECTS kreditními body. Výuka předmětu probíhá během semestru. Opakovaně se předmět vyučuje vždy v zimním(Z), nebo v letním(L) semestru každého akademického roku. Výjimečně může předmět být nabízen studentům v obou semestrech(Z,L). Za organizační zajištění výuky zodpovídá přiřazená katedra, která zejména vytvoří časový rozvrh předmětu a zajistí pro předmět vyučující. Někteří přednáší a zkouší, jiní vedou cvičení a udělují zápočty.
Obsahová náplň a další organizační informace, týkající se předmětu je popsána pomocí různých popisných textů(anotace, týdenní osnova, literatura, apod.)
$DODATEK_POPIS

Anotace:
The students will gain knowledge and understanding necessary deployment of combinatorial heuristics at a professional level. They will be able not only to select and implement but also to apply and evaluate heuristics for practical problems.

Osnovy přednášek:

1.		Discrete optimization, examples of practical tasks. Combinatorial problems. Algorithm complexity, problem complexity.
2.		Models of computation. The classes P and NP. Polynomial hierarchy.
3.		The notion of completeness. Complexity comparison techniques. The classes NP-complete, NP-hard and NPI.
4.		Communication and circuit complexity.
5.		The classes PO and NPO and their structure. Deterministic approximation algorithms. Classification of approximative problems. Pseudopolynomial algorithms. Randomization and randomized algorithms.
6.		Practical deployment of heuristic and exact algorithms. Experimental evaluation.
7.		State space and search space, exact methods.
8.		Local methods: heuristics.
9.		Simulated annealing.
10.		Simulated evolution: taxonomy, genetic algorithms.
11.		Advanced genetic algorithms: competent GA, fast messy GA, Stochastic optimization: models and applications. Bayesian optimization.
12.		Tabu search.
13.		Global methods, taxonomy of decomposition-based methods. Exact and heuristic global methods, the Davis-Putnam procedure seen as a global method.

Osnovy cvičení:

1.		Seminar: terminology, examples of complexity.
2.		Seminar: examples of state space.
3.		Homework consultation when required, self-study: dynamic programming revision.
4.		Solved problems session: the classes P and NP, complexity proofs, problems beyond NP.
5.		Solved problems session: completeness, reductions.
6.		Homework consultation when required.
7.		Homework consultation when required.
8.		Homework consultation when required.
9.		Midterm test.
10.		Homework consultation when required.
11.		Solved problems session: advanced heuristics, applications.
12.		Homework consultation when required.
13.		Homework consultation when required.
14.		Backup test term, evaluation.

Literatura:

1.		Arora, S. : Computational Complexity: A Modern Approach. Cambridge University Press, 2017. ISBN 978-1316612156.
2.		Hromkovič, J. : Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics 2nd Edition. Springer, 2004. ISBN 978 3540441342.
3.		Kučera, L. : Kombinatorické algoritmy. SNTL, 1993.
4.		Ausiello, G. - Crescenzi, P. - Kann, V. - Gambosi, G. - Spaccamela, A. M. : Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, 2003. ISBN 3540654313.

Požadavky:
Basic notions: algorithm, computational complexity, asymptotic complexity. Formal languages. Basic graph theory. Random variable. Boolean logic. Branch and bound algorithm. Basic dynamic programming. Practical programming in any imperative language.

Informace o předmětu a výukové materiály naleznete na https://moodle-vyuka.cvut.cz/course/view.php?id=6354

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr NIE-DBE.2023 Digital Business Engineering PP 1 NIE-SI.21 Software Engineering 2021 PP 1 NIE-TI.21 Computer Science 2021 PP 1 NIE-NPVS.21 Design and Programming of Embedded Systems 2021 PP 1 NIE-PSS.21 Computer Systems and Networks 2021 PP 1 NIE-PB.21 Computer Security 2021 PP 1