Problems and Algorithms
Code  Completion  Credits  Range  Language 

MIPAA  Z,ZK  5  2P+1R+1C  Czech 
 Lecturer:
 Jan Schmidt (guarantor)
 Tutor:
 Petr Fišer, Jan Schmidt (guarantor), Tomáš Beneš, Jaroslav Borecký, Jiří Dostál, Karel Hynek
 Supervisor:
 Department of Digital Design
 Synopsis:

Students are able to evaluate discrete problems by complexity and by the purpose of optimisation (online tasks, multicriterial optimisation). They understand principles and properties of heuristics and exact algorithms and, therefore, are able to select, apply, and experimentally evaluate a suitable heuristics for a practical problem.
 Requirements:

The notion of complexity, asymptotic complexity bounds. Basic graph theory. Programming in any imperative language using queues, stacks, and lists.
 Syllabus of lectures:

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 NPcomplete, NPhard and NPI.
4. The classes PO and NPO and their structure. Deterministic approximation algorithms. Classification of approximative problems. Pseudopolynomial algorithms. Randomization and randomized algorithms.
5. Communication and circuit complexity
6. Practical deployment of heuristic and exact algorithms. Experimental evaluation.
7. Local methods: state space and search space, exact methods, heuristics.
8. Simulated annealing.
9. Simulated evolution: taxonomy, genetic algorithms.
10. Advanced genetic algorithms: competent GA, fast messy GA, Stochastic optimization: models and applications. Bayesian optimization.
11. Tabu search.
12. Global methods, taxonomy of decompositionbased methods. Exact and heuristic global methods, the DavisPutnam procedure seen as a global method.
13. Reserved
 Syllabus of tutorials:

1. Seminar: terminology, examples of complexity.
2. Seminar: examples of state space.
3. Homework consultation when required, selfstudy: 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.
 Study Objective:

Many practical tasks are computationally infeasible. Students will learn to distinguish tasks where the complexity grows too fast with the task size from those which are undecidable independently of size. They will learn fast algorithms for exact and, primarily, approximate solution. Some of the more advanced ones are inspired by processes in nature and sometimes referred to as softcomputing. A series of homeworks will lead students from very simple tasks to applications of advanced heuristics on a practical problem.
 Study materials:

1. Garey, M. R., Johnson, D. S. ''Computers and Intractability: A Guide to the Theory of NPCompleteness''. W. H. Freeman, 1979. ISBN 0716710455.
2. 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://moodle.fit.cvut.cz/courses/MIPAA/
 Timetable for winter semester 2019/2020:

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 Fri Thu Fri  Timetable for summer semester 2019/2020:
 Timetable is not available yet
 The course is a part of the following study plans:

 Knowledge Engineering, in Czech, Presented in Czech, for Students who Enrolled in 2015 (compulsory course in the program)
 Master Informatics, Presented in Czech, Version for Students who Enrolled in 2015 (compulsory course in the program)
 Knowledge Engineering, in Czech, Presented in Czech, Version 2016 and and 2017 (compulsory course in the program)
 Computer Security, Presented in Czech, Version 2016 to 2019 (compulsory course in the program)
 Computer Systems and Networks, Presented in Czech, Version 2016 to 2019 (compulsory course in the program)
 Design and Programming of Embedded Systems, in Czech, Version 2016 to 2019 (compulsory course in the program)
 Specialization Web and Software Engineering, in Czech, Version 2016 to 2019 (compulsory course in the program)
 Specialization Software Engineering, in Czech, Version 2016 to 2019 (compulsory course in the program)
 Specialization Web Engineering, Presented in Czech, Version 2016 to 2019 (compulsory course in the program)
 Master Informatics, Presented in Czech, Version 2016 to 2019 (compulsory course in the program)
 Specialization System Programming, Presented in Czech, Version 2016 to 2019 (compulsory course in the program)
 Specialization Computer Science, Presented in Czech, Version 20162017 (compulsory course in the program)
 Knowledge Engineering, in Czech, Presented in Czech, Version 2018 to 2019 (compulsory course in the program)