Advanced Algorithms

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

The students will learn the most important advanced algorithms in different domains of the computer science that are not covered by modules of the Bachelor program Informatics and other modules of the Master program. They will also learn how to cope with problems that, according to the present knowledge, are not solvable optimally in polynomially bounded time.

Požadavky:

Osnova přednášek:

1. Advanced algorithms for network flows.

2. Matching: bipartite and general, minimum cost matching, parallel randomized algorithm.

3. Planar graphs: planarity conditions, planarity testing, isomorphism of planar graphs.

4. Digital signal processing: FFT and spectral compression.

5. Geometric algorithms: convex hull, Voronoi diagram, and others.

6. Streaming algorithms.

7. Primality: randomized a deterministic testing, proof of primality.

8. Approximation algorithms.

9. Approximation schemes.

10. Online algorithms.

11. General heuristic methods: simulated annealing, tabu search, genetic algorithms.

12. Specialized heuristic methods: spectral heuristics, TSP.

13. Randomized algorithms and probabilistic analysis of algorithms.

Osnova cvičení:

1. [2] Inefficiency/non-termination of the FF algorithm, hecking of the parallel matching algorithm, special cases of matchings.

2. Kuratowski theorem as a planarity testing algorithm, non-planarity of K5 and K33, planar drawing of low-connected graphs, randomized proof of non-isomorphism.

3. Fourier images of fundamental functions, convolution and FT, cosine transformation.

4. Aplications of a convex hull and Voronoi diagram and their relation.

5. Basic examples of streaming algorithms.

6. Aproximation of a robber's problem and the bin-packing.

7. Fundamentals of the spectral graph theory.

8. Examples of the probabilistic analysis of simple heuristics.

9. [5] Student reports on experimental investigation of implemented algorithms.

Cíle studia:

The goal is to give a list of the most important algorithms in different domains of computer science, to use them to illustrate general principles of the design of effective algorithms, and to show methods to cope with problems that, according to the present knowledge, are not solvable optimally in polynomially bounded time.

Studijní materiály:

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. ''Introduction to Algorithms (3d Edition)''. The MIT Press, 2009. ISBN 0262033844.

2. Kleinberg, J., Tardos, E. ''Algorithm Design''. Addison Wesley, 2005. ISBN 0321295358.

Poznámka:

Information about the course and courseware are available at https://courses.fit.cvut.cz/MI-PAL/

Další informace:

https://courses.fit.cvut.cz/MI-PAL/

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: