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

Advanced algorithms

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
AE4M33PAL Z,ZK 6 2P+2C
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)
Přednášející:
Cvičící:
Předmět zajišťuje:
katedra kybernetiky
Anotace:

The advanced course of algorithms construction and analysis is dedicated to the students which have an

interest to be able to evaluate in a experienced way effective and complex algorithms.

The aim of the course is to acquaint with advanced algorithms such as advanced search and sorting algorithms,

hash tables, tree structures used in searching, text searching, syntax analysis, Internet search

algorithms principles (page-ranking), parallel algorithms.

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

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:

1. Abstract data types, signature, axioms.

2. The methods of specification and implementations of abstract data types.

3. Optimization of the basic sorting algorithms.

4. Hash tables, implementation, complexity.

5. Advanced search trees, AVL, B, Red-Black, operations on the search trees.

6. Balancing the trees implementation and the complexity of the operations.

7. Trees for multidimensional searching.

8. Structure and implementation of a lexical analyzer.

9. LL(1) grammars and transformations to LL(1) grammar.

10. Syntax tree, syntax analysis implemented via recursive descent.

11. Text search algorithms, K-M-P, B-M, Karp-Rabin, finite automaton.

12. Algorithm Page-rank, Internet search algorithms.

13. Parallel and distributed algorithms, motivation and overview.

14. Reserve.

Osnova cvičení:

1. Signature, axioms of basic ADT: queue, stack, list, array.

2. Implementation variants of ADT queue, stack, list, array.

3. Comparison of effectivity of different enhancements of QuickSort, MergeSort, HeapSort.

4. Comparison of effectivity of open and chained hashing, different hash functions.

5. Iterative and recursive processing of the AVL, B, Red-Black trees.

6. Balancing trees - practical implementations.

7. Trees for multidimensional searching.

8. Grammar of the statements and expressions of a simple language .

9. Decomposition tables, transformations to LL(1) grammars.

10. Implementation of the recursive descent.

11. Comparison of the text search algoritms on large datasets.

12. Efectivity of the data structures used in Page-rank algorithm.

13. Parallel number addition, measures of the complexity of the parallel algorithms.

14. Reserve.

Cíle studia:

Fundamental overview and skills related to the topics of

the course.^

Studijní materiály:

Sara Baase, A. van Gelder, Computer Algoritms, Addison Wesley, 2000

Poznámka:

Rozsah výuky v kombinované formě studia: 14p+6c

Další informace:
http://cw.felk.cvut.cz/doku.php/courses/ae4m33pal/start
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/predmet12823304.html