Popis předmětu - AE4M33PAL

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
AE4M33PAL Advanced algorithms Rozsah výuky:2+2c
Garanti:  Role:P,V Jazyk výuky:EN
Vyučující:  Zakončení:Z,ZK
Zodpovědná katedra:13133 Kreditů:6 Semestr:Z

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: AE4M33PAL

Cíle studia:

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

Osnovy 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.

Osnovy 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.

Literatura:

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

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.^

Poznámka:

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

Webová stránka:

http://cw.felk.cvut.cz/doku.php/courses/ae4m33pal/start

Klíčová slova:

Directed and undirected graph, graph algorithm, syntax analysis, pattern matching, floating-point arithmetic.

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
MEKME1 Bezdrátové komunikace V 1
MEKME5 Komunikační systémy V 1
MEKME4 Sítě elektronických komunikací V 1
MEKME3 Elektronika V 1
MEKME2 Multimediální technika V 1
MEOI1 Umělá inteligence P 1
MEOI5NEW Softwarové inženýrství P 1
MEOI4 Počítačová grafika a interakce P 1
MEOI2 Počítačové inženýrství P 1
MEOI5 Softwarové inženýrství P 1
MEOI3 Počítačové vidění a digitální obraz P 1
MEEEM1 Technologické systémy V 1
MEEEM5 Ekonomika a řízení elektrotechniky V 1
MEEEM4 Ekonomika a řízení energetiky V 1
MEEEM3 Elektroenergetika V 1
MEEEM2 Elektrické stroje, přístroje a pohony V 1
MEKYR4 Letecké a kosmické systémy V 1
MEKYR1 Robotika V 1
MEKYR3 Systémy a řízení V 1
MEKYR2 Senzory a přístrojová technika V 1


Stránka vytvořena 22.10.2018 05:48:07, semestry: Z,L/2020-1, L/2017-8, L/2019-20, Z,L/2018-9, Z/2019-20, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.