Combinatorial Optimization
| Code | Completion | Credits | Range | Language |
|---|---|---|---|---|
| NI-KOP | Z,ZK | 6 | 2P+2C | Czech |
- Garant předmětu:
- Jan Schmidt
- Lecturer:
- Jan Schmidt
- Tutor:
- Jaroslav Borecký, Petr Fišer, Robert Hülle, Jaroslav Pešek, Jan Schmidt
- Supervisor:
- Department of Digital Design
- Synopsis:
-
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.
- Requirements:
-
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.
- Syllabus of lectures:
-
1. Combinatorial problems and algorithms, course introduction.
2. Experimental evaluation of algorithms.
3. The classes P and NP. Complementary problems. Polynomial hierarchy.
4. The classes NP-complete, NP-hard and NPI.
5. The classes PO and NPO. Classes of approximative problems. Deterministic approximation algorithms.
6. State space, search space, motion in state space, local heuristics, branch and bound.
7. Randomization and randomized algorithms. Experimental deployment of parametrized heuristics.
8. Simulated annealing.
9. Simulated evolution I: taxonomy, genetic algorithms.
10. Simulated evolution II: evolution strategies, genetic programming.
11. Simulated evolution III: building blocks theory, competent GA, fast messy GA. Stochastic optimization: models and applications. Bayesian optimization.
12. Global methods, taxonomy of decomposition-based methods. Exact and heuristic global methods, the Davis-Putnam procedure seen as a global method.
13. Constraint Satisfaction Problem
- Syllabus of tutorials:
-
1. Introduction, Satisfiability Problem (SAT), Knapsack Problem.
2. Problem examples, finding configuration variables.
3. Simple SAT algorithms: evaluation on a single instance.
4. Simple SAT algorithms: evaluation on ensembles.
5. Classes P, NP, NPC, NPH, completeness, reductions.
6. State space
7. Midterm test.
8. Simulated annealing: deployment and evaluation I
9. Homework consultation when required.
10. Simulated annealing: deployment and evaluation II
11. Simulated evolution: deployment and evaluation I
12. Simulated evolution: deployment and evaluation I
13. Backup test term, evaluation.
- Study Objective:
-
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.
- Study materials:
-
1. Arora, S. : Computational Complexity: A Modern Approach. Cambridge University Press, 2017. ISBN 978-1316612156.
2. Hromkovic, 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.
- Note:
- Further information:
- https://courses.fit.cvut.cz/NI-KOP/
- Time-table for winter semester 2023/2024:
-
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
Mon Tue Wed Thu Fri - Time-table for summer semester 2023/2024:
- Time-table is not available yet
- The course is a part of the following study plans:
-
- Master specialization Computer Security, in Czech, 2020 (compulsory course in the program)
- Master specialization Design and Programming of Embedded Systems, in Czech, 2020 (compulsory course in the program)
- Master specialization Computer Systems and Networks, in Czech, 202 (compulsory course in the program)
- Master specialization Management Informatics, in Czech, 2020 (compulsory course in the program)
- Master specialization Software Engineering, in Czech, 2020 (compulsory course in the program)
- Master specialization System Programming, in Czech, version from 2020 (compulsory course in the program)
- Master specialization Web Engineering, in Czech, 2020 (compulsory course in the program)
- Master specialization Knowledge Engineering, in Czech, 2020 (compulsory course in the program)
- Master specialization Computer Science, in Czech, 2020 (compulsory course in the program)
- Mgr. programme, for the phase of study without specialisation, ver. for 2020 and higher (compulsory course in the program)
- Master specialization System Programming, in Czech, version from 2023 (compulsory course in the program)
- Master specialization Computer Science, in Czech, 2023 (compulsory course in the program)