ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2018/2019

# Problems and Algorithms

Kód Zakončení Kredity Rozsah Jazyk výuky
MIE-PAA Z,ZK 5 2+2
Přednášející:
Petr Fišer (gar.)
Cvičící:
Petr Fišer (gar.)
Předmět zajišťuje:
katedra číslicového návrhu
Anotace:

Students are able to evaluate discrete problems by complexity and by the purpose of optimisation (on-line tasks, multicriterial optimisation). They understand principles and properties of heuristics and exact algorithms and, therefore, are able to select, apply, and experimentally evaluate a suitable heuristics for a practical problem.

The notion of complexity, asymptotic complexity bounds. Basic graph theory. Programming in any imperative language using queues, stacks, and lists.

Osnova přednášek:

1. Combinatorial problems and and algorithms, complexity

2. P and NP classes, polynomial hierarchy of problems

3. NPC and NPH problems, Karp reduction, Turing reduction

4. PO, NPO classes, approximation algorithms, classes APX, PTAS, FPTAS

5. Communication and circuit complexity

6. Randomized algorithms. Experimental evaluation

7. Local methods. State space. Simple local heuristics

8. Simulated annealing

9. Simulated evolution - genetic algorithms

10. Simulated evolution - genetic programming

11. Tabu Search

12. Global methods

13. Linear programming - simplex method

Osnova cvičení:

1. Introduction, the Knapsack problem

2. Examples of problems, configuration variables

3. Consultation

4. Dynamic programming

5. Consultation

6. Consultation

7. Problem classes P, NP, NPC, NPH

8. Consultation

9. Mid-term test

10. State space

12. Consultation

13. Corrective test, assessment

Cíle studia:

Many practical tasks are computationally infeasible. Students will learn to distinguish tasks where the complexity grows too fast with the task size from those which are undecidable independently of size. They will learn fast algorithms for exact and, primarily, approximate solution. Some of the more advanced ones are inspired by processes in nature and sometimes referred to as softcomputing. A series of homeworks will lead students from very simple tasks to applications of advanced heuristics on a practical problem.

Studijní materiály:

1. Garey, M. R., Johnson, D. S. ''Computers and Intractability: A Guide to the Theory of NP-Completeness''. W. H. Freeman, 1979. ISBN 0716710455.

2. Ausiello, G., Crescenzi, P., Kann, V., Gambosi, G., Spaccamela, A. M. ''Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties''. Springer, 2003. ISBN 3540654313.

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://moodle.fit.cvut.cz/courses/MIE-PAA/