Algorithms Complexity

Lecturer:

Tutor:

Supervisor:

Department of Cybernetics

Synopsis:

The aim of this course is to get the students knowledgeable in the important problems of mathematical view onto algorithms and their complexity. Attention is paid to tasks of graph theory, which serve to show and explain the problems of task complexity and complexity classes. Heuristics for NP-complete tasks as well as the Cook´s Theorem will be explained, algorithmically unsolvable problems, etc. The seminars are devoted to deepening of the knowledge of the lectured matter.

Requirements:

Syllabus of lectures:

1. Algorithm, correctness of algorithm, time and space complexity

2. Asymptotical growth of functions, notation O, ?, ?

3. Recursive algorithms, time complexity of recursive algorithms

4. Topological ordering of vertices and edges

5. Minimal spanning tree, greedy algorithms

6. Shortest paths form a given vertex, between any pair of vertices

7. Applications of algorithms for the shortest path problem

8. Flow in networks

9. Classes P and NP

10. NP-complete problems: Travelling Salesman Problem, colourability

11. Heuristics for NP-complete problems

12. Cook's Theorem, reductions of problems

13. Algorithmically unsolvable problems

14. Summary (spare time)

Syllabus of tutorials:

1. Algorithm, correctness of algorithm, time and space complexity

2. Asymptotical growth of functions, notation O, ?, ?

3. Recursive algorithms, time complexity of recursive algorithms

4. Topological ordering of vertices and edges

5. Minimal spanning tree, greedy algorithms

6. Shortest paths form a given vertex, between any pair of vertices

7. Applications of algorithms for the shortest path problem

8. Flow in networks

9. Classes P and NP

10. NP-complete problems: Travelling Salesman Problem, colourability

11. Heuristics for NP-complete problems

12. Cook's Theorem, reductions of problems

13. Algorithmically unsolvable problems

14. Summary, (spare time)

Study Objective:

Study materials:

There is no text-book covering the course completely; any book on modern operating systems can be used. The lecturer will hint resources to particular topics.

1.

2.

3.

4.

5.

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans:

• Cybernetics and Measurements - Control Engineering- structured studies (compulsory elective course)
• Cybernetics and Measurements - Artificial Intelligence- structured studies (compulsory elective course)
• Cybernetics and Measurements - Measurement and Instrumentation Systems- structured studies (compulsory elective course)
• Cybernetics and Measurements - Aeronautical Engineering and Control Systems- structured studies (compulsory elective course)