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

Theory of Algorithms

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
AE4M01TAL Z,ZK 6 3+1
Přednášející:
Cvičící:
Předmět zajišťuje:
katedra matematiky
Anotace:

The course brings several algorithms from the theory of graphs and cryptography. Stress is put on the analysis of time complexity of the algorithms presented. Further, basics of the theory of complexity are given. Next an example of randomized algorithms is given, it is the Miller-Rabin?s algorithm. When dealing with time complexity of specific algorithms suitable data structures will be given.

Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/AE4M01TAL

Požadavky:

Logic and Graphs, Discrete Mathematics

Osnova přednášek:

1.Analyzing algorithms and problems, classifying functions by their growth rates, time complexity.

2.Basic graph algorithms, minimal spanning tree, Prim?s and Kruskal?s algorithms.

3.Algorithm for strongly connected components.

4.Matching in bipartite graphs.

5.Hungarian Algorithm.

6.Isomorphism of graphs.

7.Algorithms in cryptography, Eucleid?s Algorithm, RSA.

8.The classes of P and NP, polynomial reduction of problems.

9.NP-complete problems, examples of NP-complete problems.

10.Cook?s Theorem, reductions of NP-complete problems.

11.Heuristics for NP-complete problems, colouring.

12.Randomized algorithms, Miller-Rabin algorithm for primality testing.

13.Undecidable problems.

Osnova cvičení:

1.Basic graph algorithms, minimal spanning tree, Prim?s and Kruskal?s algorithms.

2.Algorithm for strongly connected components.

3.Hungarian Algorithm.

4.Eucleid?s Algorithm, RSA.

5.NP-complete problems, polynomial reduction of problems.

6.Vertex colouring of graphs.

7.Miller-Rabin algorithm.

Cíle studia:
Studijní materiály:

[1] Kozen, D. C.: The design and Analysis of Algorithms, Springer-Vrelag, 1991

[2] Harel, D: Algorithmics: The Spirit of Computing, Addison-Wesleyt Inc., Reading MA 1002

[3] Talbot, J., Welsh, D.: Complexity and Cryptography, Cambridge University Press, 2006

Poznámka:

Rozsah výuky v kombinované formě studia: 21p+3s

Další informace:
http://math.feld.cvut.cz/demlova/teaching/e-tal_vyuka.html
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 18. 10. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet12822304.html