Problems and Algorithms

The course is a substitute for:

Problems and Algorithms (D36PAA)

Lecturer:

Jan Schmidt

Tutor:

Jan Schmidt

Supervisor:

Department of Computer Science and Engineering

Synopsis:

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.

Requirements:

All assignments done, active participation at the seminars. Discussion and defense of the TSP is a part of the exam.

Syllabus of lectures:

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

Syllabus of tutorials:

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

Study Objective:

Study materials:

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

Note:

Time-table for winter semester 2011/2012:

	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	room 14:30–16:00 (lecture parallel1)
Tue
Fri
Thu
Fri

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans:

• Computer Technology - Software Engineering- structured studies (compulsory course)
• Computer Technology - System Programming- structured studies (compulsory course)
• Computer Technology - Computer Graphics- structured studies (compulsory course)
• Computer Technology - Computer Network and Internet- structured studies (compulsory course)
• Computer Technology - Designing Digital Systems- structured studies (compulsory course)