Moodle FEL ČVUT
Pokročilá algoritmizace
B191 - Zimní 19/20
Tento předmět se nenachází v Moodle. Na jeho domovskou stránku se můžete dostat pomocí tlačítka "Stránka kurzu (mimo Moodle)" vpravo (pokud existuje).
Pokročilá algoritmizace - B4M33PAL
| Kredity | 6 |
| Semestry | zimní |
| Zakončení | zápočet a zkouška |
| Jazyk výuky | čeština |
| Rozsah výuky | 2P+2C |
Anotace
Základní grafové algoritmy a reprezentace grafů. Kombinatorické algoritmy. Aplikace teorie formálních jazyků v informatice - hledání v textu. \\Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A4M33PAL
Cíle studia
Základní přehled a dovednosti související s tématy předmětu.
Osnovy přednášek
Diskuse paměťové a časové složitosti probíraných datových typů a algoritmů je integrální součástí každého tématu, neuvádíme ji explicitně u každého tématu zvlášť.
1. Připomenutí asymptotické složitosti. Reprezentace grafů.
2. Minimální kostra grafu. Union-Find problém.
3. Eulerovy cesty. Orientované grafy: souvislost, acykličnost.
4. Haldy. Fibonacciho halda. Srovnání hald.
5. Dynamické datové struktury. Garbage collector.
6. Generování, enumerace a izomorfizmus datových struktur a kombinatorických objektů. Permutace, kombinace, variace, stromy.
7. Generování dalších kombinatorických struktur: k-prvkové podmožiny, Gray code, neizomorfní grafy.
8. Posloupnosti - vyhledávání interpolační, kvadratické; hledání mediánu v lineárním čase.
9. Konečné automaty, jejich implementace, redukce automatu.
10. Regulární výrazy a vyhledávání v textu pomocí regulárních výrazů.
11. Přibližné vyhledávání v textu pomocí konečných automatù, slovníkové automaty.
12. Hledání ve více dimenzích, K-D stromy, Quadtree.
13. Vyhledávací stromy: B a B+; 2-3-4 a R-B stromy.
14. Vyhledávací stromy: Trie, suffixový strom, splay tree.
1. Připomenutí asymptotické složitosti. Reprezentace grafů.
2. Minimální kostra grafu. Union-Find problém.
3. Eulerovy cesty. Orientované grafy: souvislost, acykličnost.
4. Haldy. Fibonacciho halda. Srovnání hald.
5. Dynamické datové struktury. Garbage collector.
6. Generování, enumerace a izomorfizmus datových struktur a kombinatorických objektů. Permutace, kombinace, variace, stromy.
7. Generování dalších kombinatorických struktur: k-prvkové podmožiny, Gray code, neizomorfní grafy.
8. Posloupnosti - vyhledávání interpolační, kvadratické; hledání mediánu v lineárním čase.
9. Konečné automaty, jejich implementace, redukce automatu.
10. Regulární výrazy a vyhledávání v textu pomocí regulárních výrazů.
11. Přibližné vyhledávání v textu pomocí konečných automatù, slovníkové automaty.
12. Hledání ve více dimenzích, K-D stromy, Quadtree.
13. Vyhledávací stromy: B a B+; 2-3-4 a R-B stromy.
14. Vyhledávací stromy: Trie, suffixový strom, splay tree.
Osnovy cvičení
Náplní cvičení a navazující domácí přípravy je především praktická implementace témat přednášky. Témata cvičení proto formálně kopírují témata přednášek.
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
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
Požadavky
Důležitou součástí cvičení je samostatná implementace datových typů a algoritmů přednášky. Znalost programování na urovni manipulace se spojovými strukturami v některém z rozšířených programovacích jazyků (C/C++/Java/...) je proto nezbytná. Další důležité informace naleznete na: http://cw.felk.cvut.cz/doku.php/courses/a4m33pal/start.