# Popis předmětu - BE4M33PAL

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
 BE4M33PAL Advanced Algorithms Rozsah výuky: 2P+2C Garanti: Průša D. Role: PV,P,V Jazyk výuky: EN Vyučující: Genyk-Berezovskyj M., Průša D. Zakončení: Z,ZK Zodpovědná katedra: 13133 Kreditů: 6 Semestr: Z

Anotace:

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

Cíle studia:

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

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

Osnovy cvičení:

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

Literatura:

 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

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.

Webová stránka:

http://cw.fel.cvut.cz/wiki/courses/be4m33pal/start

Klíčová slova:

Directed and undirected graph, graph algorithm, priority queue, pattern matching,

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

 Plán Obor Role Dop. semestr MEOI7_2018 Umělá inteligence P 1 MEOI9_2018 Datové vědy P 1 MEOI8_2018 Bioinformatika P 1 MEOI4_2018 Počítačové inženýrství P 1 MEOI3_2018 Počítačová grafika P 1 MEOI2_2018 Kybernetická bezpečnost P 1 MEOI1_2018 Interakce člověka s počítačem P 1 MEOI6_2018 Softwarové inženýrství P 1 MEOI5_2018 Počítačové vidění a digitální obraz P 1 MEBIO_2018 Před zařazením do oboru V 1 MEBIO_2018 Před zařazením do oboru V 1 MEOI7_2016 Umělá inteligence P 1 MEOI9_2016 Datové vědy P 1 MEOI8_2016 Bioinformatika P 1 MEOI4_2016 Počítačové inženýrství P 1 MEOI3_2016 Počítačová grafika P 1 MEOI2_2016 Kybernetická bezpečnost P 1 MEOI1_2016 Interakce člověka s počítačem P 1 MEOI6_2016 Softwarové inženýrství P 1 MEOI5_2016 Počítačové vidění a digitální obraz P 1 MEBIO_2018 Před zařazením do oboru PV 1

 Stránka vytvořena 21.1.2020 12:50:52, semestry: Z,L/2020-1, L/2018-9, Z,L/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.