Problems and Algorithms

The course is a substitute for:

Problems and Algorithms (XE36PAA)

Lecturer:

Tutor:

Supervisor:

Department of Computer Science and Engineering

Synopsis:

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.

Requirements:

http://service.felk.cvut.cz/courses/E36PAA

Syllabus of lectures:

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

Syllabus of tutorials:

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

Study Objective:

Study materials:

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

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: