|
|
|
||
Last update: T_KTI (20.04.2004)
|
|
||
Last update: T_KTI (23.05.2008)
Naučit základy z teorie složitosti algoritmů, včetně NP-úplnosti a převoditelnosti. |
|
||
Last update: prof. RNDr. Ondřej Čepek, Ph.D. (08.04.2004)
L. Kučera: Kombinatorické algoritmy J. Plesník: Grafové algoritmy Cormen, Leiserson, Rivest : Introduction to algorithms, Mc Graw Hill 1990 Kozen : Design and analysis of algorithms, Springer-Verlag 1992 Tarjan : Data structures and network algorithms, SIAM, 1983 Garey, Johnson : Computers and intractability - a guide to the theory of NP-completeness, W.H.Freeman 1978 |
|
||
Last update: T_KTI (20.04.2004)
1. Time complexity of algorithms, asymptotic notation. 2. Divide and conquer algorithms (linear time median algorithm, Strassen's matrix multiplication), methods for solving recursive equations which describe the complexity of such algorithms. 3. Greedy algorithms on weighted matriods, their applications (minimum spanning tree, scheduling problems). 4. Graph algorithms based on DFS and BFS. 5. Lower bounds for time complexity of problems, decision trees, lower bound for sorting by comparisons. 6. Amortized complexity, binomial and Fibonacci heaps and their application in Dijkstra's algorithm. 7. Formal definitions of classes P and NP, polynomial reducibility among decision problems, NP-completeness. 8. Pseudopolynomial algorithms and strong NP-completeness. 9. Counting problems, class #P, #P-completeness. 10.Approximations of NP-hard problems, completely polynomial approximation schemes. |