Problems and Algorithms
Code  Completion  Credits  Range  Language 

MIEPAA  Z,ZK  5  2P+1R+1C 
 Lecturer:
 Petr Fišer (guarantor)
 Tutor:
 Petr Fišer (guarantor)
 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. Combinatorial problems and and algorithms, complexity
2. P and NP classes, polynomial hierarchy of problems
3. NPC and NPH problems, Karp reduction, Turing reduction
4. PO, NPO classes, approximation algorithms, classes APX, PTAS, FPTAS
5. Communication and circuit complexity
6. Randomized algorithms. Experimental evaluation
7. Local methods. State space. Simple local heuristics
8. Simulated annealing
9. Simulated evolution  genetic algorithms
10. Simulated evolution  genetic programming
11. Tabu Search
12. Global methods
 Syllabus of tutorials:

1. Introduction, the Knapsack problem
2. Examples of problems, configuration variables
3. Consultation
4. Dynamic programming
5. Consultation
6. Consultation
7. Problem classes P, NP, NPC, NPH
8. Consultation
9. Midterm test
10. State space
11. Advanced iterative algorithms
12. Consultation
13. Corrective test, assessment
 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://moodlevyuka.cvut.cz/course/view.php?id=2207
 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:

 Computer Security, Presented in English, Version 2016 až 2020 (compulsory course in the program)
 Computer Systems and Networks, Presented in English, Version 2016 až 2020 (compulsory course in the program)
 Design and Programming of Embedded Systems, in English, Version 2016 až 2020 (compulsory course in the program)
 Specialization Software Engineering, in English, Version 2016 až 2020 (compulsory course in the program)