Complexity and Combinatorical Algorithms

Garant předmětu:

Lecturer:

Tutor:

Supervisor:

Department of Mathematics

Synopsis:

Time and space complexity of algorithms. P and NP problems and their solutions: exact solutions, heuristics, approximation schemes, probabilistic algorithm. Equivalences of problems.

Requirements:

Syllabus of lectures:

Syllabus of tutorials:

Study Objective:

Study materials:

1. G. Ausiello, P. Croscenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi: Complexity and Approximztion Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999.

2. Jozef Gruska: Foundations of Computing. International Thomson Computer Press, 1997.

Note:

Further information:

http://math.feld.cvut.cz/demlova/teaching/kas.html

No time-table has been prepared for this course

The course is a part of the following study plans:

• Doctoral studies, daily studies (compulsory elective course)
• Doctoral studies, combined studies (compulsory elective course)
• Doctoral studies, structured daily studies (compulsory elective course)
• Doctoral studies, structured combined studies (compulsory elective course)