Předmět Problems and Algorithms (MIE-PAA)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu MIE-PAA - Problems and Algorithms, Fakulta informačních technologií, České vysoké učení technické v Praze (ČVUT).

Materiál	Typ	Datum	Počet stažení

Cíl

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.

Literatura

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.

Požadavky

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

Garant

Petr Fišer

Vyučující

Petr Fišer