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

Advanced algorithms

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
BE4M33PAL Z,ZK 6 2P+2C
Korekvizita:
Safety in Electrical Engineering for a master´s degree (BEEZM)
Předmět nesmí být zapsán současně s:
Pokročilá algoritmizace (A4M33PAL)
Pokročilá algoritmizace (B4M33PAL)
Předmět je náhradou za:
Pokročilá algoritmizace (A4M33PAL)
Pokročilá algoritmizace (B4M33PAL)
Přednášející:
Daniel Průša (gar.), Marko Genyk-Berezovskyj
Cvičící:
Daniel Průša (gar.), Marko Genyk-Berezovskyj, Ihor Varha
Předmět zajišťuje:
katedra kybernetiky
Anotace:

Basic graph algorithms and graph representation. Combinatorial algorithms. Application of formal languages theory in computer science - pattern matching.

Požadavky:

Individual implementation of data types and algorithms discussed in the lectures is an important part of the exercises. Thus, capabilty of programmatic manipulation of linked data structures in some of the prevalent languages (C/C++/Java/...) is indispensable.

Osnova přednášek:

Formal and informal analysis of the memory and time complexity of all data sructures and algorithms taught is an integral part of the course, it is not expicitely listed under particular topics.

1. Asymptotic complexity of algorithms. Graphs, their properties and memory representation.

2. Minimum spanning tree. Union-Find problem.

3. Euler paths. Directed graphs: connectivity, acyclic graphs.

4. Heaps. Fibonacci heap. Heaps performance comparison.

5. Dynamic data structures. Garbage collector.

6. Generating, enumeration aand isomorphism of data structures and combinatorial objects. Permutations, combinations, variations, trees.

7. Generating other combinatorial structures: k-element subsets, Gray code, non-isomorphic graphs.

8. Search in sequences - linear and quadratic interpolation. Median search.

9. Finite automata, implementation, automaton reduction.

10. Regular expressions and text search using regular expressions.

11. Approximate text search using finite automata, dictionary automata.

12. Search in higher dimensions, K-D trees, Quadtree.

13. Search trees: B a B+; 2-3-4 a R-B trees.

14. Search trees: Trie, suffix tree, splay tree.

Osnova cvičení:

Exercises and related homeworks are devoted mostly to implementation of lecture topics. Consequently, the themes of each exercise formally correspond to those

Cíle studia:

Fundamental overview and skills related to the topics of the course.

Studijní materiály:

R. Sedgewick: Algoritmy v C, SoftPress 2003,

T. H. Cormen, C. E. Leiserson, R. L. Rievest, C. Stein: Introduction to Algorithms, 2nd ed., MIT Press, 2001

B. Melichar: Jazyky a překlady, Praha , ČVUT 1996

J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001

Poznámka:
Další informace:
http://cw.fel.cvut.cz/wiki/courses/be4m33pal/start
Rozvrh na zimní semestr 2019/2020:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St
místnost KN:E-107
Genyk-Berezovskyj M.
Průša D.

11:00–12:30
(přednášková par. 1)
Karlovo nám.
Zengerova posluchárna K1
místnost KN:E-127
Varha I.
12:45–14:15
(přednášková par. 1
paralelka 101)

Karlovo nám.
Kotkova cvičebna K4
Čt

Rozvrh na letní semestr 2019/2020:
Rozvrh není připraven
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/predmet4685106.html