Complexity and Combinatorical Algorithms

Lecturer:

Marie Demlová (gar.)

Tutor:

Marie Demlová (gar.)

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:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer 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
Tue
Fri
Thu	roomZ4:B2-326 Demlová M. 11:00–12:30 (lecture parallel1) Zikova ulice Konzultační místnostroomZ4:B2-326 Demlová M. 12:45–13:30 (parallel nr.1) Zikova ulice Konzultační místnost
Fri

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)