Algorithms Complexity

Lecturer:

Tutor:

Supervisor:

Department of Cybernetics

Synopsis:

The aim of this course is to offer 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 fregment NP-complete tasks as well as the Cook´s Theorem will be explained, examples of algorithmically unsolvable problems will be giver, 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(f(x)), o(f(x))

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(f(x)), o(f(x))

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 between problems

13. Algorithmically unsolvable problems

14. Summary (spare time)

Study Objective:

Study materials:

Harel, D.: Alogorithmics: The Spirit of Computing, Addison-Wesley Inc.,

Reading MA 1992 Gruska, J.: Foundations of Computing, Int. Thompson

Computer Press, London 1997

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)