Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2022/2023

Combinatorial Optimization

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
NIE-KOP Z,ZK 6 3P+1C anglicky
Přednášející:
Petr Fišer (gar.), Jan Schmidt
Cvičící:
Petr Fišer (gar.), Jan Schmidt
Předmět zajišťuje:
katedra číslicového návrhu
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.

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.

Osnova 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.

Osnova 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.

Cíle studia:

Many practical tasks are computationally infeasible. The course is about fast algorithms for such problems, both exact and heuristic. Heuristic algorithms tend to be simple to program, but difficult to configure and deploy. Their successful application requires a deeper understanding of their operation and complexity theory. A series of individual works guides the student from simple techniques to solutions of practically significant problems.

Studijní materiály:

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.

Poznámka:

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

Rozvrh na zimní semestr 2022/2023:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
místnost TH:A-1042
Fišer P.
11:00–12:30
(přednášková par. 1)
Thákurova 7 (FSv-budova A)
Hlavickova laborka
místnost TH:A-1042
Fišer P.
17:00–18:45
(přednášková par. 1
paralelka 101)

Thákurova 7 (FSv-budova A)
Hlavickova laborka
Út
St
Čt

Rozvrh na letní semestr 2022/2023:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 29. 1. 2023
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6623806.html