Problems and Algorithms

Semestr: Summer

Range: 3+2s

Completion:

Credits: 6

Programme type: Undefined

Study form:

Course language:

Summary:

Many seemingly simple tasks cannot be solved using computers, because the time required would be longer than the life time of the machine. The course tells how to recognize such tasks and how to devise practically applicable methods for their solution. The mathematics used is minimised. Emphasis is put on methods applicable in engineering practice and on links and similarities of the methods.

Keywords:

Combinatorial problem, time complexity, approximative algorithm, simulated annealing, genetic algorithms, global methods

Course syllabus:

1. Combinatorial problems and methods of their solution
2. Algorithm complexity
3. State space metaphor, exhaustive search
4. Systematic state space search
5. Computation models, P and NP problem class
6. NP-complete and NP-hard problems, polynomial reduction
7. Quality measures of approximate methods
8. Local constructive methods
9. Local iterative methods
10. Simulated annealing
11. Simulated evolution
12. Tabu search
13. Global methods: principle, typical strategies
14. Integer and 0-1 linear programming, relaxation

Seminar syllabus:

1. Typical combinatorial problems
2. Asymptotic complexity notation
3. Search implementation
4. Geometric manipulations
5. Typical P-class problems
6. Polynomial reduction - typical cases
7. Approximative methods and maximum error estimation
8. Local methods, semestral project
9. Iterative methods
10. Simulated annealing, simulated evolution
11. Global methods
12. Proglem transformation to integer linear program
13. Dynamic programming
14. Semestral project - evaluation

Literature:

[1] Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H.Freeman, San Francisco 1979

Examiners:

Lecturers:

Instructors: