Problems and Algorithms
Semestr: Winter
Range: 2+2s
Completion:
Credits: 5
Programme type: Undefined
Study form:
Course language: English
Summary:
The student gains the ability to solve combinatorial problems in practice. Necessary parts of complexity theory, the theory of NP-hard problems and their approximation are presented in a simple manner, followed by the most popular class of heuristic algorithms. Practical assignments build up intuitive insight into the heuristics.
Keywords:
Combinatorial problem, time complexity, approximative algorithm, simulated annealing, genetic algorithms, global methods
Course syllabus:
1. Combinatorial problems and methods
2. Computational complexity analysis
3. State space, search methods
4. Computational models, the P and NP classes
5. The classes NP-complete and NP-hard, polynomial reduction
6. Approximative algorithms, quality evaluation
7. Local methods, typical local strategies
8. Constructive methods
9. Simple iterative methods
10. Simulated annealing
11. Simulated evolution - genetic algorithms
12. Taboo search
13. Global methods
14. Linear programming
Seminar syllabus:
Seminars marked "assignment" are devoted to individual work.
1. Demonstration of illustrative problems, introduction into algorithms. 1st assignment given.
2. Construction of asymptotic complexity bounds.
3. Examples of state space. 1st assignment due. 2nd assignment given.
4. 2nd assignment.
5. The classes P and NP, transformations, proofs of membership. 2nd assignment due, 3rd assignment given.
6. 3rd assignment.
7. Local constructive methods. 3rd assignment due. 4th assignment given.
8. Simple iterative methods.
9. 4th assignment.
10. Advanced iterative methods. Final assignment (the Travelling Salesperson Problem, TSP) given.
11. 4th assignment.
12. 4th assignment.
13. Presentation of TSP solution
14. Presentation of TSP solution
Literature:
1. Garey, M. R., Johnson, D. S.: Computers and Intractability. San Francisco, W. H. Freeman, 1979
2. Ausielo, G., et al: Complexity and Approximation. Berlin, Springer 1999