| A4M33PAL | Pokročilá algoritmizace | Rozsah výuky: | 2+2c | ||
|---|---|---|---|---|---|
| Garant: | Matas J. | Typ předmětu: | P | Zakončení: | Z,ZK |
| Vyučující: | Genyk-Berezovskyj M., Vyskočil J. | ||||
| Zodpovědná katedra: | 13133 | Kreditů: | 6 | Semestr: | Z |
Anotace:
Základní grafové algoritmy a reprezentace grafů. Kombinatorické algoritmy. Aplikace teorie formálních jazyků v informatice - hledání v textu.
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. |
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 |
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.
|
Předmět je zahrnut do těchto studijních plánů:
| Stránka vytvořena 19. 5. 2013, semestry: L/2011-2, L/2012-3, L/2010-1, Z/2011-2, Z/2010-1, Z/2013-4, 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) |