Advanced Algorithms
| Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
|---|---|---|---|---|
| BE4M33PAL | Z,ZK | 6 | 2P+2C | anglicky |
- Vztahy:
- Předmět BE4M33PAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět B4M33PAL (vztah je symetrický)
- Předmět BE4M33PAL může při kontrole studijních plánů nahradit předmět B4M33PAL
- Předmět BE4M33PAL může při kontrole studijních plánů nahradit předmět A4M33PAL
- Předmět BE4M33PAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět A4M33PAL (vztah je symetrický)
- Podmínkou zápisu na předmět BE4M33PAL je, že student si nejpozději ve stejném semestru zapsal příslušný počet předmětů ze skupiny BEZBM
- Předmět BE4M33PAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět A4M33PAL (vztah je symetrický)
- Předmět BE4M33PAL nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět B4M33PAL (vztah je symetrický)
- Předmět je ekvivalentní s AE4M33PAL .
- Garant předmětu:
- Daniel Průša
- Přednášející:
- Ondřej Drbohlav, Marko Genyk-Berezovskyj
- Cvičící:
- Marko Genyk-Berezovskyj
- 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:
- https://cw.fel.cvut.cz/wiki/courses/BE4M33PAL
- Rozvrh na zimní semestr 2024/2025:
-
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 Čt Pá - Rozvrh na letní semestr 2024/2025:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů:
-
- Open Informatics - Artificial Intelligence (povinný předmět programu)
- Open Informatics - Computer Vision and Image Processing (povinný předmět programu)
- Open Informatics - Software Engineering (povinný předmět programu)
- Open Informatics - Human-Computer Interaction (povinný předmět programu)
- Open Informatics - Cyber Security (povinný předmět programu)
- Open Informatics - Computer Graphics (povinný předmět programu)
- Open Informatics - Computer Engineering (povinný předmět programu)
- Open Informatics - Bioinformatics (povinný předmět programu)
- Open Informatics - Data Science (povinný předmět programu)
- Medical Electronics and Bioinformatics - Specialization Image Processing (PS)
- Medical Electronics and Bioinformatics - Specialization Signal Processing (povinně volitelný předmět)
- Medical Electronics and Bioinformatics - Specialization Bioinformatics (PS)
- Medical Electronics and Bioinformatics - Specialization Medical Instrumentation (povinně volitelný předmět)